English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Polynomial Kernelization for Removing Induced Claws and Diamonds

MPS-Authors
/persons/resource/persons98374

van Leeuwen,  Erik Jan
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (public)

arXiv:1503.00704.pdf
(Preprint), 248KB

Supplementary Material (public)
There is no public supplementary material available
Citation

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.


Cite as: http://hdl.handle.net/11858/00-001M-0000-002C-5388-E
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