Solving Problems on Graphs: From Structure to Algorithms

The sphere dimension of a graph $G$ is the smallest integer $d\ge 2$ so that $G$ is an intersection graph of metric spheres in ${ℝ}^d$. This talk considers the class ${𝒞}^d$ of graphs with sphere dimension $d$. We present the results that for each integer $t$, the class of all graphs in ${𝒞}^d$ that exclude $K_{t,t}$ as a subgraph has strongly sublinear separators and that ${𝒞}^d$ has asymptotic dimension at most $2d+2$.

For graphs $G$ and $H$, an $H$-coloring of $G$ is an edge-preserving mapping from $V(G)$ to $V(H)$. Note that if $H$ is the triangle, then $H$-colorings are equivalent to $3$-colorings. In this paper we are interested in the case that $H$ is the five-vertex cycle $C_5$.

A minimal obstruction to $C_5$-coloring is a graph that does not have a $C_5$-coloring, but every proper induced subgraph thereof has a $C_5$-coloring. In this paper we are interested in minimal obstructions to $C_5$-coloring in $F$-free graphs, i.e., graphs that exclude some fixed graph $F$ as an induced subgraph. Let $P_t$ denote the path on $t$ vertices, and let $S_{a,b,c}$ denote the graph obtained from paths $P_{a+1},P_{b+1},P_{c+1}$ by identifying one of their endvertices.

We show that there is only a finite number of minimal obstructions to $C_5$-coloring among $F$-free graphs, where $F\in \{P_8,S_{2,2,1},S_{3,1,1}\}$ and explicitly determine all such obstructions. This extends the results of Kamiński and Pstrucha [1] who proved that there is only a finite number of $P_7$-free minimal obstructions to $C_5$-coloring, and of Dębski et al. [2] who showed that the triangle is the unique $S_{2,1,1}$-free minimal obstruction to $C_5$-coloring.

We complement our results with a construction of an infinite family of minimal obstructions to $C_5$-coloring, which are simultaneously $P_{13}$-free and $S_{2,2,2}$-free. We also discuss infinite families of $F$-free minimal obstructions to $H$-coloring for other graphs $H$.

The theory of induced minors of graphs aims to generalize the theory of graph minors to dense graph classes. This dates back to the end of the 80s and the start of the 90s, when several negative results in this direction were proven. However, in the recent years there has been a resurgence of interest into induced minors, and some positive results and interesting conjectures have been discovered. In this talk I survey the theory of induced minors and the most interesting open problems in this area, focusing mostly on the algorithmic perspective.

The talk surveys some recent work on parameterized algorithms for graph problems relative to structural parameters: (1) Efficient parameterized algorithms that obtain in polynomial time a approximate solution with additive error depending on a chosen graph parameter. (2) Key ideas behind the recent tight bound for Steiner Tree parameterized by clique-width. (3) Tight bounds relative to multi-clique-width.

Our first main results are a P versus NP-complete classification of CSPs when the input is restricted to $ℱ$-homomorphism-free digraphs, or restricted to CSP($H^{\prime }$) for some finite digraph $H^{\prime }$. We then use the established connection to constraint satisfaction theory to show our third main result (and partial answer to the question above): if CSP($H$) is NP-complete, then there is a positive integer $N$ such that CSP($H$) remains NP-hard even for $D{P}_N$-(subgraph)-free digraphs. Moreover, CSP($H$) remains NP-hard for $D{P}_N$-(subgraph)-free acyclic digraphs, and becomes polynomial-time solvable for $D{P}_{N-1}$-(subgraph)-free acyclic digraphs.

Another contribution of this work is verifying the question above for digraphs on three vertices and a family of smooth tournaments.

The intensively studied Diameter problem is to find the diameter of a given connected graph. We investigate, for the first time in a structured manner, the complexity of Diameter for $H$-free graphs, that is, graphs that do not contain a fixed graph $H$ as an induced subgraph. We first show that if $H$ is not a linear forest with small components, then Diameter cannot be solved in subquadratic time for $H$-free graphs under SETH. For some small linear forests, we do show linear-time algorithms for solving Diameter. For other linear forests $H$, we make progress towards linear-time algorithms by considering specific diameter values. If $H$ is a linear forest, the maximum value of the diameter of any graph in a connected $H$-free graph class is some constant $d_{\max }$ dependent only on $H$. We give linear-time algorithms for deciding if a connected $H$-free graph has diameter $d_{\max }$, for several linear forests $H$. In contrast, for one such linear forest $H$, Diameter cannot be solved in subquadratic time for $H$-free graphs under SETH. Moreover, we even show that, for several other linear forests $H$, one cannot decide in subquadratic time if a connected $H$-free graph has diameter $d_{\max }$ under SETH.

The classic greedy coloring algorithm considers the vertices of an input graph G in a given order and assigns the first available color to each vertex v in G. In the Grundy Coloring problem, the task is to find an ordering of the vertices that will force the greedy algorithm to use as many colors as possible. In the Partial Grundy Coloring, the task is also to color the graph using as many colors as possible. This time, however, we may select both the ordering in which the vertices are considered and which color to assign the vertex. The only constraint is that the color assigned to a vertex v is a color previously used for another vertex if such a color is available. Aboulker et al. [1] proved that Grundy Coloring is W[1]-hard. In this talk, we prove that Partial Grundy Coloring is fixed-parameter tractable.

In a directed graph $D$ with sources $S$ and sinks $T$, a tripod is the union of a pair of $S-T$ paths that have different sources but the same sink. We prove that tripods in directed graphs have the Erdős-Pósa property. The key element in the proof is the use of the Matroid Intersection Theorem. We will also mention open problems about possible generalizations and related algorithmic problems.

In this talk we report a successful resolution of an open problem from the previous edition (Dagstuhl Seminar 22481) of this seminar.

At Dagstuhl Seminar 22481, Michal Pilipczuk asked whether one can find a maximum 2-colorable induced subgraph on $P_5$-free graphs in polynomial time or even in quasi-polynomial time.

We [Agrawal, Lima, Lokshtanov, Saurabh, Sharma] designed a quasi-polynomial time algorithm for the problem, which appeared at SODA 2024 [1]. Later together with Rzążewski, we improved the running time to polynomial for the same problem. This work will appear at ACM TALG 2025.

In a follow-up work [2], we [Lokshtanov, Rzążewski, Saurabh, Sharma, Zehavi] show that one can also design a polynomial time algorithm on $P_5$-free graphs for an even more general problem: the Maximum $k$-Colorable Induced Subgraph problem, for any fixed positive integer k. This can be further generalised to the Maximum Weight Partial List H-Coloring problem.

Layered wheels are constructions of graphs first discovered by Ni Luh Dewi Sintiari and the speaker. They disprove several conjectures and answer several questions. For instance, jointly with Maria Chudnovsky, the speaker could use them to disprove a conjecture de Dallard, Milanič and Štorgel about the tree-independence number and a conjecture of Hajebi about the induced subgraphs contained in graphs of high treewidth. The goal of the talk is to present all the situations where layered wheels turned out to be useful and to present in more detail the variant that disproved the two conjectures mentioned above.

I will talk about vertex-deletion problems that become harder when the vertices are weighted. This is because we do not know a weighted counterpart of the technique known as “protrusion replacement”. I will talk about a recent work on approximation for Weighted Treewidth-$\eta$ Deletion which circumvents this issue. Then I will move on to some open problems related to weighted graphs and protrusions.

For every positive integer $t$ there exists an integer $c_t$ with the following property. Let $G$ be a graph with no complete subgraph of size $t$, and no induced minor isomorphic to $K_{t,t}$ is the $txt$ wall. Then the treewidth of $G$ is bounded from above by $c_t{\log }^{c_t}|V(G)|$.

A clique cut-set in a connected graph is a clique whose deletion results in a disconnected graph. A graph is an atom if it has no clique cut-set. A simplicial vertex is one whose neighbourhood is a clique. If an atom is not a complete graph, then it cannot contain any simplicial vertices.

For a hereditary graph class $𝒢$, we denote its set of connected graphs by ${𝒢}^c$, its set of atoms by ${𝒢}_a^c$, and its set of connected graphs that are either an atom or else have no simplicial vertices by ${𝒢}_s^c$. Equivalently, ${𝒢}_s^c$ consists of all connected graphs that are either complete or have no simplicial vertices. Note that ${𝒢}_a^c\subseteq {𝒢}_s^c\subseteq {𝒢}^c$. A hereditary graph class $𝒢$ will have ${𝒢}_a^c\ne {𝒢}_s^c$ if and only if $G$ contains at least one graph from one of 27 infinite families of minimal graphs that have no simplicial vertices, but are not atoms. Roughly speaking, the graphs in these families consist of exactly two holes, which are linked together by a clique cut-set that has size at most $4$ and that may contain some vertices of the two holes.

There are many computational problems that are polynomial-time solvable on a hereditary graph class $𝒢$ whenever they are polynomial-time solvable on the atoms in ${𝒢}_a^c$. If we replace ${𝒢}_a^c$ with ${𝒢}_s^c$ in the previous sentence, does the statement apply to a strictly wider range of computational problems?

More formally, does there exist a natural graph problem $\mathrm{\Pi }$, for which the following holds:

1. 1.

   for every hereditary graph class $𝒢$, the problem $\mathrm{\Pi }$ is polynomial-time solvable on $𝒢$ if and only if it is polynomial-time solvable on ${𝒢}_s^c$, and

2. 2.

   there exists a hereditary graph class $ℱ$ such that $\mathrm{\Pi }$ is NP-hard on $ℱ$, but polynomial-time solvable on ${ℱ}_a^c$.

Given as input two positive integers $n$ and $k$, compute the number of graphs with vertex set $\{1,\mathrm{\dots },n\}$ and at least one vertex cover of size at most $k$. The naive algorithm does this in time $2^{n^2}$. Does there exist an algorithm with running time $2^{o(n^2)}$?

The task of the classical Longest Cycle problem is, given a graph $G$ and a positive integer $k$, to decide whether $G$ has a cycle of length at least $k$. This problem generalizes Hamiltonian Cycle and is well-known to be NP-complete. From the positive side, Longest Cycle is known to be FPT when parameterized by $k$, and there is a long history of research focused on developing various algorithmic tools for the problem. On the other hand, various lower bounds on the circumference of a graph, i.e., the length of the longest cycle, are well-known in Extremal Combinatorics. This raises the question of whether it is possible to combine the strengths of both areas. Recently [4, 5], Longest Cycle was investigated for the parameterization above the classical circumference lower bounds of Dirac [2] and Erdős and Gallai [3], respectively. These results are obtained for undirected graphs and the area of directed graphs is completely unexplored. This leads to a plethora of open problems. For example, any directed graph of minimum in-degree ${\delta }^{+}(G)\ge 1$ has a cycle of length at least ${\delta }^{+}(G)+1$. Is it possible to find a cycle of length ${\delta }^{+}(G)+k$ in FPT in $k$ time on (2-strong) digraphs? More generally, we ask whether it is possible to obtain interesting and nontrivial parameterized algorithms for Longest Cycle on directed graphs above combinatorial bounds and refer to the survey of Bermond and Thomassen [1] for the circumference bounds.

When a $k$-expression witnessing that a graph has clique-width at most $k$ is given, many NP-hard graph problems can be solved in time $2^{O(k)}{n}^{O(1)}$. Can we obtain such algorithms parameterized by clique-width without the assumption that a $k$-expression is given as an input? Oum, Sæther, and Vatshelle gave $2^{O(k\log k)}{n}^{O(1)}$ time algorithms in [1].

Let $H_i$ be the graph obtained from two copies of $P_3$ with a path of length $i$ joining the central vertices. For $k$, fixed, the $k$-Induced Disjoint Paths problem takes as input a graph with $k$ terminal pairs $(s_1,t_1)$, …, $(s_k,t_k)$ and asks if there are vertex-disjoint paths connecting the terminal pairs such that there are no edges between these paths.

It is known that $k$-Induced Disjoint Paths is in P for $H_1$-subgraph-free graphs and for $H_2$-subgraph-free graphs. Furthermore, it is NP-complete for $H_i$-subgraph-free graphs for all $i\ge 4$ [1]. What is the complexity in the $H_3$-subgraph-free case?

$(k,\varphi )$-Maximum Weight Induced Subgraph is a meta-problem that asks for a maximum-weight induced subgraph of treewidth at most $k$ that models an CMSO2 formula $\varphi$; this problem captures Maximum Independent Set and Feedback Vertex Set, among others. It is known to be solvable in quasi-polynomial time in $P_t$-free graphs [2] and we conjecture it is actually polynomial-time solvable in these graph classes; the conjecture is confirmed up to $t=6$ [1].

A recent manuscript [3] established this conjecture in $P_7$-free graphs of bounded clique number. Somewhat surprisingly, the case of $P_7$-free bipartite graphs turned out to be an important subcase.

This motivates the following question: can we establish polynomial-time solvability of $(k,\varphi )$-Maximum Weight Induced Subgraph in $P_t$-free bipartite graphs? A special case of Feedback Vertex Set is already very interesting. (Note that Maximum Independent Set is polynomial-time solvable in bipartite graphs thanks to the maximum matching techniques.)

For some fixed graph $H$, one may wonder whether detecting $H$ as an induced minor can be done in polynomial time. For some $H$’s, the problem is known to be polytime solvable, for others it is known to be NP-complete, so that a dichotomy theorem would be good, and this is a well-known open question that is widely open. A direction might therefore be to find graph some graphs $H$ that are likely to give insight on the general goal. I propose $H=K_t\setminus e$, that is the graph obtained from the complete graph on $t$ vertices by removing one edge.

These are very “close” to be polytime to detect because $K_t$ is. Indeed, containing $K_t$ as an induced minor is equivalent to containing it as a minor. So, to detect $K_t$, one may rely on the classical Robertson and Seymour algorithm to detect a minor. Having $H=K_t\setminus e$ being NP-complete would therefore be striking, but not unlikely since adding a non-edge constraint is really demanding a lot. On the other hand, it might be polytime by some clever reduction to detect a minor, or by a structure theorem for $K_t\setminus e$-induced-minor-free graphs, or by some other mean.