Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
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 more »
Authors:
; ; ;
Award ID(s):
Publication Date:
NSF-PAR ID:
10164193
Journal Name:
Proceedings of the annual ACMSIAM symposium on discrete algorithms
3. Intersection graphs of planar geometric objects such as intervals, disks, rectangles and pseudodisks are well-studied. Motivated by various applications, Butman et al. (ACM Trans. Algorithms, 2010) considered algorithmic questions in intersection graphs of $t$-intervals. A $t$-interval is a union of $t$ intervals --- these graphs are also referred to as multiple-interval graphs. Subsequent work by Kammer et al.\ (APPROX-RANDOM 2010) considered intersection graphs of $t$-disks (union of $t$ disks), and other geometric objects. In this paper we revisit some of these algorithmic questions via more recent developments in computational geometry. For the \emph{minimum-weight dominating set problem} in $t$-interval graphs, wemore »