English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

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

Files

show Files
hide Files
:
arXiv:1503.00704.pdf (Preprint), 248KB
Name:
arXiv:1503.00704.pdf
Description:
File downloaded from arXiv at 2017-02-02 09:57
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

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: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 1503.00704
URI: http://arxiv.org/abs/1503.00704
BibTex Citekey: DBLP:journals/corr/CyganPPLW15
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show