Independence and Efficient Domination on P 6 -free Graphs

DOI10.1145/3147214MaRDI QIDQ4554948zbMATH OpenOpenAlexFDO

Authors Daniel Lokshtanov, Marcin Pilipczuk, Erik Jan van Leeuwen

Publication date 12 November 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.02163

zbMATH Keywords

(quasi)polynomial-time algorithms\(P_6\)-free graphsefficient dominationindependence

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

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(lo{g}^{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.

Recommendations

• Independence and efficient domination on \(P_6\)-free graphs
• Efficient domination for classes of \(P_6\)-free graphs
• Efficient domination for some subclasses of P₆-free graphs in polynomial time
• Total dominations in P₆-free graphs
• A note on independent domination in graphs of girth 6
• scientific article; zbMATH DE number 5761816
• New Polynomial Case for Efficient Domination in P 6-free Graphs
• Weighted efficient domination in two subclasses of P₆-free graphs
• Weighted efficient domination for P₆-free and for P₅-free graphs
• Independent domination in subcubic graphs of girth at least six

Cited in

(7)

• Excluding hooks and their complements
• Maximum weight independent sets for (\(S_{1,2,4}\), triangle)-free graphs in polynomial time
• New results on independent sets in extensions of \(2K_2\)-free graphs
• Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs
• Independence and efficient domination on \(P_6\)-free graphs
• New Polynomial Case for Efficient Domination in P 6-free Graphs
• Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs

This page was built for publication: Independence and Efficient Domination on P ₆ -free Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4554948)