# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Independence and Efficient Domination on P6-free Graphs

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:1507.02163.pdf

(Preprint), 652KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Lokshtanov, D., Pilipczuk, M., & van Leeuwen, E. J. (2015). Independence and Efficient Domination on P6-free Graphs. Retrieved from http://arxiv.org/abs/1507.02163.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0029-2494-4

##### 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.