Independence and Efficient Domination on P 6 -free Graphs
| Autor: | Lokshtanov, Daniel, Pilipczuk, Marcin, Leeuwen, Erik Jan van, Sub Algorithms and Complexity, Algorithms and Complexity |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Computational complexity theory
010102 general mathematics Induced subgraph 0102 computer and information sciences Independence efficient domination 01 natural sciences Graph Vertex (geometry) Combinatorics Mathematics (miscellaneous) 010201 computation theory & mathematics Dominating set Independent set (quasi) polynomial-time algorithms P-6-free graphs Pairwise comparison 0101 mathematics MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | ACM Transactions on Algorithms, 14(1). Association for Computing Machinery (ACM) |
| ISSN: | 1549-6333 1549-6325 |
| DOI: | 10.1145/3147214 |
| Popis: | In the M aximum W eight I ndependent S et 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 nonadjacent 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 M aximum W eight I ndependent S et on P k -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 M aximum W eight E fficient D ominating S et 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 M aximum W eight E fficient D ominating S et was unknown. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|