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
