Title | ||
---|---|---|
Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs. |
Abstract | ||
---|---|---|
In the Maximum Independent Set problem we are asked to find a set of pairwise nonadjacent vertices in a given graph with the maximum possible cardinality. In general graphs, this classical problem is known to be NP-hard and hard to approximate within a factor of n1−ε for any ε > 0. Due to this, investigating the complexity of Maximum Independent Set in various graph classes in hope of finding better tractability results is an active research direction.
In H-free graphs, that is, graphs not containing a fixed graph H as an induced subgraph, the problem is known to remain NP-hard and APX-hard whenever H contains a cycle, a vertex of degree at least four, or two vertices of degree at least three in one connected component. For the remaining cases, where every component of H is a path or a subdivided claw, the complexity of Maximum Independent Set remains widely open, with only a handful of polynomial-time solvability results for small graphs H such as P5, P6, the claw, or the fork.
We prove that for every such "possibly tractable" graph H there exists an algorithm that, given an H-free graph G and an accuracy parameter ε > 0, finds an independent set in G of cardinality within a factor of (1 − ε) of the optimum in time exponential in a polynomial of log |V(G)| and ε−1. That is, we show that for every graph H for which Maximum Independent
Set is not known to be APX-hard in H-free graphs, the problem admits a quasi-polynomial time approximation scheme in this graph class. Our algorithm works also in the more general weighted setting, where the input graph is supplied with a weight function on vertices and we are maximizing the total weight of an independent set.
|
Year | DOI | Venue |
---|---|---|
2020 | 10.5555/3381089.3381228 | SODA '20: ACM-SIAM Symposium on Discrete Algorithms
Salt Lake City
Utah
January, 2020 |
Field | DocType | Citations |
Graph,Discrete mathematics,Combinatorics,Computer science,Quasi-polynomial,Independent set | Conference | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Maria Chudnovsky | 1 | 390 | 46.13 |
Marcin Pilipczuk | 2 | 436 | 47.86 |
michal pilipczuk | 3 | 403 | 51.93 |
Stéphan Thomassé | 4 | 651 | 66.03 |