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 that the problem is polynomialtime solvable, which is witnessed by algorithmic results for graphs excluding some small paths or subdivided claws. A more conclusive evidence was given by the recent breakthrough result by Gartland and Lokshtanov [FOCS 2020]: They proved that MWIS can be solved in quasipolynomial time in Hfree graphs, where H is any fixed path. If H is an arbitrary subdivided claw, we know much less: The problem admits a QPTAS and a subexponentialtime algorithm [Chudnovsky et al., SODA 2019].
In this paper we make an important step towards solving the problem by showing that for any subdivided claw H, MWIS is polynomialtime solvable in Hfree graphs of bounded degree.
more »
« less
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 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 APXhard in Hfree graphs, the problem admits a quasipolynomial 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.
more »
« less
 Award ID(s):
 1763817
 NSFPAR ID:
 10164193
 Date Published:
 Journal Name:
 Proceedings of the annual ACMSIAM symposium on discrete algorithms
 Format(s):
 Medium: X
 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 at least 5. This problem is closely related to the well known open problem of determining the complexity of 3Coloring of Ptfree graphs. We show that for every odd k ≥ 5 the CkColoring problem, even in the precoloringextension variant, can be solved in polynomial time in P9free graphs. On the other hand, we prove that the extension version of CkColoring is NPcomplete for Ffree graphs whenever some component of F is not a subgraph of a subdivided claw.more » « less

A _theta_ is a graph consisting of two nonadjacent vertices and three internally disjoint paths between them, each of length at least two. For a family $\mathcal{H}$ of graphs, we say a graph $G$ is $\mathcal{H}$_free_ if no induced subgraph of $G$ is isomorphic to a member of $\mathcal{H}$. We prove a conjecture of Sintiari and Trotignon, that there exists an absolute constant $c$ for which every (theta, triangle)free graph $G$ has treewidth at most $c\log (V(G))$. A construction by Sintiari and Trotignon shows that this bound is asymptotically best possible, and (theta, triangle)free graphs comprise the first known hereditary class of graphs with arbitrarily large yet logarithmic treewidth.Our main result is in fact a generalization of the above conjecture, that treewidth is at most logarithmic in $V(G)$ for every graph $G$ excluding the socalled _threepathconfigurations_ as well as a fixed complete graph. It follows that several NPhard problems such as Stable Set, Vertex Cover, Dominating Set and $k$Coloring (for fixed $k$) admit polynomial time algorithms in graphs excluding the threepathconfigurations and a fixed complete graph.more » « less

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, we obtain a polynomialtime $O(t \log t)$approximation algorithm, improving upon the previously known polynomialtime $t^2$approximation by Butman et al. In the same class of graphs we show that it is $\NP$hard to obtain a $(t1\epsilon)$approximation for any fixed $t \ge 3$ and $\epsilon > 0$. The approximation ratio for dominating set extends to the intersection graphs of a collection of $t$pseudodisks (nicely intersecting $t$tuples of closed Jordan domains). We obtain an $\Omega(1/t)$approximation for the \emph{maximumweight independent set} in the intersection graph of $t$pseudodisks in polynomial time. Our results are obtained via simple reductions to existing algorithms by appropriately bounding the union complexity of the objects under consideration.more » « less

null (Ed.)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 work has obtained a similar result for the more general problem of hypergraph cut sparsifiers. However, all known sparsification algorithms require Ω(n + m) time where n denotes the number of vertices and m denotes the number of hyperedges in the hypergraph. Since m can be exponentially large in n, a natural question is if it is possible to create a hypergraph cut sparsifier in time polynomial in n, independent of the number of edges. We resolve this question in the affirmative, giving the first sublinear time algorithm for this problem, given appropriate query access to the hypergraph. Specifically, we design an algorithm that constructs a (1 ± ε)approximate cut sparsifier of a hypergraph H(V,E) in polynomial time in n, independent of the number of hyperedges, when given access to the hypergraph using the following two queries: 1) given any cut (S, ̄S), return the size δ_E(S) (cut value queries); and 2) given any cut (S, ̄S), return a uniformly at random edge crossing the cut (cut edge sample queries). Our algorithm outputs a sparsifier with Õ(n/ε²) edges, which is essentially optimal. We then extend our results to show that cut value and cut edge sample queries can also be used to construct hypergraph spectral sparsifiers in poly(n) time, independent of the number of hyperedges. We complement the algorithmic results above by showing that any algorithm that has access to only one of the above two types of queries can not give a hypergraph cut sparsifier in time that is polynomial in n. Finally, we show that our algorithmic results also hold if we replace the cut edge sample queries with a pair neighbor sample query that for any pair of vertices, returns a random edge incident on them. In contrast, we show that having access only to cut value queries and queries that return a random edge incident on a given single vertex, is not sufficient.more » « less