Vertex Partitioning in Graphs: From Structure to Algorithms

A classic result from Robertson and Seymour’s Graph Minors Project is the Grid Minor Theorem, which states that a graph has large treewidth if and only if it has a large grid minor. The Grid Minor Theorem characterizes the relationship between bounded treewidth and minors. Recently, much research on treewidth has focused on the relationship between bounded treewidth and induced subgraphs, aiming for an analog of the Grid Minor Theorem for induced subgraphs. Currently, there are several results that identify hereditary graph classes of bounded treewidth, but no complete characterization has yet been found. In this talk, we review recent progress and results involving induced subgraph obstructions to bounded treewidth.

Call a graph $G$ linear if $V(G)$ admits a partition into two sets $S$ and $P$ such that:

• $\mathrm{■}$

  $S$ is stable;

• $\mathrm{■}$

  $P$ induces a path;

• $\mathrm{■}$

  every vertex of $P$ has at most one neighbour in $S$.

Inspired by the study of treewidth (in the hereditary closure) of linear graphs, we formulate a word-combinatorial problem concerning the minimum length of words with certain properties. We describe the beginning of a solution to the problem.

There are many examples of a packing and covering duality: either there are many disjoint $A$–$B$-paths (a packing), or there is a small vertex set meeting all $A$–$B$-paths (a covering); either there are many disjoint cycles or a small cycle cover; either there are many disjoint $K_4$-subdivisions or a small vertex set meeting them all, and so on.

In this survey talk I will discuss several such packing and covering dualities. We will look at variants, for example, when the graphs is additionally endowed with group edge weights, and I will try to present as many open problems as possible.

A class $ℱ$ of graphs is called tame if every graph in $ℱ$ on n vertices contains at most $n^{O(1)}$ minimal separators, quasi-tame if every graph in $ℱ$ on $n$ vertices contains at most $2^{{\log }^{O(1)}(n)}$ minimal separators, and feral if there exists a constant $c>1$ so that $F$ contains $n$-vertex graphs with at least $c^n$ minimal separators for arbitrarily large $n$. The classification of graph classes into (quasi-) tame or feral has numerous algorithmic consequences, and has recently received considerable attention.

In this talk we precisely characterize the structure of graphs which have few minimal separators. Specifically we show that every graph which excludes certain graphs called $k$-creatures and $k$-critters as induced subgraphs has at most quasi-polynomially many minimal separators. We then demonstrate that this sufficient condition for having few minimal separators is the “right” one. In particular we show that every hereditary graph class $ℱ$ definable in CMSO logic that contains $k$-creatures or $k$-critters for every $k$ is feral.

We study the parameterized complexity of various classic vertex-deletion problems such as Odd cycle transversal, Vertex planarization, and Chordal vertex deletion under hybrid parameterizations. Existing FPT algorithms for these problems either focus on the parameterization by solution size, detecting solutions of size $k$ in time $f(k)\cdot n^{O(1)}$, or width parameterizations, finding arbitrarily large optimal solutions in time $f(w)\cdot n^{O(1)}$ for some width measure like treewidth. We unify these lines of research by presenting FPT algorithms for parameterizations that can simultaneously be arbitrarily much smaller than the solution size and the treewidth.

The first class of parameterizations is based on the notion of elimination distance of the input graph to the target graph class $H$, which intuitively measures the number of rounds needed to obtain a graph in $H$ by removing one vertex from each connected component in each round. The second class of parameterizations consists of a relaxation of the notion of treewidth, allowing arbitrarily large bags that induce subgraphs belonging to the target class of the deletion problem as long as these subgraphs have small neighborhoods. Both kinds of parameterizations have been introduced recently and have already spawned several independent results.

Our contribution is twofold. First, we present a framework for computing approximately optimal decompositions related to these graph measures. Namely, if the cost of an optimal decomposition is $k$, we show how to find a decomposition of cost $k^{O(1)}$ in time $f(k)\cdot n^{O(1)}$. This is applicable to any class H for which we can solve the so-called separation problem. Secondly, we exploit the constructed decompositions for solving vertex-deletion problems by extending ideas from algorithms using iterative compression and the finite state property. For the three mentioned vertex-deletion problems, and all problems which can be formulated as hitting a finite set of connected forbidden (a) minors or (b) (induced) subgraphs, we obtain FPT algorithms with respect to both studied parameterizations. For example, we present an algorithm running in time $n^{O(1)}+2^{(k^O(1))\cdot (n+m)}$ and polynomial space for Odd cycle transversal parameterized by the elimination distance $k$ to the class of bipartite graphs.

The independence number of a tree decomposition is the maximum of the independence numbers of the subgraphs induced by its bags. The tree-independence number of a graph is the minimum independence number of a tree decomposition of it. Several NP-hard graph problems, like maximum weight independent set, can be solved in polynomial time if the input graph is given with a tree decomposition of bounded independence number. I discuss results about computing the tree-independence number of a graph, and also its relation to a graph parameter “minor-matching hypertree width” of Yolov [SODA 2018].

The fractional and circular chromatic numbers are the two most well-known rational relaxations of the chromatic number of a graph. During the talk, we introduce the notion of gyrocoloring, a new recent relaxation of the chromatic number. Gyrocoloring of graphs stems from the notion of a coloring base studied by Avila and Candela in ergodic theory. We present various results concerning gyrocolorings of graphs, in particular, we show that the gyrochromatic chromatic is sandwiched between the fractional and circular chromatic numbers and it is robust in the sense that it permits various alternative definitions, analogous to alternative definitions of fractional and circular chromatic numbers.

In this talk I will survey fairly recent (past 10 years or so) developments for algorithms for Independent Set on $P_k$-free graphs, as well as extensions to other graph classes (excluding long cycles or long claws as induced subgraphs), and to other problems (such as Feedback Vertex Set or 3-Coloring).

A graph $G$ is $H$-subgraph-free if $G$ does not contain $H$ as a (not necessarily induced) subgraph. We make inroads into the classification of three problems for $H$-subgraph-free graphs that have the properties that they are solvable in polynomial time on classes of bounded treewidth and NP-complete on subcubic graphs, yet NP-hardness is not preserved under edge subdivision. The three problems are $k$-Induced Disjoint Paths, $C_5$-Colouring and Hamilton Cycle. Although we do not complete the classifications, we show that the boundary between polynomial time and NP-complete differs for $C_5$-Colouring from the other two problems.

An oriented graph is a digraph that does not contain a directed cycle of length two. An (oriented) graph $D$ is $H$-free if $D$ does not contain $H$ as an induced sub(di)graph. The Gyárfás-Sumner conjecture is a widely-open conjecture on simple graphs, which states that for any forest $F$, there is some function $f$ such that every $F$-free graph $G$ with clique number $\omega (G)$ has chromatic number at most $f(\omega (G))$. Aboulker, Charbit, and Naserasr [Extension of Gyárfás-Sumner Conjecture to Digraphs; E-JC 2021] proposed an analogue of this conjecture to the dichromatic number of oriented graphs. The dichromatic number of a digraph $D$ is the minimum number of colors required to color the vertex set of $D$ so that no directed cycle in $D$ is monochromatic.

Aboulker, Charbit, and Naserasr’s $\overrightarrow{\chi }$-boundedness conjecture states that for every oriented forest $F$, there is some function $f$ such that every $F$-free oriented graph $D$ has dichromatic number at most $f(\omega (D))$, where $\omega (D)$ is the size of a maximum clique in the graph underlying $D$. In this paper, we perform the first step towards proving Aboulker, Charbit, and Naserasr’s $\overrightarrow{\chi }$-boundedness conjecture by showing that it holds when $F$ is any orientation of a path on four vertices.

In this talk, we consider the parameterized complexity of Diameter in the streaming paradigm. The streaming paradigm is a model where our graph is not in memory, but we inspect it through the so-called “stream”. A focus on memory-efficiency is crucial in this setting. On the positive end, knowing a vertex cover of size k allows for algorithms in the Adjacency List (AL) streaming model whose number of passes is constant and memory is $O(logn)$ for any fixed $k$. On the negative end, many other parameters lead to lower bounds in the AL model, where $\mathrm{\Omega }(n/p)$ bits of memory is needed for any $p$-pass algorithm even for constant parameter values. In particular, this holds for graphs with a known modulator (deletion set) of constant size to a graph that has no induced subgraph isomorphic to a fixed graph $H$, for most $H$. Open problems for our work include solving Diameter for specific $H$-free graphs, and for interval graphs in the AL model. Another interesting open problem relevant to this work is whether there is a streaming algorithm for Vertex Cover $[k]$ using $O(\text{poly}(k))$ passes and $O(\text{poly}(k,logn))$ bits of memory.

We proposed a framework for the complexity classification of problems that satisfy the following three conditions:

1. 1.

   they are efficiently computable on graph classes of bounded treewidth

2. 2.

   they are computationally hard on the class of subcubic graphs

3. 3.

   they remain computationally hard on subdivisions of subcubic graphs

We call the problems that satisfy all three conditions C123-problems. This talk discusses the complexity of problems that satisfy the first condition but violate the second on graph classes excluding certain subdivided stars as subgraphs. A few notable examples of these problems are feedback vertex set, independent feedback vertex set, and colouring. In particular, we show that certain classes of connected, $H$-subgraph-free graphs that are not subcubic must have bounded treewidth. We show this for the cases when $H=S_{1,1,1,r}$ and $H=S_{1,1,q,r}$. The immediate consequence of these theorems is that the problems under consideration are polynomial-time solvable on the aforementioned graph classes. We also discuss the NP-completeness of Feedback Vertex Set and Independent Feedback Vertex Set on $S_{2,2,2,2}$-subgraph-free graphs, leaving $S_{1,p,q,r}$-subgraph-free graphs as the only open case remaining.

In this tutorial talk I presented the framework of potential maximal cliques, with emphasis on recent attempts to relax the requirements for the enumerated family of “approximate” potential maximal cliques to containers and carvers. This enables solving a large family of problems in six-vertex-path-free graphs in polynomial time

We prove that if a graph $G$ excludes a path, complement of a path, and a threshold graph, all as induced subgraphs, then $G$ can be colored with a bounded number of colors so that every color induces a cograph. This statement, together with its depth-$2$ generalization that concerns pairs of colors, can be used to prove a conjecture about the characterization of graph classes of bounded shrubdepth through forbidden First-Order transductions. At the end we will discuss variants of this conjecture for linear cliquewidth and cliquewidth, which remain open.

A classic result of Alekseev asserts that for connected $H$ the Max Independent Set (MIS) problem in $H$-free graphs is NP-hard unless $H$ is a path or a subdivided claw. Recently we have witnessed some great progress in understanding the complexity of MIS in $P_t$-free graphs. The situation for forbidden subdivided claws is, however, much less understood.

During the talk we will present some recent advances in understanding the structure of graphs with no long induced claws, and their applications in designing algorithms for MIS and related problems.

A graph $G$ is “$H$-free” if no induced subgraph is isomorphic to $H$. In 1977, Erdős and Hajnal made the conjecture that, for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ has a clique or stable set of size at least ${|G|}^c$; and they proved that this is true with ${|G|}^c$ replaced by $2^{c\sqrt{\log |G|}}$. Until now, there has no improvement on this result (for general $H$).

In joint work with M. Bucić, T. Nguyen, A. Scott, we recently proved a strengthening: that for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ with $|G|\ge 2$ has a clique or stable set of size at least

Indeed, we prove the corresponding strengthening of a theorem of Fox and Sudakov, which in turn was a common strengthening of theorems of Rödl, Nikiforov, and the theorem of Erdős and Hajnal mentioned above.

In this talk, we survey this material, and a number of other results related to the Erdős-Hajnal conjecture, for instance:

• $\mathrm{■}$

  it holds when $H$ is the five-vertex cycle (a recent result joint with M. Chudnovsky, A. Scott and S. Spirkl);

• $\mathrm{■}$

  it “almost” holds when $H$ is the five-vertex path $P_5$ (Blanco and Bucić recently proved that every $P_5$-free graph $G$ has a clique or stable set of size at least $2^{c{(\log |G|)}^{2/3}}$);

• $\mathrm{■}$

  it almost holds in another sense when $H=P_5$; Chudnovsky, Scott and the speaker proved that every $P_5$-free graph $G$ has chromatic number at most $k^{\log k}$, where $k$ is the clique number of $G$.

We present a framework to classify the complexity of certain problems on $H$-subgraph-free graph classes. A graph problem $\mathrm{\Pi }$ a C123-problem if it satisfies the following three conditions:

C1.

$\mathrm{\Pi }$ is efficiently solvable for every graph class of bounded treewidth;

C2.

$\mathrm{\Pi }$ is computationally hard for the class of subcubic graphs; and

C3.

$\mathrm{\Pi }$ is computationally hard under edge subdivision of subcubic graphs.

In this talk we give a meta-theorem classifying the complexity of problems satisfying these conditions. We then discuss the limits of this framework together with a number of open problems.

In this talk, we consider the complexity of Steiner Forest on graphs that exclude a fixed graph $H$ as a subgraph. Recently, a framework was proposed to classify the complexity of problems on $H$-subgraph-free graphs (see [1] as well as the talk in this seminar). Unfortunately, Steiner Forest does not fit this framework. In this talk, we discuss why this is the case as well as our progress on obtaining a separate classification for Steiner Forest.

Let $t$ be an integer. A graph is clean if it does not contain any of the following as an induced subgraph.

• $\mathrm{■}$

  the complete graph on $t$ vertices

• $\mathrm{■}$

  the complete bipartite graph $K_{t,t}$

• $\mathrm{■}$

  a subdivision of the $t\times t$-wall

• $\mathrm{■}$

  the line graph of a subdivision of a $t\times t$ wall.

Is the following true: for every integer $t$ there exists an integer $c(t)$ such that every $t$-clean $n$-vertex graph with maximum degree at most $\log n$ has treewidth at most $c(t)\log n$?

Only very few parameterized complexity results for Coloring on H-free graphs are known (see [1] for the survey) and some of the open problems seem to be highly nontrivial. In particular, the following problem, which was first stated by Hoáng et al. in [2], remains open for a long time despite all efforts. Hoáng et al. proved in [2] that $k$-Coloring can be solved in polynomial time on $P_5$-free graphs for every positive integer $k$, that is the problem is in XP when parameterized by $k$. This leads to the question whether $k$-Coloring is FPT on $P_5$-free graphs when parameterized by $k$. The question about complexity of $k$-Coloring is also open and interesting for $2K_2$-free graphs that compose a proper subclass of $P_5$-free graphs.