New Tools in Parameterized Complexity: Paths, Cuts, and Decomposition

Parameterized Complexity is an alternative approach of handling computational intractability. The main idea of the approach taken by the Parameterized Complexity is to analyze the complexity in finer detail by considering additional problem parameters beyond the input size and expresses the efficiency of the algorithms in terms of these parameters. In this framework, many NP-hard problems have been shown to be (fixed-parameter) tractable (FPT) when certain structural parameters of the inputs are bounded.

In the last three decades, there has been tremendous progress in understanding which problems are fixed-parameter tractable and which problems are not (under standard complexity assumptions). For all these years the central vision of the Parameterized Complexity has been to provide the algorithmic and complexity-theoretic toolkit for studying multivariate algorithmics in different disciplines and subfields of Computer Science. To achieve this vision several algorithmic and complexity theoretic tools such as polynomial time preprocessing, aka, kernelization, color-coding, graph-decompositions, parameterized integer programming, iterative compression, or lower bounds methods based on assumptions stronger than P$\ne$NP have been developed. These tools are universal as they not only helped in the development of the core of Parameterized Complexity but also led to its success in other subfields of Computer Science such as Approximation Algorithms, Computational Social Choice, Computational Geometry, problems solvable in P (polynomial time) to name a few.

In the last few years several decade old open problems in Parameterized Complexity have been resolved. These have resulted in several new algorithmic tools for the core of Parameterized Complexity. These include tools such as iterative and local improvement methods for graph decomposition, methods arising from extremal combinatorics and graph theory, flow augmentation, faster algorithms for solving integer programs on $n$ variables, and new algebraic methods. A natural question is to extend these tools in different directions and explore the limits and applicability of these new tools. Thus,

the main objective of the Dagstuhl Seminar was to initiate the discussion on extension, limits and applicability of newly developed tools arising from paths, cuts, and decomposition.

One of the seminar’s central goals was to facilitate a fruitful dialogue between researchers working at the core of Parameterized Complexity and those from Mathematical Programming, Computational Linear Algebra, Graph Theory, and Combinatorics, who had contributed to recent advances in parameterized algorithms. The Dagstuhl event enabled participants to explore possibilities for developing new tools and techniques that emerged from this collaboration.

Next, the seminar presented a few concrete examples of newly developed tools and techniques from various domains of Parameterized Complexity, which formed the focal points of discussion.

• $\mathrm{■}$

  Width Parameters: Treewidth and Twinwidth.

• $\mathrm{■}$

  Tools Based on Extremal Combinatorics: Paths and Rainbow Matching.

• $\mathrm{■}$

  Cut Based Tool: Flow Augmentation.

• $\mathrm{■}$

  Mathematical Programming.

• $\mathrm{■}$

  Algebraic Methods.

This Dagstuhl Seminar could be considered as a continuation of the Dagstuhl Seminar series on parameterized algorithms and complexity. The previous seminars in this series are New Horizons in Parameterized Complexity (seminar 19041), Randomization in Parameterized Complexity (seminar 17041), Optimality and Tight Results in Parameterized Complexity (seminar 14451), Data Reduction and Problem Kernels (seminar 12241), Parameterized complexity and approximation algorithms (seminar 09511), Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs (seminar 07281), Exact Algorithms and Fixed-Parameter Tractability (seminar 05301), Fixed Parameter Algorithms (seminar 03311), and Parameterized Complexity (seminar 01311).

During the five-day seminar, 48 researchers from theoretical computer science, mathematical optimization, and operations research convened. Attendees ranged from senior scientists to postdoctoral scholars and advanced doctoral candidates, creating a rich environment for both mentorship and innovation.

The seminar featured 22 presentations of varying lengths. Six keynote speakers–Dániel Marx, Michał Pilipczuk, Euiwoong Lee, Tuukka Korhonen, Jie Xue, and Daniel Lokshtanov–delivered 60-minute talks that provided overviews of state-of-the-art methods and showcased recent breakthroughs in their respective areas. The remaining slots were filled with shorter, 30-minute talks covering various topics.

At the beginning of the week, open problem sessions encouraged participants to share challenges and spark collaborative research. The schedule also included ample free time, which attendees used for productive discussions and joint work, fostering new ideas and potential research partnerships.

Organizers and participants regarded the seminar as a great success. It successfully brought together the relevant research communities, facilitated the sharing of state-of-the-art results, and enabled discussions on the major challenges in the field. The talks were not only excellent but also highly stimulating, prompting active engagement in working groups during afternoons and evenings. Particularly noteworthy was the participation of younger researchers (postdocs and PhD students), who integrated seamlessly and contributed to the seminar’s collegial and productive atmosphere.

We study polynomial-time approximation algorithms for (edge/vertex) Sparsest Cut and Small Set Expansion in terms of $k$, the number of edges or vertices cut in the optimal solution. Our main results are $O(poly\log k)$-approximation algorithms for various versions in this setting.

Our techniques involve an extension of the notion of sample sets (Feige and Mahdian STOC’06), originally developed for small balanced cuts, to sparse cuts in general. We then show how to combine this notion of sample sets with two algorithms, one based on an existing framework of LP rounding and another new algorithm based on the cut-matching game, to get such approximation algorithms. Our cut-matching game algorithm can be viewed as a local version of the cut-matching game by Khandekar, Khot, Orecchia and Vishnoi and certifies an expansion of every vertex set of size s in $O(\log s)$ rounds. These techniques may be of independent interest.

As corollaries of our results, we also obtain an O(logopt)-approximation for min-max graph partitioning, where opt is the min-max value of the optimal cut, and improve the bound on the size of multicut mimicking networks computable in polynomial time.

Unbreakable decomposition, introduced by Cygan et al. (SICOMP’19) and Cygan et al. (TALG’20), has proven to be one of the most powerful tools for parameterized graph cut problems in recent years. Unfortunately, all known constructions require at least ${\mathrm{\Omega }}_k(m{n}^2)$ time, given an undirected graph with $n$ vertices, $m$ edges, and cut-size parameter $k$. In this work, we show the first close-to-linear time parameterized algorithm that computes an unbreakable decomposition. More precisely, for any , our algorithm runs in time $2^{O(\frac{k}{ϵ}\log (k/ϵ))}{m}^{1+ϵ}$ and computes a $(O(k/ϵ),k)$ unbreakable tree decomposition of the input graph, where each bag has adhesion at most $O(k/ϵ)$. This immediately opens up possibilities for obtaining close-to-linear time algorithms for numerous problems whose only known solution is based on unbreakable decomposition.

In the Min-Sum Disjoint Paths problem, we are given an edge-weighted n-vertex graph and k terminal pairs. The task is to connect all terminal pairs by pairwise internally vertex-disjoint paths of minimum total length (or decide that there is no set of pairwise disjoint paths). We show that Min-Sum Disjoint Paths on (directed or undirected) planar input graphs can be solved in $2^{O(\sqrt{\mathrm{\ell }}{\log }^{O(1)}(\mathrm{\ell }))}{n}^{O(1)}$ time, where $\mathrm{\ell }$ is the number of edges in an optimal solution. We complement our main result with an ETH-based lower bound excluding $2^{o(\sqrt{n})}$-time algorithms for undirected and unweighted planar graphs even in the special case where we ask whether all terminal pairs can be connected by shortest paths between the respective endpoints.

We survey some algorithmic applications of twin-width.

The $k$-Steiner-2NCS problem is as follows: Given a constant $k$, and an undirected connected graph $G=(V,E)$, non-negative costs $c$ on the edges, and a partition of $V$ into a set of terminals, $T$, and a set of non-terminals (or, Steiner nodes), $V-T$, where $|T|=k$, our algorithmic goal is to find a min-cost two-node connected subgraph that contains the terminals.

We present a randomized polynomial-time algorithm for the unweighted problem, and a randomized FPTAS for the weighted problem.

We obtain similar results for the $k$-Steiner-2ECS problem, where the input is the same, and the algorithmic goal is to find a min-cost two-edge connected subgraph that contains the terminals.

Our methods build on results by Bjorklund, Husfeldt, and Taslaman (SODA 2012) that give a randomized polynomial-time algorithm for the unweighted $k$-Steiner-cycle problem; this problem has the same inputs as the unweighted $k$-Steiner-2NCS problem, and the algorithmic goal is to find a min-cost simple cycle that contains the terminals.

Minimum cut and multicut problems for general graphs are well-studied. In this talk, we survey algorithms and lower bounds for these problems when restricting to graphs that are either planar or embeddable on a fixed surface. For such classes of graphs, topological techniques, developed originally in computational geometry/topology with very different motivations in mind, turn out to be very useful.

We first aim to provide an executive summary of the computational topology routines that are the most useful for cut problems for surface-embedded graphs. We then discuss near-linear time algorithms for minimum cut on a fixed surface, which outperform the existing generic (polynomial-time) combinatorial algorithms. We then turn to the multicut problem, presenting an algorithm that is fixed-parameter tractable parameterized by the genus and the number of terminals, and an almost matching lower bound. There is actually a refined complexity analysis depending also on the demand pattern. Finally, we present an algorithm for the multicut problem that returns an $(1+\epsilon )$-approximation and that is fixed parameter tractable in the genus, the number of terminals, and $\epsilon$.

All these results rely on topological methods: The subgraph of the dual of the input graph, made of the edges dual to a multicut, has nice properties, which can be exploited using classical tools from algebraic topology such as homotopy, homology, and covering spaces.

We give two new approximation algorithms to compute the fractional hypertree width of an input hypergraph. The first algorithm takes as input $n$-vertex $m$-edge hypergraph $H$ of fractional hypertree width at most $\omega$, runs in polynomial time and produces a tree decomposition of $H$ of fractional hypertree width $𝒪(\omega \log n\log \omega )$, i.e., it is an $𝒪(\log n\log \omega )$-approximation algorithm. As an immediate corollary this yields polynomial time $𝒪({\log }^{2}n\log \omega )$-approximation algorithms for (generalized) hypertree width as well. To the best of our knowledge our algorithm is the first non-trivial polynomial-time approximation algorithm for fractional hypertree width and (generalized) hypertree width, as opposed to algorithms that run in polynomial time only when $\omega$ is considered a constant. For hypergraphs with the bounded intersection property (i.e. hypergraphs where every pair of hyperedges have at most $\eta$ vertices in common) the algorithm outputs a hypertree decomposition with fractional hypertree width $𝒪(\eta {\omega }^2\log \omega )$ and generalized hypertree width $𝒪(\eta {\omega }^2\log \omega (\log \eta +\log \omega ))$. This ratio is comparable with the recent algorithm of Lanzinger and Razgon [STACS 2024], which produces a hypertree decomposition with generalized hypertree width $𝒪({\omega }^2(\omega +\eta ))$, but uses time (at least) exponential in $\eta$ and $\omega$.

The second algorithm runs in time $n^{\omega }{m}^{𝒪(1)}$ and produces a tree decomposition of $H$ of fractional hypertree width $𝒪(\omega {\log }^2\omega )$. This significantly improves over the ${(n+m)}^{𝒪({\omega }^3)}$ time algorithm of Marx [ACM TALG 2010], which produces a tree decomposition of fractional hypertree width $𝒪({\omega }^3)$, both in terms of running time and the approximation ratio.

Our main technical contribution, and the key insight behind both algorithms, is a variant of the classic Menger’s Theorem for clique separators in graphs: For every graph $G$, vertex sets $A$ and $B$, family $ℱ$ of cliques in $G$, and positive rational $f$, either there exists a sub-family of $𝒪(f\cdot {\log }^{2}n)$ cliques in $ℱ$ whose union separates $A$ from $B$, or there exist $f\cdot \log |ℱ|$ paths from $A$ to $B$ such that no clique in $ℱ$ intersects more than $\log |ℱ|$ paths.

Twin-width is a relatively new notion introduced in 2020 by Bonnet, Kim, Thomassé and Watrigant. Since then, it is prove to demonstrate rich structure and be a useful tool for understanding graph classes and logic, designing algorithms, etc. In this talk, we present the notion, grid theorem for twin-width and how to use it for proving certain graph classes have bounded twin-width as well as other use cases of twin-width.

In the Steiner Tree problem we are given an undirected edge-weighted graph as input, along with a set $K$ of vertices called terminals. The task is to output a minimum-weight connected subgraph that spans all the terminals. The famous Dreyfus-Wagner algorithm running in $3^{|K|}\mathrm{𝗉𝗈𝗅𝗒}(n)$ time shows that the problem is fixed-parameter tractable parameterized by the number of terminals. We present fixed-parameter tractable algorithms for Steiner Tree using structurally smaller parameterizations.

Our first result concerns the parameterization by a multiway cut $S$ of the terminals, which is a vertex set $S$ (possibly containing terminals) such that each connected component of $G-S$ contains at most one terminal. We show that Steiner Tree can be solved in $2^{O(|S|\log |S|)}\mathrm{𝗉𝗈𝗅𝗒}(n)$ time and polynomial space, where $S$ is a minimum multiway cut for $K$. The algorithm is based on the insight that, after guessing how an optimal Steiner tree interacts with a multiway cut $S$, computing a minimum-cost solution of this type can be formulated as minimum-cost bipartite matching.

Our second result concerns a new hybrid parameterization called $K$-free treewidth that simultaneously refines the number of terminals $|K|$ and the treewidth of the input graph. By utilizing recent work on $\mathscr{H}$-Treewidth in order to find a corresponding decomposition of the graph, we give an algorithm that solves Steiner Tree in time $2^{O(k)}\mathrm{𝗉𝗈𝗅𝗒}(n)$, where $k$ denotes the $K$-free treewidth of the input graph. To obtain this running time, we show how the rank-based approach for solving Steiner Tree parameterized by treewidth can be extended to work in the setting of $K$-free treewidth, by exploiting existing algorithms parameterized by $|K|$ to compute the table entries of leaf bags of a tree $K$-free decomposition.

In a classical scheduling problem, we are given a set of $n$ jobs of unit length with precedence constraints, and the goal is to find a schedule of these jobs on $m$ identical machines that minimizes the makespan. In standard 3-field notation, it is denoted as $Pm|\text{prec},p_j=1|C_{\max }$.

For $m=2$ machines, the problem can be solved in polynomial time. Settling the complexity for any constant $m\ge 3$ is a longstanding open question in the field, asked by Lenstra and Rinnooy Kan [OR 1978] in the late 70s and prominently featured in the textbook of Garey and Johnson. Since then, the problem has been thoroughly investigated, but nontrivial solutions had been found only in special cases or relaxed settings. For example, despite the possibility of the problem being polynomially solvable in the exact setting, just the existence of an approximation-scheme is widely regarded as a major open problem (see the survey of Bansal [MAPS 2017]), but so far, only superpolynomial approximations are known.

In this paper, we make the first progress on the exact complexity of $Pm|\text{prec},p_j=1|C_{\max }$. We present an algorithm that runs in $2^{O(\sqrt{n}\log n)}$ time for $m=O(1)$. Before our work, only a $2^{O(n)}$ time exact algorithm was known by Held and Karp [ACM 1961].

A strength of parameterized algorithmics is that each problem can be parameterized by an essentially inexhaustible set of parameters. Usually, the choice of the considered parameter is informed by the theoretical relations between parameters with the general goal of achieving FPT-algorithms for smaller and smaller parameters. However, the FPT-algorithms for smaller parameters usually have higher running times and it is not clear whether the decrease in the parameter value or the increase in the running time bound dominates in real-world data. Any answer to this question requires knowledge on typical parameter values. To provide a data-driven guideline for parameterized complexity studies of graph problems, we present the first comprehensive comparison of parameter values for a set of benchmark graphs originating from real-world applications. Our study covers degree-related parameters, such as maximum degree or degeneracy, neighborhood-based parameters such as neighborhood diversity and modular-width, modulator-based parameters such as vertex cover number and feedback vertex set number, and the treewidth of the graphs. Our implementation and full experimental data are openly available.

We present $k^{O(k^2)}m$ time algorithms for various problems about decomposing a given graph by edge cuts or vertex separators of size less than $k$ into parts that are “well-connected” with respect to cuts or separators of size less than $k$; here, $m$ is the total number of vertices and edges of the graph. As an application of our results, we obtain for every fixed $k$ a linear-time algorithm for computing the $k$-edge-connected components of a given graph, solving a long-standing open problem. More generally, we obtain a $k^{O(k^2)}m$ time algorithm for computing a $k$-Gomory-Hu tree of a given graph, which is a structure representing all pairwise minimum cuts of size less than $k$.

Our main technical result, from which the other results follow, is a $k^{O(k^2)}m$ time algorithm for computing a $k$-lean tree decomposition of a given graph. This is a tree decomposition with adhesion size less than $k$ that captures the existence of separators of size less than $k$ between subsets of its bags. A $k$-lean tree decomposition is also an unbreakable tree decomposition with optimal unbreakability parameters for the adhesion size bound $k$.

As further applications, we obtain $k^{O(k^2)}m$ time algorithms for $k$-vertex connectivity and for $k$-Gomory-Hu tree for element connectivity. All of our algorithms are deterministic.

Our techniques are inspired by the tenth paper of the Graph Minors series of Robertson and Seymour and by Bodlaender’s parameterized linear-time algorithm for computing treewidth.

The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the number of variables, from one where every assignment fails to satisfy an $\epsilon$ fraction of constraints for some absolute constant $\epsilon >0$. PIH plays the role of the PCP theorem in parameterized complexity. However, PIH has only been established under Gap-ETH, a very strong assumption with an inherent gap.

In this work, we prove PIH under the Exponential Time Hypothesis (ETH). This is the first proof of PIH from a gap-free assumption. Our proof is self-contained and elementary. We identify an ETH-hard CSP whose variables take vector values, and constraints are either linear or of a special parallel structure. Both kinds of constraints can be checked with constant soundness via a “parallel PCP of proximity” based on the Walsh-Hadamard code.

Given an undirected graph $G=(V,E)$, the Feedback Vertex Set (FVS) problem asks for a minimum-size subset $S\subseteq V$ such that the subgraph induced by $V\setminus S$ is acyclic. The unweighted Feedback Vertex Set problem is known to admit an EPTAS on planar graphs, whereas the weighted version only has a PTAS. A natural question is whether the problem admits an EPTAS even in the weighted case.

We overview the many different types of cut, path, and decomposition problems in the field of parameterized algorithms and sketch some connections between the different topics.

I give a gentle tutorial on using the minimum isolating cuts for fast graph algorithms, as well as, give a survey of its applications.

The streaming model has been studied from the point of parameterized complexity in the last decade by several researchers. However, the applicability of the streaming model to central problems in parameterized complexity has remained somewhat limited due to simple $\mathrm{\Omega }(n)$-space lower bounds for many problems. In other words, the $k^{O(1)}{(\log n)}^{O(1)}$ space requirement of the parameterized streaming model is too restrictive. This has motivated the study of parameterized semi-streaming algorithms.

In this talk, we will discuss some recent developments in this direction.

In the Disjoint Shortest Paths problem one is given a graph $G$ and a set $T=\{(s{1}_{,}{t}_1),\mathrm{\dots },(s_k,t_k)\}$ of $k$ vertex pairs. The question is whether there exist vertex-disjoint paths $P_1,\mathrm{\dots },P_k$ in $G$ so that each $P_i$ is a shortest path between $s_i$ and $t_i$. While the problem is known to be W[1]-hard in general, we show that it is fixed-parameter tractable on planar graphs with positive edge weights. Specifically, we propose an algorithm for Planar Disjoint Shortest Paths with running time $2^{O(k\log k)}{n}^{O(1)}$. Notably, our parameter dependency is better than state-of-the-art $2^{O(k^2)}$ for the Planar Disjoint Paths problem, where the sought paths are not required to be shortest paths.

In the Capacitated $d$-Hitting Set problem input is a universe $U$ equipped with a capacity function $\mathrm{𝖼𝖺𝗉}:U\to \mathbb{N}$, and a collection $𝒜$ of subsets of $U$, each of size at most $d$. The task is to find a minimum size subset $S$ of $U$ and an assignment $\varphi :𝒜\to S$ such that, for every set $A\in 𝒜$ we have $\varphi (A)\in A$ and for every $x\in U$ we have $|{\varphi }^{-1}(x)|\le \mathrm{𝖼𝖺𝗉}(x)$. When $d=2$ the problem is known under the name Capacitated Vertex Cover. In Weighted Capacitated $d$-Hitting Set each element of $U$ has a positive integer weight and the goal is to find a capacitated hitting set of minimum weight.

In this paper we initiate the study of parameterized (approximation) algorithms for Capacitated $d$-Hitting Set. Capacitated $d$-Hitting Set is a well studied problem and is known to admit a $d$-approximation algorithm and no $(d-ϵ)$-approximation under UGC for any $ϵ>0$. Further, unweighted Capacitated $d$-Hitting Set for $d\ge 3$ is W[1]-hard parameterized by solution size. Our main result is a parameterized approximation algorithm that runs in time ${\left(\frac{k}{ϵ}\right)}^k{2}^{k^{O(kd)}}{(|U|+|𝒜|)}^{O(1)}$ and either concludes that there is no solution of size at most $k$ or outputs a solution $S$ of size at most $4/3\cdot k$ and weight at most $2+ϵ$ times the minimum weight of a solution whose size is at most $k$. We also complement our algorithmic results with hardness results.

As machine learning (ML) models become increasingly complex, interpretability and explainability in ML-based decisions, referred to as eXplainable AI (XAI) has become an important objective. In this talk, we introduce two computational questions that arise in the context of XAI and discuss possible parameterizations.

1. 1.

   Finding a small symbolic ML model that best represents given data.

2. 2.

   Generating a concise explanation for a prediction from an existing symbolic model.

We discuss recent results [1, 2, 3, 4, 5, 6, 7, 8] and examine these questions for various model types, including decision trees (DT), decision sets (DS), decision lists (DL), and binary decision diagrams (BDD), highlighting possible avenues for future research.

A drawing of a graph $G$ is 1-planar (or $1$-plane) if each edge has at most one crossing. We restrict our attention to simple drawings – in particular, the curves representing edges are not allowed to “touch” or cross through vertices which are not their endpoints. A drawing $\alpha$ extends a drawing $\beta$ if $\beta \subseteq \alpha$. The following question was left open in an ICALP paper of Eiben, Ganian, Hamm, Klute and Nöllenburg [3].

Is the following problem $FPT$ w.r.t. $k$?

Given a graph $G$, a vertex subset $X\subseteq V(G)$ of size $k$ and a $1$-planar drawing $\mathscr{H}$ of the graph $H=G-X$, does there exist a $1$-planar drawing of $G$ which extends $\mathscr{H}$?

Essentially, we are given an “almost complete” partial $1$-planar drawing of a graph $G$ and want to extend it to a full drawing, where the parameter tells us how many vertices are still missing from the partial drawing. Note that the statement in the paper is slightly more general as it also allows individual edges to be missing from $H$, but the real difficult/interesting case is the one above.

The problem was shown to be in $XP$ in a follow-up MFCS paper [3], and the edge-deletion version of the problem – i.e., where we parameterize by how many edges are missing – is known to be $FPT$ [2] (by using decomposition techniques). Several follow-ups to the latter result are known by now [4, 5, 1], but the vertex-deletion case has not been cracked so far.