In the d-Clique Packing problem, given a graph G and an integer t, we need to decide whether G contains a set of t pairwise vertex-disjoint cliques of size d each. This generalizes Triangle Packing and it is NP-complete for all d ≥ 3. For each such d, we show how to solve the problem in n^𝒪(k^{d-1}) time where k is the clique-width of the graph (with a k-expression of G given in the input). We complement this by showing that, assuming the Exponential-Time Hypothesis (ETH), there is no algorithm that solves the problem in n^o(k^{d-1}) time for any fixed d ≥ 3, already for the special case of seeking a partition into cliques of size d. Our proof also entails W[1]-hardness of d-Clique Packing (and d-Clique Partitioning) parameterized by clique-width for each d ≥ 3. Our work continues a series of results on ETH-tight bounds for fundamental graph problems started by Fomin et al. (SICOMP 2010+2014) who obtained tight bounds for Max-Cut and Edge Dominating Set.

We investigate the computation of minimum-cost spanning trees satisfying prescribed vertex degree constraints: Given a graph $G$ and a constraint function $D$, we ask for a (minimum-cost) spanning tree $T$ such that for each vertex $v$, $T$ achieves a degree specified by $D(v)$. Specifically, we consider three kinds of constraint functions ordered by their generality -- $D$ may either assign each vertex to a list of admissible degrees, an upper bound on the degrees, or a specific degree. Using a combination of novel techniques and state-of-the-art machinery, we obtain an almost-complete overview of the fine-grained complexity of these problems taking into account the most classical graph parameters of the input graph $G$. In particular, we present SETH-tight upper and lower bounds for these problems when parameterized by the pathwidth and cutwidth, an ETH-tight algorithm parameterized by the cliquewidth, and a nearly SETH-tight algorithm parameterized by treewidth. In order to obtain our upper bound for clique-width, we develop a novel technique of double representation through ``requirement shifting''. Using this technique, we also obtain an ETH-tight single-exponential XP algorithm for the Exact Leaf Spanning Tree problem parameterized by clique-width, which settles the final remaining open case for clique-width from the classical Cut and Count of Cygan et al. [FOCS 2011, TALG 2022]. This shows the versatility of our technique and its potential applicability to other problems as well. Additionally, in order to establish our lower and upper bounds we introduce a number of tools which may be of independent interest, including lazy coloring and ``asymptotic'' SETH-based reductions for structural parameters.

We introduce a new notion of acyclicity representation in labeled graphs, and present three applications thereof. Our main result is an algorithm that, given a graph $G$ and a $k$-clique expression of $G$, in time $O(6^kn^c)$ counts modulo $2$ the number of feedback vertex sets of $G$ of each size. We achieve this through an involved subroutine for merging partial solutions at union nodes in the expression. In the usual way this results in a one-sided error Monte-Carlo algorithm for solving the decision problem in the same time. We complement these by a matching lower bound under the Strong Exponential-Time Hypothesis (SETH). This closes an open question that appeared multiple times in the literature [ESA 23, ICALP 24, IPEC 25]. We also present an algorithm that, given a graph $G$ and a tree decomposition of width $k$ of $G$, in time $O(3^kn^c)$ counts modulo $2$ the number of feedback vertex sets of $G$ of each size. This matches the known SETH-tight bound for the decision version, which was obtained using the celebrated cut-and-count technique [FOCS 11, TALG 22]. Unlike other applications of cut-and-count, which use the isolation lemma to reduce a decision problem to counting solutions modulo $2$, this bound was obtained via counting other objects, leaving the complexity of counting solutions modulo $2$ open. Finally, we present a one-sided error Monte-Carlo algorithm that, given a graph $G$ and a $k$-clique expression of $G$, in time $O(18^kn^c)$ decides the existence of a connected feedback vertex set of size $b$ in $G$. We provide a matching lower bound under SETH.

Cutwidth is a widely studied parameter and it quantifies how well a graph can be decomposed along small edge-cuts. It complements pathwidth, which captures decomposition by small vertex separators, and it is well-known that cutwidth upper-bounds pathwidth. The SETH-tight parameterized complexity of problems on graphs of bounded pathwidth (and treewidth) has been actively studied over the past decade while for cutwidth the complexity of many classical problems remained open. For Hamiltonian Cycle, it is known that a (2+√2)^{pw} n^𝒪(1) algorithm is optimal for pathwidth under SETH [Cygan et al. JACM 2018]. Van Geffen et al. [J. Graph Algorithms Appl. 2020] and Bojikian et al. [STACS 2023] asked which running time is optimal for this problem parameterized by cutwidth. We answer this question with (1+√2)^{ctw} n^𝒪(1) by providing matching upper and lower bounds. Second, as our main technical contribution, we close the gap left by van Heck [2018] for Partition Into Triangles (and Triangle Packing) by improving both upper and lower bound and getting a tight bound of ∛{3}^{ctw} n^𝒪(1), which to our knowledge exhibits the only known tight non-integral basis apart from Hamiltonian Cycle [Cygan et al. JACM 2018] and C₄-Hitting Set [SODA 2025]. We show that the cuts inducing a disjoint union of paths of length three (unions of so-called Z-cuts) lie at the core of the complexity of the problem - usually lower-bound constructions use simpler cuts inducing either a matching or a disjoint union of bicliques. Finally, we determine the optimal running times for Max Cut (2^{ctw} n^𝒪(1)) and Induced Matching (3^{ctw} n^𝒪(1)) by providing matching lower bounds for the existing algorithms - the latter result also answers an open question for treewidth by Chaudhary and Zehavi [WG 2023].

Recently, Bojikian and Kratsch [2023] have presented a novel approach to tackle connectivity problems parameterized by clique-width ($\operatorname{cw}$), based on counting small representations of partial solutions (modulo two). Using this technique, they were able to get a tight bound for the Steiner Tree problem, answering an open question posed by Hegerfeld and Kratsch [ESA, 2023]. We use the same technique to solve the Connected Odd Cycle Transversal problem in time $\mathcal{O}^*(12^{\operatorname{cw}})$. We define a new representation of partial solutions by separating the connectivity requirement from the 2-colorability requirement of this problem. Moreover, we prove that our result is tight by providing SETH-based lower bound excluding algorithms with running time $\mathcal{O}^*((12-ε)^{\operatorname{lcw}})$ even when parameterized by linear clique-width. This answers the second question posed by Hegerfeld and Kratsch in the same paper.

Given a graph G = (V,E), a set T ⊆ V, and an integer b, the Steiner Tree problem asks whether G has a connected subgraph H with at most b vertices that spans all of T. This work presents a 3^k⋅ n^𝒪(1) time one-sided Monte-Carlo algorithm for solving Steiner Tree when additionally a clique-expression of width k is provided. Known lower bounds for less expressive parameters imply that this dependence on the clique-width of G is optimal assuming the Strong Exponential-Time Hypothesis (SETH). Indeed our work establishes that the parameter dependence of Steiner Tree is the same for any graph parameter between cutwidth and clique-width, assuming SETH. Our work contributes to the program of determining the exact parameterized complexity of fundamental hard problems relative to structural graph parameters such as treewidth, which was initiated by Lokshtanov et al. [SODA 2011 & TALG 2018] and which by now has seen a plethora of results. Since the cut-and-count framework of Cygan et al. [FOCS 2011 & TALG 2022], connectivity problems have played a key role in this program as they pose many challenges for developing tight upper and lower bounds. Recently, Hegerfeld and Kratsch [ESA 2023] gave the first application of the cut-and-count technique to problems parameterized by clique-width and obtained tight bounds for Connected Dominating Set and Connected Vertex Cover, leaving open the complexity of other benchmark connectivity problems such as Steiner Tree and Feedback Vertex Set. Our algorithm for Steiner Tree does not follow the cut-and-count technique and instead works with the connectivity patterns of partial solutions. As a first technical contribution we identify a special family of so-called complete patterns that has strong (existential) representation properties, and using these at least one solution will be preserved. Furthermore, there is a family of 3^k basis patterns that (parity) represents the complete patterns, i.e., it has the same number of solutions modulo two. Our main technical contribution, a new technique called "isolating a representative," allows us to leverage both forms of representation (existential and parity). Both complete patterns and isolation of a representative will likely be applicable to other (connectivity) problems.

In this work we start the investigation of tight complexity bounds for connectivity problems parameterized by cutwidth assuming the Strong Exponential-Time Hypothesis (SETH). Van Geffen et al. posed this question for odd cycle transversal and feedback vertex set. We answer it for these two and four further problems, namely connected vertex cover, connected domintaing set, steiner tree, and connected odd cycle transversal. For the latter two problems it sufficed to prove lower bounds that match the running time inherited from parameterization by treewidth; for the others we provide faster algorithms than relative to treewidth and prove matching lower bounds. For upper bounds we first extend the idea of Groenland et al.~[STACS~2022] to solve what we call coloring-like problem. Such problems are defined by a symmetric matrix $M$ over $\mathbb{F}_2$ indexed by a set of colors. The goal is to count the number (modulo some prime $p$) of colorings of a graph such that $M$ has a $1$-entry if indexed by the colors of the end-points of any edge. We show that this problem can be solved faster if $M$ has small rank over $\mathbb{F}_p$. We apply this result to get our upper bounds for connected vertex cover and connected dominating set. The upper bounds for odd cycle transversal and feedback vertex set use a subdivision trick to get below the bounds that matrix rank would yield.