hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS
Abstract:
In the Independent set problem, the input is a graph $G$, every vertex has a
non-negative integer weight, and the task is to find a set $S$ of pairwise
non-adjacent vertices, maximizing the total weight of the vertices in $S$. We
give an $n^{O (\log^2 n)}$ time algorithm for this problem on graphs excluding
the path $P_6$ on $6$ vertices as an induced subgraph. Currently, there is no
constant $k$ known for which Independent Set on $P_{k}$-free graphs becomes
NP-complete, and our result implies that if such a $k$ exists, then $k > 6$
unless all problems in NP can be decided in (quasi)polynomial time.
Using the combinatorial tools that we develop for the above algorithm, we
also give a polynomial-time algorithm for Efficient Dominating Set on
$P_6$-free graphs. In this problem, the input is a graph $G$, every vertex has
an integer weight, and the objective is to find a set $S$ of maximum weight
such that every vertex in $G$ has exactly one vertex in $S$ in its closed
neighborhood, or to determine that no such set exists. Prior to our work, the
class of $P_6$-free graphs was the only class of graphs defined by a single
forbidden induced subgraph on which the computational complexity of Efficient
Dominating Set was unknown.
