English

Item

ITEM ACTIONSEXPORT
Polynomial Kernelization for Removing Induced Claws and Diamonds

Cygan, M., Pilipczuk, M., Pilipczuk, M., van Leeuwen, E. J., & Wrochna, M. (2015). Polynomial Kernelization for Removing Induced Claws and Diamonds. Retrieved from http://arxiv.org/abs/1503.00704.

Item is

show hide
Genre: Paper

Files

show Files
hide Files
:
arXiv:1503.00704.pdf (Preprint), 248KB
Name:
arXiv:1503.00704.pdf
Description:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
-
-

show

Creators

show
hide
Creators:
Cygan, Marek1, Author
Pilipczuk, Marcin1, Author
Pilipczuk, Michał1, Author
van Leeuwen, Erik Jan2, Author
Wrochna, Marcin1, Author
Affiliations:
1External Organizations, ou_persistent22
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019

Content

show
hide
Free keywords: Computer Science, Data Structures and Algorithms, cs.DS
Abstract: A graph is called (claw,diamond)-free if it contains neither a claw (a $K_{1,3}$) nor a diamond (a $K_4$ with an edge removed) as an induced subgraph. Equivalently, (claw,diamond)-free graphs can be characterized as line graphs of triangle-free graphs, or as linear dominoes, i.e., graphs in which every vertex is in at most two maximal cliques and every edge is in exactly one maximal clique. In this paper we consider the parameterized complexity of the (claw,diamond)-free Edge Deletion problem, where given a graph $G$ and a parameter $k$, the question is whether one can remove at most $k$ edges from $G$ to obtain a (claw,diamond)-free graph. Our main result is that this problem admits a polynomial kernel. We complement this finding by proving that, even on instances with maximum degree $6$, the problem is NP-complete and cannot be solved in time $2^{o(k)}\cdot |V(G)|^{O(1)}$ unless the Exponential Time Hypothesis fail

Details

show
hide
Language(s): eng - English
Dates: 2015-03-022015
Publication Status: Published online
Pages: 17 p.
Publishing info: -
Rev. Type: -
Identifiers: arXiv: 1503.00704
URI: http://arxiv.org/abs/1503.00704
BibTex Citekey: DBLP:journals/corr/CyganPPLW15
Degree: -

show

show

show

show