A Linear Kernel for Co-Path/Cycle Packing View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2010

AUTHORS

Zhi-Zhong Chen , Michael Fellows , Bin Fu , Haitao Jiang , Yang Liu , Lusheng Wang , Binhai Zhu

ABSTRACT

Bounded-Degree Vertex Deletion is a fundamental problem in graph theory that has new applications in computational biology. In this paper, we address a special case of Bounded-Degree Vertex Deletion, the Co-Path/Cycle Packing problem, which asks to delete as few vertices as possible such that the graph of the remaining (residual) vertices is composed of disjoint paths and simple cycles. The problem falls into the well-known class of ’node-deletion problems with hereditary properties’, is hence NP-complete and unlikely to admit a polynomial time approximation algorithm with approximation factor smaller than 2. In the framework of parameterized complexity, we present a kernelization algorithm that produces a kernel with at most 37k vertices, improving on the super-linear kernel of Fellows et al.’s general theorem for Bounded-Degree Vertex Deletion. Using this kernel,and the method of bounded search trees, we devise an FPT algorithm that runs in time O*(3.24k). On the negative side, we show that the problem is APX-hard and unlikely to have a kernel smaller than 2k by a reduction from Vertex Cover. More... »

PAGES

90-102

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-14355-7_10

DOI

http://dx.doi.org/10.1007/978-3-642-14355-7_10

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1022550977


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Zhi-Zhong", 
        "id": "sg:person.015654265661.98", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "The University of New Castle, 2308, Callaghan, NSW, Australia", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "The University of New Castle, 2308, Callaghan, NSW, Australia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Fellows", 
        "givenName": "Michael", 
        "id": "sg:person.011724401755.73", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011724401755.73"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Texas-American, 78739-2999, Edinburg, TX, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Department of Computer Science, University of Texas-American, 78739-2999, Edinburg, TX, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Fu", 
        "givenName": "Bin", 
        "id": "sg:person.014764020611.79", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014764020611.79"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Montana State University, 59717-3880, Bozeman, MT, USA", 
          "id": "http://www.grid.ac/institutes/grid.41891.35", 
          "name": [
            "Department of Computer Science, Montana State University, 59717-3880, Bozeman, MT, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Jiang", 
        "givenName": "Haitao", 
        "id": "sg:person.01212750653.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01212750653.39"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Texas-American, 78739-2999, Edinburg, TX, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Department of Computer Science, University of Texas-American, 78739-2999, Edinburg, TX, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Liu", 
        "givenName": "Yang", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong", 
          "id": "http://www.grid.ac/institutes/grid.35030.35", 
          "name": [
            "Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wang", 
        "givenName": "Lusheng", 
        "id": "sg:person.01105113721.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Montana State University, 59717-3880, Bozeman, MT, USA", 
          "id": "http://www.grid.ac/institutes/grid.41891.35", 
          "name": [
            "Department of Computer Science, Montana State University, 59717-3880, Bozeman, MT, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zhu", 
        "givenName": "Binhai", 
        "id": "sg:person.0671007714.04", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0671007714.04"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "Bounded-Degree Vertex Deletion is a fundamental problem in graph theory that has new applications in computational biology. In this paper, we address a special case of Bounded-Degree Vertex Deletion, the Co-Path/Cycle Packing problem, which asks to delete as few vertices as possible such that the graph of the remaining (residual) vertices is composed of disjoint paths and simple cycles. The problem falls into the well-known class of \u2019node-deletion problems with hereditary properties\u2019, is hence NP-complete and unlikely to admit a polynomial time approximation algorithm with approximation factor smaller than 2. In the framework of parameterized complexity, we present a kernelization algorithm that produces a kernel with at most 37k vertices, improving on the super-linear kernel of Fellows et al.\u2019s general theorem for Bounded-Degree Vertex Deletion. Using this kernel,and the method of bounded search trees, we devise an FPT algorithm that runs in time O*(3.24k). On the negative side, we show that the problem is APX-hard and unlikely to have a kernel smaller than 2k by a reduction from Vertex Cover.", 
    "editor": [
      {
        "familyName": "Chen", 
        "givenName": "Bo", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-14355-7_10", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-14354-0", 
        "978-3-642-14355-7"
      ], 
      "name": "Algorithmic Aspects in Information and Management", 
      "type": "Book"
    }, 
    "keywords": [
      "Vertex Deletion", 
      "polynomial-time approximation algorithm", 
      "node-deletion problems", 
      "time approximation algorithm", 
      "general theorem", 
      "graph theory", 
      "vertex cover", 
      "hereditary properties", 
      "approximation algorithm", 
      "special case", 
      "cycle packing problem", 
      "approximation factor", 
      "kernelization algorithm", 
      "parameterized complexity", 
      "FPT algorithm", 
      "cycle packing", 
      "computational biology", 
      "vertices", 
      "packing problem", 
      "disjoint paths", 
      "Fellows et al", 
      "fundamental problem", 
      "simple cycle", 
      "kernel", 
      "algorithm", 
      "search tree", 
      "problem", 
      "linear kernel", 
      "theorem", 
      "et al", 
      "graph", 
      "new applications", 
      "theory", 
      "class", 
      "complexity", 
      "NPs", 
      "path", 
      "properties", 
      "applications", 
      "framework", 
      "al", 
      "negative side", 
      "cases", 
      "time", 
      "trees", 
      "packing", 
      "side", 
      "biology", 
      "reduction", 
      "cycle", 
      "cover", 
      "factors", 
      "deletion", 
      "method", 
      "paper"
    ], 
    "name": "A Linear Kernel for Co-Path/Cycle Packing", 
    "pagination": "90-102", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1022550977"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-14355-7_10"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-14355-7_10", 
      "https://app.dimensions.ai/details/publication/pub.1022550977"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:46", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_342.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-14355-7_10"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14355-7_10'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14355-7_10'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14355-7_10'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14355-7_10'


 

This table displays all metadata directly associated to this object as RDF triples.

167 TRIPLES      23 PREDICATES      81 URIs      74 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-14355-7_10 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nb7b259eaa5ce41ba8cb1d7d29be9806b
4 schema:datePublished 2010
5 schema:datePublishedReg 2010-01-01
6 schema:description Bounded-Degree Vertex Deletion is a fundamental problem in graph theory that has new applications in computational biology. In this paper, we address a special case of Bounded-Degree Vertex Deletion, the Co-Path/Cycle Packing problem, which asks to delete as few vertices as possible such that the graph of the remaining (residual) vertices is composed of disjoint paths and simple cycles. The problem falls into the well-known class of ’node-deletion problems with hereditary properties’, is hence NP-complete and unlikely to admit a polynomial time approximation algorithm with approximation factor smaller than 2. In the framework of parameterized complexity, we present a kernelization algorithm that produces a kernel with at most 37k vertices, improving on the super-linear kernel of Fellows et al.’s general theorem for Bounded-Degree Vertex Deletion. Using this kernel,and the method of bounded search trees, we devise an FPT algorithm that runs in time O*(3.24k). On the negative side, we show that the problem is APX-hard and unlikely to have a kernel smaller than 2k by a reduction from Vertex Cover.
7 schema:editor N33432a6c9d604366a3f1f18de566abf3
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nd6828bed23a84daf91ea99f998a4f1ba
12 schema:keywords FPT algorithm
13 Fellows et al
14 NPs
15 Vertex Deletion
16 al
17 algorithm
18 applications
19 approximation algorithm
20 approximation factor
21 biology
22 cases
23 class
24 complexity
25 computational biology
26 cover
27 cycle
28 cycle packing
29 cycle packing problem
30 deletion
31 disjoint paths
32 et al
33 factors
34 framework
35 fundamental problem
36 general theorem
37 graph
38 graph theory
39 hereditary properties
40 kernel
41 kernelization algorithm
42 linear kernel
43 method
44 negative side
45 new applications
46 node-deletion problems
47 packing
48 packing problem
49 paper
50 parameterized complexity
51 path
52 polynomial-time approximation algorithm
53 problem
54 properties
55 reduction
56 search tree
57 side
58 simple cycle
59 special case
60 theorem
61 theory
62 time
63 time approximation algorithm
64 trees
65 vertex cover
66 vertices
67 schema:name A Linear Kernel for Co-Path/Cycle Packing
68 schema:pagination 90-102
69 schema:productId N3c85ab5105004562bc1f5ad9d9d05ec0
70 N9653825076a54626ad77b30a627fbcef
71 schema:publisher N21401683a1184522a9c78464056ab076
72 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022550977
73 https://doi.org/10.1007/978-3-642-14355-7_10
74 schema:sdDatePublished 2022-05-20T07:46
75 schema:sdLicense https://scigraph.springernature.com/explorer/license/
76 schema:sdPublisher Nef65d3ad74654160a1a8382e19489f50
77 schema:url https://doi.org/10.1007/978-3-642-14355-7_10
78 sgo:license sg:explorer/license/
79 sgo:sdDataset chapters
80 rdf:type schema:Chapter
81 N0286db51cbfe4238b4d7dd7e7b091d74 rdf:first sg:person.014764020611.79
82 rdf:rest N12ed4ec45f61479687d9849275bc85c1
83 N12ed4ec45f61479687d9849275bc85c1 rdf:first sg:person.01212750653.39
84 rdf:rest N74a2a5d06ca1452f81c5ce1712727e13
85 N13e1e99e5b7847f88f1eb45efe17cb05 schema:familyName Chen
86 schema:givenName Bo
87 rdf:type schema:Person
88 N21401683a1184522a9c78464056ab076 schema:name Springer Nature
89 rdf:type schema:Organisation
90 N33432a6c9d604366a3f1f18de566abf3 rdf:first N13e1e99e5b7847f88f1eb45efe17cb05
91 rdf:rest rdf:nil
92 N3c85ab5105004562bc1f5ad9d9d05ec0 schema:name dimensions_id
93 schema:value pub.1022550977
94 rdf:type schema:PropertyValue
95 N6c79275af2464c11bde014f07c3c97d4 rdf:first sg:person.01105113721.52
96 rdf:rest Nacd40c9ee94f499cbece52d6ae5a44d0
97 N74a2a5d06ca1452f81c5ce1712727e13 rdf:first Nd86a93ab165b41f9b0041efa46240991
98 rdf:rest N6c79275af2464c11bde014f07c3c97d4
99 N9653825076a54626ad77b30a627fbcef schema:name doi
100 schema:value 10.1007/978-3-642-14355-7_10
101 rdf:type schema:PropertyValue
102 Nacd40c9ee94f499cbece52d6ae5a44d0 rdf:first sg:person.0671007714.04
103 rdf:rest rdf:nil
104 Nb7b259eaa5ce41ba8cb1d7d29be9806b rdf:first sg:person.015654265661.98
105 rdf:rest Nc654b5cca2894f2f9188a24e8ce2512e
106 Nc654b5cca2894f2f9188a24e8ce2512e rdf:first sg:person.011724401755.73
107 rdf:rest N0286db51cbfe4238b4d7dd7e7b091d74
108 Nd6828bed23a84daf91ea99f998a4f1ba schema:isbn 978-3-642-14354-0
109 978-3-642-14355-7
110 schema:name Algorithmic Aspects in Information and Management
111 rdf:type schema:Book
112 Nd86a93ab165b41f9b0041efa46240991 schema:affiliation grid-institutes:None
113 schema:familyName Liu
114 schema:givenName Yang
115 rdf:type schema:Person
116 Nef65d3ad74654160a1a8382e19489f50 schema:name Springer Nature - SN SciGraph project
117 rdf:type schema:Organization
118 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
119 schema:name Information and Computing Sciences
120 rdf:type schema:DefinedTerm
121 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
122 schema:name Computation Theory and Mathematics
123 rdf:type schema:DefinedTerm
124 sg:person.01105113721.52 schema:affiliation grid-institutes:grid.35030.35
125 schema:familyName Wang
126 schema:givenName Lusheng
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52
128 rdf:type schema:Person
129 sg:person.011724401755.73 schema:affiliation grid-institutes:None
130 schema:familyName Fellows
131 schema:givenName Michael
132 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011724401755.73
133 rdf:type schema:Person
134 sg:person.01212750653.39 schema:affiliation grid-institutes:grid.41891.35
135 schema:familyName Jiang
136 schema:givenName Haitao
137 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01212750653.39
138 rdf:type schema:Person
139 sg:person.014764020611.79 schema:affiliation grid-institutes:None
140 schema:familyName Fu
141 schema:givenName Bin
142 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014764020611.79
143 rdf:type schema:Person
144 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
145 schema:familyName Chen
146 schema:givenName Zhi-Zhong
147 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
148 rdf:type schema:Person
149 sg:person.0671007714.04 schema:affiliation grid-institutes:grid.41891.35
150 schema:familyName Zhu
151 schema:givenName Binhai
152 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0671007714.04
153 rdf:type schema:Person
154 grid-institutes:None schema:alternateName Department of Computer Science, University of Texas-American, 78739-2999, Edinburg, TX, USA
155 The University of New Castle, 2308, Callaghan, NSW, Australia
156 schema:name Department of Computer Science, University of Texas-American, 78739-2999, Edinburg, TX, USA
157 The University of New Castle, 2308, Callaghan, NSW, Australia
158 rdf:type schema:Organization
159 grid-institutes:grid.35030.35 schema:alternateName Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong
160 schema:name Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong
161 rdf:type schema:Organization
162 grid-institutes:grid.412773.4 schema:alternateName Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan
163 schema:name Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan
164 rdf:type schema:Organization
165 grid-institutes:grid.41891.35 schema:alternateName Department of Computer Science, Montana State University, 59717-3880, Bozeman, MT, USA
166 schema:name Department of Computer Science, Montana State University, 59717-3880, Bozeman, MT, USA
167 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...