For graphs G and H, we say that G is Hfree if it does not contain H as an induced subgraph. Already in the early 1980s Alekseev observed that if H is connected, then the Max Weight Independent Set problem (MWIS) remains NPhard in Hfree graphs, unless H is a path or a subdivided claw, i.e., a graph obtained from the threeleaf star by subdividing each edge some number of times (possibly zero). Since then determining the complexity of MWIS in these remaining cases is one of the most important problems in algorithmic graph theory. A general belief is thatmore »
Quasipolynomial time approximation schemes for the Maximum Weight Independent Set Problem in Hfree 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 NPhard 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 Hfree graphs, that is, graphs not containing a fixed graph H as an induced subgraph, the problem is known to remain NPhard and APXhard 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 polynomialtime 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 Hfree graph G and an accuracy parameter ε > 0, finds an independent more »
 Award ID(s):
 1763817
 Publication Date:
 NSFPAR ID:
 10164193
 Journal Name:
 Proceedings of the annual ACMSIAM symposium on discrete algorithms
 Sponsoring Org:
 National Science Foundation
More Like this


For a graph F, a graph G is Ffree if it does not contain an induced subgraph isomorphic to F. For two graphs G and H, an Hcoloring of G is a mapping f : V (G) → V (H) such that for every edge uv ∈ E(G) it holds that f(u)f(v) ∈ E(H). We are interested in the complexity of the problem HColoring, which asks for the existence of an Hcoloring of an input graph G. In particular, we consider HColoring of Ffree graphs, where F is a fixed graph and H is an odd cycle of length atmore »

Intersection graphs of planar geometric objects such as intervals, disks, rectangles and pseudodisks are wellstudied. 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 multipleinterval graphs. Subsequent work by Kammer et al.\ (APPROXRANDOM 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{minimumweight dominating set problem} in $t$interval graphs, wemore »

The problem of sparsifying a graph or a hypergraph while approximately preserving its cut structure has been extensively studied and has many applications. In a seminal work, Benczúr and Karger (1996) showed that given any nvertex undirected weighted graph G and a parameter ε ∈ (0,1), there is a nearlinear time algorithm that outputs a weighted subgraph G' of G of size Õ(n/ε²) such that the weight of every cut in G is preserved to within a (1 ± ε)factor in G'. The graph G' is referred to as a (1 ± ε)approximate cut sparsifier of G. Subsequent recent workmore »

We present a weighted approach to compute a maximum cardinality matching in an arbitrary bipartite graph. Our main result is a new algorithm that takes as input a weighted bipartite graph G(A cup B,E) with edge weights of 0 or 1. Let w <= n be an upper bound on the weight of any matching in G. Consider the subgraph induced by all the edges of G with a weight 0. Suppose every connected component in this subgraph has O(r) vertices and O(mr/n) edges. We present an algorithm to compute a maximum cardinality matching in G in O~(m(sqrt{w} + sqrt{r}more »