We study connectivity functions, that is, integer-valued symmetric submodular functions on a finite ground set attaining 0 on the empty set. For a connectivity function f on an n-element set V and an integer k ≥ 0, we show that the family of all sets X ⊆ V with f(X) = k admits a polynomial-size representation: it can be described by a list of at most O(n^{4k}) items, each consisting of a set to be included, another set to be excluded, and a partition of remaining elements, such that the union of some members of the partition and the set to be included are precisely all sets X with f(X) = k. We also give an algorithm that constructs this representation in time O(n^{2k+7}γ+n^{2k+8}+n^{4k+2}), where γ is the oracle time to evaluate f. This generalizes the low rank structure theorem of Bojańczyk, Pilipczuk, Przybyszewski, Sokołowski, and Stamoulis [Low rank MSO, LICS 2026] on cut-rank functions on graphs to general connectivity functions. As an application, for fixed k, we obtain a polynomial-time algorithm for finding a set A with f(A) = k and a prescribed cardinality constraint on A.

We prove that for any circle graph \(H\) with at least one edge and for any positive integer \(k\), there exists an integer \(t = t(k,H)\) so that every graph \(G\) either has a vertex-minor isomorphic to the disjoint union of \(k\) copies of \(H\), or has a \(t\)-perturbation with no vertex-minor isomorphic to \(H\). Using the same techniques, we also prove that for any planar multigraph \(H\), every binary matroid either has a minor isomorphic to the cycle matroid of \(kH\), or is a low-rank perturbation of a binary matroid with no minor isomorphic to the cycle matroid of \(H\).

Let ${\mathbb{F}}$ be a finite field. We prove that there is an MSO-transduction which, given an ${\mathbb{F}}$-representable matroid of path-width k, produces a branch-decomposition of width at most f(k), for some function f. As a corollary, any recognizable property of ${\mathbb{F}}$-representable matroids with bounded path-width is definable in MSO logic, and therefore recognizability is equivalent to MSO-definability on classes of ${\mathbb{F}}$-representable matroids of bounded path-width. This generalizes the result of Bojańczyk, Grohe and Pilipczuk [Logical Methods in Computer Science 17(1), 2021] which asserts the equivalence of the two notions on graphs of bounded linear clique-width.

Abstract. For each [Formula: see text], we construct a finite set [Formula: see text] of multigraphs such that for each graph [Formula: see text] of girth at least 5 obtained from a multigraph [Formula: see text] by subdividing each edge at least two times, [Formula: see text] has twin-width at most [Formula: see text] if and only if [Formula: see text] has no minor in [Formula: see text]. This answers a question of Bergé, Bonnet, and Déprés asking for the structure of graphs [Formula: see text] such that each long subdivision of [Formula: see text] has twin-width 4. As a corollary, we show that the [Formula: see text] grid has twin-width 4, which answers a question of Schidler and Szeider.

Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simple as path or tree decompositions, such dynamic programming uses space that is exponential in the decomposition's width, and there are good reasons to believe that this is necessary. However, it has been shown that in graphs of low treedepth it is possible to design algorithms which achieve polynomial space complexity without requiring worse time complexity than their counterparts working on tree decompositions of bounded width. Here, treedepth is a graph parameter that, intuitively speaking, takes into account both the depth and the width of a tree decomposition of the graph, rather than the width alone. Motivated by the above, we consider graphs that admit clique expressions with bounded depth and label count, or equivalently, graphs of low shrubdepth (sd). Here, sd is a bounded-depth analogue of cliquewidth, in the same way as td is a bounded-depth analogue of treewidth. We show that also in this setting, bounding the depth of the decomposition is a deciding factor for improving the space complexity. Precisely, we prove that on $n$-vertex graphs equipped with a tree-model (a decomposition notion underlying sd) of depth $d$ and using $k$ labels, we can solve - Independent Set in time $2^{O(dk)}\cdot n^{O(1)}$ using $O(dk^2\log n)$ space; - Max Cut in time $n^{O(dk)}$ using $O(dk\log n)$ space; and - Dominating Set in time $2^{O(dk)}\cdot n^{O(1)}$ using $n^{O(1)}$ space via a randomized algorithm. We also establish a lower bound, conditional on a certain assumption about the complexity of Longest Common Subsequence, which shows that at least in the case of IS the exponent of the parametric factor in the time complexity has to grow with $d$ if one wishes to keep the space complexity polynomial.

For a non-negative integer $$\ell $$ , the $$\ell $$ -leaf power of a tree T is a simple graph G on the leaves of T such that two vertices are adjacent in G if and only if their distance in T is at most $$\ell $$ . We provide a polynomial kernel for the problem of deciding whether we can delete at most k vertices to make an input graph a 3-leaf power of some tree. More specifically, we present a polynomial-time algorithm for an input instance (G, k) for the problem to output an equivalent instance $$(G',k')$$ such that $$k'\leqslant k$$ and $$G'$$ has at most $$O(k^{14})$$ vertices.

Abstract. We show that for pairs [Formula: see text] and [Formula: see text] of disjoint subsets of vertices of a graph [Formula: see text], if [Formula: see text] is sufficiently large, then there exists a vertex [Formula: see text] in [Formula: see text] such that there are two ways to reduce [Formula: see text] by a vertex-minor operation that removes [Formula: see text] while preserving the connectivity between [Formula: see text] and [Formula: see text] and the connectivity between [Formula: see text] and [Formula: see text]. Our theorem implies an analogous theorem of Chen and Whittle (SIAM J. Discrete Math., 28 (2014), pp. 1402–1404) for matroids restricted to binary matroids.

Every minor-closed class of matroids of bounded branch-width can be characterized by a minimal list of excluded minors, but unlike graphs, this list could be infinite in general. However, for each fixed finite field F, the list contains only finitely many F-representable matroids, due to the well-quasi-ordering of F-representable matroids of bounded branch-width under taking matroid minors [J. F. Geelen, A. M. H. Gerards, and G. Whittle (2002)]. But this proof is non-constructive and does not provide any algorithm for computing these F-representable excluded minors in general. We consider the class of matroids of path-width at most k for fixed k. We prove that for a finite field F, every F-representable excluded minor for the class of matroids of path-width at most k has at most 2^{|𝔽|^{O(k²)}} elements. We can therefore compute, for any integer k and a fixed finite field F, the set of F-representable excluded minors for the class of matroids of path-width k, and this gives as a corollary a polynomial-time algorithm for checking whether the path-width of an F-represented matroid is at most k. We also prove that every excluded pivot-minor for the class of graphs having linear rank-width at most k has at most 2^{2^{O(k²)}} vertices, which also results in a similar algorithmic consequence for linear rank-width of graphs.

For a class C of graphs, we define C-edge-brittleness of a graph G as the minimum ℓ such that the vertex set of G can be partitioned into sets inducing a subgraph in C and there are ℓ edges having ends in distinct parts. We characterize classes of graphs having bounded C-edge-brittleness for a class C of forests or a class C of graphs with no K4∖e topological minors in terms of forbidden obstructions. We also define C-vertex-brittleness of a graph G as the minimum ℓ such that the edge set of G can be partitioned into sets inducing a subgraph in C and there are ℓ vertices incident with edges in distinct parts. We characterize classes of graphs having bounded C-vertex-brittleness for a class C of forests or a class C of outerplanar graphs in terms of forbidden obstructions. We also investigate the relations between the new parameters and the edit distance.

Bonnet et al. [ J. ACM, 69 (2022), 3] introduced the twin-width of a graph. We show that the twin-width of an $n$-vertex graph is less than $(n+\sqrt{n\ln n}+\sqrt{n}+2\ln n)/2$, and the twin-width of an $m$-edge graph for a positive $m$ is less than $\sqrt{3m}+ m^{1/4} \sqrt{\ln m} / (4\cdot 3^{1/4}) + 3m^{1/4} / 2$. Conference graphs of order $n$ (when such graphs exist) have twin-width at least $(n-1)/2$, and we show that Paley graphs achieve this lower bound. We also show that the twin-width of the Erdös--Rényi random graph $G(n,p)$ with $1/n\leq p\leq 1/2$ is larger than $2p(1-p)n - (2\sqrt{2}+\varepsilon)\sqrt{p(1-p)n\ln n}$ asymptotically almost surely for any positive $\varepsilon$. Last, we calculate the twin-width of random graphs $G(n,p)$ with $p\leq c/n$ for a constant $c<1$, determining the thresholds at which the twin-width jumps from $0$ to $1$ and from $1$ to $2$.

For an abelian group $Γ$, a $Γ$-labelled graph is a graph whose vertices are labelled by elements of $Γ$. We prove that a certain collection of edge sets of a $Γ$-labelled graph forms a delta-matroid, which we call a $Γ$-graphic delta-matroid, and provide a polynomial-time algorithm to solve the separation problem, which allows us to apply the symmetric greedy algorithm of Bouchet to find a maximum weight feasible set in such a delta-matroid. We present two algorithmic applications on graphs; Maximum Weight Packing of Trees of Order Not Divisible by $k$ and Maximum Weight $S$-Tree Packing. We also discuss various properties of $Γ$-graphic delta-matroids.

Tree-width and its linear variant path-width play a central role for the graph minor relation. In particular, Robertson and Seymour [ J. Combin. Theory Ser. B, 35 (1983), pp. 39--61] proved that for every tree $T$, the class of graphs that do not contain $T$ as a minor has bounded path-width. For the pivot-minor relation, rank-width and linear rank-width take over the role of tree-width and path-width. As such, it is natural to examine if, for every tree $T$, the class of graphs that do not contain $T$ as a pivot-minor has bounded linear rank-width. We first prove that this statement is false whenever $T$ is a tree that is not a caterpillar. We conjecture that the statement is true if $T$ is a caterpillar. We are also able to give partial confirmation of this conjecture by proving for every tree $T$, the class of $T$-pivot-minor-free distance-hereditary graphs has bounded linear rank-width if and only if $T$ is a caterpillar; for every caterpillar $T$ on at most four vertices, the class of $T$-pivot-minor-free graphs has bounded linear rank-width. To prove our second result, we only need to consider $T=P_4$ and $T=K_{1,3}$, but we follow a general strategy: first we show that the class of $T$-pivot-minor-free graphs is contained in some class of $(H_1,H_2)$-free graphs, which we then show to have bounded linear rank-width. In particular, we prove that the class of $(K_3,S_{1,2,2})$-free graphs has bounded linear rank-width, which strengthens a known result that this graph class has bounded rank-width.

Given $n$ subspaces of a finite-dimensional vector space over a fixed finite field ${\mathbb F}$, we wish to find a “branch-decomposition” of these subspaces of width at most $k$ that is a subcubic tree $T$ with $n$ leaves mapped bijectively to the subspaces such that for every edge $e$ of $T$, the sum of subspaces associated to the leaves in one component of $T-e$ and the sum of subspaces associated to the leaves in the other component have the intersection of dimension at most $k$. This problem includes the problems of computing branch-width of ${\mathbb F}$-represented matroids, rank-width of graphs, branch-width of hypergraphs, and carving-width of graphs. We present a fixed-parameter algorithm to construct such a branch-decomposition of width at most $k$, if it exists, for input subspaces of a finite-dimensional vector space over ${\mathbb F}$. Our algorithm is analogous to the algorithm of Bodlaender and Kloks [ J. Algorithms, 21 (1996), pp. 358--402] on tree-width of graphs. To extend their framework to branch-decompositions of vector spaces, we developed highly generic tools for branch-decompositions on vector spaces. The only known previous fixed-parameter algorithm for branch-width of ${\mathbb F}$-represented matroids was due to Hliněný and Oum [ SIAM J. Comput., 38 (2008), pp. 1012--1032] that runs in time $O(n^3)$ where $n$ is the number of elements of the input ${\mathbb F}$-represented matroid. But their method is highly indirect. Their algorithm uses the nontrivial fact by Geelen et al. [ J. Combin. Theory Ser. B, 88 (2003), pp. 261--265] that the number of forbidden minors is finite and uses the algorithm of Hliněný [ J. Combin. Theory Ser. B, 96 (2006), pp. 325--351] on checking monadic second-order formulas on ${\mathbb F}$-represented matroids of small branch-width. Our result does not depend on such a fact and is completely self-contained, and yet matches their asymptotic running time for each fixed $k$.

Many NP-hard problems on graphs are known to be tractable if we restrict the input to have a certain decomposition into a tree-like structure. Width parameters of graphs are measures on how easy it is to decompose the input graph into a tree-like structure. The tree-width is one of the most well-studied width parameters of graphs and the rank-width is a generalization of tree-width into dense graphs. This talk will present a survey on width parameters of graphs such as tree-width and rank-width and discuss known algorithms to find a decomposition of an input graph into such tree-like structures efficiently.

For a non-negative integer 𝓁, a graph G is an 𝓁-leaf power of a tree T if V(G) is equal to the set of leaves of T, and distinct vertices v and w of G are adjacent if and only if the distance between v and w in T is at most 𝓁. Given a graph G, 3-Leaf Power Deletion asks whether there is a set S ⊆ V(G) of size at most k such that G\S is a 3-leaf power of some treeT. We provide a polynomial kernel for this problem. More specifically, we present a polynomial-time algorithm for an input instance (G,k) to output an equivalent instance (G',k') such that k'≤ k and G' has at most O(k^14) vertices.

For a class $\mathcal C$ of graphs $G$ equipped with functions $f_G$ defined on subsets of $E(G)$ or $V(G)$, we say that $\mathcal{C}$ is $k$-$scattered$ with respect to $f_G$ if there exists a constant $\ell$ such that for every graph $G\in \mathcal C$, the domain of $f_G$ can be partitioned into subsets of size at most $k$ so that the union of every collection of the subsets has $f_G$ value at most $\ell$. We present structural characterizations of graph classes that are $k$-scattered with respect to several graph connectivity functions. In particular, our theorem for cut-rank functions provides a rough structural characterization of graphs having no $mK_{1,n}$ vertex-minor, which allows us to prove that such graphs have bounded linear rank-width.

Given $n$ subspaces of a finite-dimensional vector space over a fixed finite field $\mathbb F$, we wish to find a "branch-decomposition" of these subspaces of width at most $k$ that is a subcubic tree $T$ with $n$ leaves mapped bijectively to the subspaces such that for every edge $e$ of $T$, the sum of subspaces associated to the leaves in one component of $T-e$ and the sum of subspaces associated to the leaves in the other component have the intersection of dimension at most $k$. This problem includes the problems of computing branch-width of $\mathbb F$-represented matroids, rank-width of graphs, branch-width of hypergraphs, and carving-width of graphs. We present a fixed-parameter algorithm to construct such a branch-decomposition of width at most $k$, if it exists, for input subspaces of a finite-dimensional vector space over $\mathbb F$. Our algorithm is analogous to the algorithm of Bodlaender and Kloks (1996) on tree-width of graphs. To extend their framework to branch-decompositions of vector spaces, we developed highly generic tools for branch-decompositions on vector spaces. The only known previous fixed-parameter algorithm for branch-width of $\mathbb F$-represented matroids was due to Hliněný and Oum (2008) that runs in time $O(n^3)$ where $n$ is the number of elements of the input $\mathbb F$-represented matroid. But their method is highly indirect. Their algorithm uses the nontrivial fact by Geelen et al. (2003) that the number of forbidden minors is finite and uses the algorithm of Hliněný (2006) on checking monadic second-order formulas on $\mathbb F$-represented matroids of small branch-width. Our result does not depend on such a fact and is completely self-contained, and yet matches their asymptotic running time for each fixed $k$.

For nonnegative integers $k, d_1, \ldots, d_k$, a graph is $(d_1, \ldots, d_k)$-colorable if its vertex set can be partitioned into $k$ parts so that the $i$th part induces a graph with maximum degree at most $d_i$ for all $i\in\{1, \ldots, k\}$. A class $\mathcal C$ of graphs is balanced $k$-partitionable and unbalanced $k$-partitionable if there exists a nonnegative integer $D$ such that all graphs in $\mathcal C$ are $(D, \ldots, D)$-colorable and $(0, \ldots, 0, D)$-colorable, respectively, where the tuple has length $k$. A set $X$ of cycles is a cycle obstruction set of a class $\mathcal C$ of planar graphs if every planar graph containing none of the cycles in $X$ as a subgraph belongs to $\mathcal C$. This paper characterizes all cycle obstruction sets of planar graphs to be balanced $k$-partitionable and unbalanced $k$-partitionable for all $k$; namely, we identify all inclusionwise minimal cycle obstruction sets for all $k$.

Given n subspaces of a finite-dimensional vector space over a fixed finite field F, we wish to find a linear layout V1, V2,..., Vnof the subspaces such that dim((V1+ V2+ ··· + Vi) ∩ (Vi+1+ ··· + Vn)) ≤ k for all i; such a linear layout is said to have width at most k. When restricted to 1-dimensional subspaces, this problem is equivalent to computing the trellis-width (or minimum trellis state-complexity) of a linear code in coding theory and computing the path-width of an F-represented matroid in matroid theory. We present a fixed-parameter tractable algorithm to construct a linear layout of width at most k, if it exists, for input subspaces of a finite-dimensional vector space over F. As corollaries, we obtain a fixed-parameter tractable algorithm to produce a path-decomposition of width at most k for an input F-represented matroid of path-width at most k, and a fixed-parameter tractable algorithm to find a linear rank-decomposition of width at most k for an input graph of linear rank-width at most k. In both corollaries, no such algorithms were known previously. Our approach is based on dynamic programming combined with the idea developed by Bodlaender and Kloks (1996) for their work on path-width and tree-width of graphs. It was previously known that a fixed-parameter tractable algorithm exists for the decision version of the problem for matroid path-width; a theorem by Geelen, Gerards, and Whittle (2002) implies that for each fixed finite field F, there are finitely many forbidden F-representable minors for the class of matroids of path-width at most k. An algorithm by Hlinený (2006) can detect a minor in an input F-represented matroid of bounded branch-width. However, this indirect approach would not produce an actual path-decomposition. Our algorithm is the first one to construct such a path-decomposition and does not depend on the finiteness of forbidden minors.

Given n subspaces of a finite-dimensional vector space over a fixed finite field F, we wish to find a linear layout V1, V2, …, Vn of the subspaces such that dim((V1 + V2 + ⃛ + Vi)∩(Vi+1 + ⃛ + Vn)) ≤ k for all i; such a linear layout is said to have width at most k. When restricted to 1-dimensional subspaces, this problem is equivalent to computing the path-width of an F-represented matroid in matroid theory and computing the trellis-width (or minimum trellis state-complexity) of a linear code in coding theory. We present a fixed-parameter tractable algorithm to construct a linear layout of width at most k, if it exists, for input subspaces of a finite-dimensional vector space over F. As corollaries, we obtain a fixed-parameter tractable algorithm to produce a path-decomposition of width at most k for an input F-represented matroid of path-width at most k, and a fixed-parameter tractable algorithm to find a linear rank-decomposition of width at most k for an input graph of linear rank-width at most k. In both corollaries, no such algorithms were known previously. Our approach is based on dynamic programming combined with the idea developed by Bodlaender and Kloks (1996) for their work on path-width and tree-width of graphs. It was previously known that a fixed-parameter tractable algorithm exists for the decision version of the problem for matroid path-width; a theorem by Geelen, Gerards, and Whittle (2002) implies that for each fixed finite field F, there are finitely many forbidden F-representable minors for the class of matroids of path-width at most k. An algorithm by Hliněný (2006) can detect a minor in an input F-represented matroid of bounded branch-width. However, this indirect approach would not produce an actual path-decomposition even if the complete list of forbidden minors were known. Our algorithm is the first one to construct such a path-decomposition and does not depend on the finiteness of forbidden minors.

Hadwiger's conjecture asserts that if a simple graph $G$ has no $K_{t+1}$ minor, then its vertex set $V(G)$ can be partitioned into $t$ stable sets. This is still open, but we prove under the same hypothesis that $V(G)$ can be partitioned into $t$ sets $X_1,\ldots,X_t$, such that for $1\le i\le t$, the subgraph induced on $X_i$ has maximum degree at most a function of $t$. This is sharp, in that the conclusion becomes false if we ask for a partition into $t-1$ sets with the same property.

We prove that for all positive integers $t$, every $n$-vertex graph with no $K_t$-subdivision has at most $2^{50t}n$ cliques. We also prove that asymptotically, such graphs contain at most $2^{(5+o(1))t}n$ cliques, where $o(1)$ tends to zero as $t$ tends to infinity. This strongly answers a question of Wood that asks whether the number of cliques in $n$-vertex graphs with no $K_t$-minor is at most $2^{ct}n$ for some constant $c$.

Linear rank-width is a graph width parameter, which is a variation of rank-width by restricting its tree to a caterpillar. As a corollary of known theorems, for each k, there is a finite set \mathcal{O}_k of graphs such that a graph G has linear rank-width at most k if and only if no vertex-minor of G is isomorphic to a graph in \mathcal{O}_k. However, no attempts have been made to bound the number of graphs in \mathcal{O}_k for k >= 2. We construct, for each k, 2^{\Omega(3^k)} pairwise locally non-equivalent graphs that are excluded vertex-minors for graphs of linear rank-width at most k. Therefore the number of graphs in \mathcal{O}_k is at least double exponential.

Besides the successful concept of tree-width (see [H. Bodlaender, A. Koster: Combinatorial optimisation on graphs of bounded treewidth, ***** * this survey volume ******, 14 p.]) in the past years, many concepts and parameters measuring a similarity of structures to trees, or how a structure distinguishes from a tree, have been born and studied. These concepts and parameters proved to be useful tools for many applications, especially in the design of efficient algorithms. We present a novel view of contemporary developments of these “width” parameters in combinatorial structures that, besides traditional tree-width and derived dynamic programming schemes, leads to other usable parameters like branch-width,

We present a new algorithm that can output the rank-decomposition of width at most k of a graph if such exists. For that we use an algorithm that, for an input matroid represented over a fixed finite field, outputs its branch-decomposition of width at most k if such exists. This algorithm works also for partitioned matroids. Both of these algorithms are fixed-parameter tractable, that is, they run in time $O(n^3)$ where n is the number of vertices / elements of the input, for each constant value of k and any fixed finite field. The previous best algorithm for construction of a branch-decomposition or a rank-decomposition of optimal width due to Oum and Seymour [J. Combin. Theory Ser. B, 97 (2007), pp. 385–393] is not fixed-parameter tractable.

Robertson and Seymour [J. Combin. Theory Ser. B, 48 (1990), pp. 227–254] proved that graphs of bounded tree-width are well-quasi-ordered by the graph minor relation. By extending their arguments, Geelen, Gerards, and Whittle [J. Combin. Theory Ser. B, 84 (2002), pp. 270–290] proved that binary matroids of bounded branch-width are well-quasi-ordered by the matroid minor relation. We prove another theorem of this kind in terms of rank-width and vertex-minors. For a graph $G=(V,E)$ and a vertex v of G, a local complementation at v is an operation that replaces the subgraph induced by the neighbors of v with its complement graph. A graph H is called a vertex-minor of G if H can be obtained from G by applying a sequence of vertex deletions and local complementations. Rank-width was defined by Oum and Seymour [J. Combin. Theory Ser. B, 96 (2006), pp. 514–528] to investigate clique-width; they showed that graphs have bounded rank-width if and only if they have bounded clique-width. We prove that graphs of bounded rank-width are well-quasi-ordered by the vertex-minor relation; in other words, for every infinite sequence $G_1,G_2,\ldots$ of graphs of rank-width (or clique-width) at most k, there exist $i

Rank-width was defined by Oum and Seymour [2006] to investigate clique-width. They constructed an algorithm that either outputs a rank-decomposition of width at most f ( k ) for some function f or confirms that rank-width is larger than k in time O (| V | 9 log | V |) for an input graph G = ( V , E ) and a fixed k . We develop three separate algorithms of this kind with faster running time. We construct an O (| V | 4 )-time algorithm with f ( k ) = 3 k + 1 by constructing a subroutine for the previous algorithm; we avoid generic algorithms minimizing submodular functions used by Oum and Seymour. Another one is an O (| V | 3 )-time algorithm with f ( k ) = 24 k , achieved by giving a reduction from graphs to binary matroids; then we use an approximation algorithm for matroid branch-width by Hliněný [2005]. Finally we construct an O (| V | 3 )-time algorithm with f ( k ) = 3 k − 1 by combining the ideas of the two previously cited papers.