Independence and efficient domination on P6-free graphs

Abstract

In the Maximum Weight Independent Set problem, the input is a graphG, every vertex has a non-negative integer weight, and the task is to find a set S of pairwise nonadjacent vertices, maximizing the total weight of the vertices in S. We give an nO(log2 n) time algorithm for this problem on graphs excluding the path P6 on 6 vertices as an induced subgraph. Currently, there is no constant k known for which Maximum Weight Independent Set on Pk -free graphs becomes NP-hard, 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 this algorithm, we also give a polynomial-time algorithm for Maximum Weight Efficient Dominating Set on P6-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 inG 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 P6-free graphs was the only class of graphs defined by a single forbidden induced subgraph on which the computational complexity of Maximum Weight Efficient Dominating Set was unknown.