Loading...
Please wait, while we are loading the content...
Similar Documents
icient Domination on P 6-free Graphs
| Content Provider | Semantic Scholar |
|---|---|
| Author | Lokshtanov, Daniel Pilipczuk, Marcin |
| Copyright Year | 2017 |
| Abstract | In the Maximum Weight Independent Set problem, the input is a graph G , every vertex has a non-negative integer weight, and the task is to nd a set S of pairwise non-adjacent 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 the above 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 nd 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 P6-free graphs was the only class of graphs dened by a single forbidden induced subgraph on which the computational complexity of Maximum Weight Efficient Dominating Set was unknown. CCS Concepts: •Mathematics of computing → Graph theory; Graph algorithms; Combinatorics; •eory of computation → Graph algorithms analysis; Branch-and-bound; Complexity classes; Problems, reductions and completeness; Additional |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://sites.cs.ucsb.edu/~daniello/papers/p6isetTALG18.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
