The induced matching width of a tree decomposition of a graph \(G\) is the cardinality of a largest induced matching \(M\) of \(G\), such that there exists a bag that intersects every edge in \(M\). The induced matching treewidth of \(G\), denoted by tree-\(\mu(G)\), is the minimum induced matching width of a tree decomposition of \(G\). The parameter tree-\(\mu\) was introduced by Yolov [SODA ’18], who showed that, for example, Maximum-Weight Independent Set can be solved in polynomial-time on graphs of bounded tree-\(\mu\). Lima, Milanič, Muršič, Okrasa, Rzążewski, and Šorgel [ESA ’24] conjectured that this algorithm can be generalized to a meta-problem called Maximum-Weight Induced Subgraph of Bounded Treewidth, where we are given a vertex-weighted graph \(G\), an integer \(w\), and a \(\mathsf{CMSO_2}\)-sentence \(\Phi\), and are asked to find a maximum-weight set \(X \subseteq V(G)\) so that \(G[X]\) has treewidth at most \(w\) and satisfies \(\Phi\). They proved the conjecture for some special cases, such as for the problem Maximum-Weight Induced Forest.

Kernelization studies polynomial-time preprocessing algorithms. Over the last 20 years, the most celebrated positive results of the field have been linear kernels for classical NP-hard graph problems on sparse graph classes. In this paper, we lift these results to the dynamic setting.

The planar separator theorem by Lipton and Tarjan [FOCS '77, SIAM Journal on Applied Mathematics '79] states that any planar graph with $n$ vertices has a balanced separator of size $O(\sqrt{n})$ that can be found in linear time. This landmark result kicked off decades of research on designing linear or nearly linear-time algorithms on planar graphs. In an attempt to generalize Lipton-Tarjan's theorem to nonplanar graphs, Alon, Seymour, and Thomas [STOC '90, Journal of the AMS '90] showed that any minor-free graph admits a balanced separator of size $O(\sqrt{n})$ that can be found in $O(n^{3/2})$ time. The superlinear running time in their separator theorem is a key bottleneck for generalizing algorithmic results from planar to minor-free graphs. Despite extensive research for more than two decades, finding a balanced separator of size $O(\sqrt{n})$ in (linear) $O(n)$ time for minor-free graphs remains a major open problem. Known algorithms either give a separator of size much larger than $O(\sqrt{n})$ or have superlinear running time, or both. In this paper, we answer the open problem affirmatively. Our algorithm is very simple: it runs a vertex-weighted variant of breadth-first search (BFS) a constant number of times on the input graph. Our key technical contribution is a weighting scheme on the vertices to guide the search for a balanced separator, offering a new connection between the size of a balanced separator and the existence of a clique-minor model. We believe that our weighting scheme may be of independent interest.

Abstract We study the following Independent Stable Set problem. Let $$\varvec{G}$$ G be an undirected graph and $$\varvec{\mathcal {M}} \varvec{=} \varvec{(V(G),} \varvec{\mathcal {I})}$$ M = ( V ( G ) , I ) be a matroid whose elements are the vertices of $$\varvec{G}$$ G . For an integer $$\varvec{k}\varvec{\ge } \varvec{1}$$ k ≥ 1 , the task is to decide whether $$\varvec{G}$$ G contains a set $$\varvec{S}\varvec{\subseteq } \varvec{V(G)}$$ S ⊆ V ( G ) of size at least $$\varvec{k}$$ k which is independent (stable) in $$\varvec{G}$$ G and independent in $$\varvec{\mathcal {M}}$$ M . This problem generalizes several well-studied algorithmic problems, including Rainbow Independent Set , Rainbow Matching , and Bipartite Matching with Separation . We show that when the matroid $$\varvec{\mathcal {M}}$$ M is represented by an independence oracle, then for any computable function $$\varvec{f}$$ f , no algorithm can solve Independent Stable Set using $$\varvec{f(k)} \varvec{\cdot } \varvec{n}^{\varvec{o(k)}}$$ f ( k ) · n o ( k ) calls to the oracle. On the other hand, when the graph $$\varvec{G}$$ G

Cycle packing is a fundamental problem in optimization, graph theory, and algorithms. Motivated by recent advancements in finding vertex-disjoint paths between a specified set of vertices that either minimize the total length of the paths [Björklund and Husfeldt, ICALP 2014; Mari et al., SODA 2024] or request the paths to be shortest [Lochet, SODA 2021], we consider the following cycle packing problems: Min-Sum Cycle Packing and Shortest Cycle Packing . In Min-Sum Cycle Packing , we try to find, in a weighted undirected graph, \( k \) vertex-disjoint cycles of minimum total weight. Our first main result is an algorithm that, for any fixed \( k \) , solves the problem in polynomial time. We complement this result by establishing the W[1]-hardness of Min-Sum Cycle Packing parameterized by \( k \) . The same results hold for the version of the problem where the task is to find \( k \) edge-disjoint cycles. Our second main result concerns Shortest Cycle Packing , which is a special case of Min-Sum Cycle Packing that asks to find a packing of \( k \) shortest cycles in a graph. We prove this problem to be Fixed-Parameter Tractable (FPT) when parameterized by \( k \) on weighted planar graphs. We also obtain a polynomial kernel for the edge-disjoint variant of the problem on planar graphs. Whether Min-Sum Cycle Packing is FPT on planar graphs, or Shortest Cycle Packing on general graphs, remains open.

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 time \(n^{\mathcal{O}(k)}\) if the input \( n \) -vertex graph is given together with a tree decomposition of independence number \( k \) . Yolov, in SODA 2018, gave an algorithm that, given an \( n \) -vertex graph \( G \) and an integer \( k \) , in time \(n^{\mathcal{O}(k^{3})}\) either constructs a tree decomposition of \( G \) whose independence number is \(\mathcal{O}(k^{3})\) or correctly reports that the tree-independence number of \( G \) is larger than \( k \) . In this article, we first give an algorithm for computing the tree-independence number with a better approximation ratio and running time and then prove that our algorithm is, in some sense, the best one can hope for. More precisely, our algorithm runs in time \(2^{\mathcal{O}(k^{2})}n^{\mathcal{O}(k)}\) and either outputs a tree decomposition of \( G \) with independence number at most \(8k\) or determines that the tree-independence number of \( G \) is larger than \( k \) . This implies \(2^{\mathcal{O}(k^{2})}n^{\mathcal{O}(k)}\) -time algorithms for various problems, like maximum-weight independent set, parameterized by the tree-independence number \( k \) without needing the decomposition as an input. Assuming Gap-ETH, an \(n^{\Omega(k)}\) factor in the running time is unavoidable for any approximation algorithm for the tree-independence number. Our second result is that the exact computation of the tree-independence number is para-NP -hard: We show that for every constant \(k\geq 4\) it is NP -complete to decide whether a given graph has the tree-independence number at most \( k \) .

We present a dynamic data structure that maintains a tree decomposition of width at most $9 k+8$ of a dynamic graph with treewidth at most k, which is updated by edge insertions and deletions. The amortized update time of our data structure is $2^{\mathcal{O}(k)} \log n$, where n is the number of vertices. The data structure also supports maintaining any “dynamic programming scheme” on the tree decomposition, providing, for example, a dynamic version of Courcelle’s theorem with ${\mathcal{O}}_{k}(\log n)$ amortized update time; the ${\mathcal{O}}_{k}(\cdot)$ notation hides factors that depend on k. This improves upon a result of Korhonen, Majewski, Nadara, Pilipczuk, and Sokołowski [FOCS 2023], who gave a similar data structure but with amortized update time $2^{k^{\mathcal{O}(1)}} n^{o(1)}$. Furthermore, our data structure is arguably simpler. Our main novel idea is to maintain a tree decomposition that is “downwards well-linked”, which allows us to implement local rotations and analysis similar to those for splay trees.

Cycle packing is a fundamental problem in optimization, graph theory, and algorithms. Motivated by recent advancements in finding vertex-disjoint paths between a specified set of vertices that either minimize the total length of the paths [Björklund, Husfeldt, ICALP 2014;

In the Hedge Cut problem, the edges of a graph are partitioned into groups called hedges, and the question is what is the minimum number of hedges to delete to disconnect the graph. Ghaffari, Karger, and Panigrahi [SODA 2017] showed that Hedge Cut can be solved in quasipolynomial-time, raising the hope for a polynomial time algorithm. Jaffke, Lima, Masarik, Pilipczuk, and Souza [SODA 2023] complemented this result by showing that assuming the Exponential Time Hypothesis (ETH), no polynomial-time algorithm exists. In this paper, we show that Hedge Cut is fixed-parameter tractable parameterized by the solution size ℓ by providing an algorithm with running time , which can be upper bounded by Cℓ · (n + m)O (1) for any constant c > 1. This running time captures at the same time the fact that the problem is quasipolynomial-time solvable, and that it is fixed-parameter tractable parameterized by ℓ. We further generalize this algorithm to an algorithm with running time for Hedge k-CUT.

We present kO(k2) m time algorithms for various problems about decomposing a given undirected graph by edge cuts or vertex separators of size O(k2) m time algorithm for computing a k-Gomory-Hu tree of a given graph, which is a structure representing pairwise minimum cuts of size O(k2) m time algorithm for computing a k-lean tree decomposition of a given graph. This is a tree decomposition with adhesion size O(k2) m time algorithms for k-vertex connectivity and for element connectivity k-Gomory-Hu tree. 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 treewidth.

Abstract. We prove that if a graph contains the complete bipartite graph [Formula: see text] as an induced minor, then it contains a cycle of length at most 12 or a theta as an induced subgraph. With a longer and more technical proof, we prove that if a graph contains [Formula: see text] as an induced minor, then it contains a triangle or a theta as an induced subgraph. Here, a theta is a graph made of three internally vertex-disjoint chordless paths [Formula: see text], [Formula: see text], [Formula: see text], each of length at least two, such that no edges exist between the paths except the three edges incident to [Formula: see text] and the three edges incident to [Formula: see text]. A consequence is that excluding a grid and a complete bipartite graph as induced minors is not enough to guarantee a bounded tree-independence number or even that the treewidth is bounded by a function of the size of the maximum clique, because the existence of graphs with large treewidth that contain no triangles or thetas as induced subgraphs is already known (the so-called layered wheels).

Abstract. A framework consists of an undirected graph [Formula: see text] and a matroid [Formula: see text] whose elements correspond to the vertices of [Formula: see text]. Recently, Fomin et al. [ Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2023, pp. 2214–2227] and Eiben, Koana, and Wahlström [ Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2024, pp. 377–423] developed parameterized algorithms for computing paths of rank [Formula: see text] in frameworks. More precisely, for vertices [Formula: see text] and [Formula: see text] of [Formula: see text], and an integer [Formula: see text], they gave FPT algorithms parameterized by [Formula: see text] deciding whether there is an [Formula: see text]-path in [Formula: see text] whose vertex set contains a subset of elements of [Formula: see text] of rank [Formula: see text]. These algorithms are based on the Schwartz–Zippel lemma for polynomial identity testing and thus are randomized, and therefore the existence of a deterministic FPT algorithm for this problem remains open. We present the first deterministic FPT algorithm that solves the problem in frameworks whose underlying graph [Formula: see text] is planar. While the running time of our algorithm is worse than the running times of the recent randomized algorithms, our algorithm works on more general classes of matroids. In particular, this is the first FPT algorithm for the case when matroid [Formula: see text] is represented over rationals. We complement this result by proving that if the input matroids are given by their independence oracles, then there is no algorithm solving the problem with [Formula: see text] oracle queries. Furthermore, this computational lower bound holds even if the input graphs are planar graphs of treewidth at most two.

Markov networks are probabilistic graphical models that employ undirected graphs to depict conditional independence relationships among variables. Our focus lies in constraint-based structure learning, which entails learning the undirected graph from data through the execution of conditional independence tests. We establish theoretical limits concerning two critical aspects of constraint-based learning of Markov networks: the number of tests and the sizes of the conditioning sets. These bounds uncover an exciting interplay between the structural properties of the graph and the amount of tests required to learn a Markov network. The starting point of our work is that the graph parameter maximum pairwise connectivity, $\kappa$, that is, the maximum number of vertex-disjoint paths connecting a pair of vertices in the graph, is responsible for the sizes of independence tests required to learn the graph. On one hand, we show that at least one test with the size of the conditioning set at least $\kappa$ is always necessary. On the other hand, we prove that any graph can be learned by performing tests of size at most $\kappa$. This completely resolves the question of the minimum size of conditioning sets required to learn the graph. When it comes to the number of tests, our upper bound on the sizes of conditioning sets implies that every $n$-vertex graph can be learned by at most $n^{\kappa}$ tests with conditioning sets of sizes at most $\kappa$. We show that for any upper bound q on the sizes of the conditioning sets, there exist graphs with $O(nq)$ vertices that require at least $n^{\Omega(\kappa)}$ tests to learn. This lower bound holds even when the treewidth and the maximum degree of the graph are at most $\kappa+2$. On the positive side, we prove that every graph of bounded treewidth can be learned by a polynomial number of tests with conditioning sets of sizes at most $2*\kappa$.

We give an algorithm that, given graphs$G$and$H$, tests whether$H$is a minor of$G$in time$\mathcal{O}_{H}(\overline{n}^{1+o(1)})$; here,$n$is the number of vertices of$G$and the$\mathrm{O}_{H}(.)$-notation hides factors that depend on$H$and are computable. By the Graph Minor Theorem, this implies the existence of an$n^{1+o(1)}$-time membership test for every minor-closed class of graphs. More generally, we give an$\mathcal{O}_{H,\vert X\vert} (m^{1+o(1)})$-time algorithm for the rooted version of the problem, in which$G$comes with a set of roots$X\subseteq V(G)$and some of the branch sets of the sought minor model of$H$are required to contain prescribed subsets of$X$; here,$m$is the total number of vertices and edges of$G$. This captures the Disjoint Pathsproblem, for which we obtain an$\mathcal{O}_{k}(m^{1+o(1)\backslash }$-time algorithm, where$k$is the number of terminal pairs. For all the mentioned problems, the fastest algorithms known before are due to Kawarabayashi, Kobayashi, and Reed [JCTB 2012], and have a time complexity that is quadratic in the number of vertices of$G$. Our algorithm has two main ingredients: First, we show that by using the dynamic treewidth data structure of Korhonen, Majewski, Nadara, Pilipczuk, and Sokolowski [FOCS 2023], the irrelevant vertex technique of Robertson and Seymour can be implemented in almost-linear time on apex-minor-free graphs. Then, we apply the recent advances in almost-linear time flow/cut algorithms to give an almost-linear time implementation of the recursive understanding technique, which effectively reduces the problem to apex-minor-free graphs.

We study the following Two-Sets Cut-Uncut problem on planar graphs. Therein, one is given an undirected planar graph $G$ and two sets of vertices $S$ and $T$. The question is, what is the minimum number of edges to remove from $G$, such that we separate all of $S$ from all of $T$, while maintaining that every vertex in $S$, and respectively in $T$, stays in the same connected component. We show that this problem can be solved in time $2^{|S|+|T|} n^{O(1)}$ with a one-sided error randomized algorithm. Our algorithm implies a polynomial-time algorithm for the network diversion problem on planar graphs, which resolves an open question from the literature. More generally, we show that Two-Sets Cut-Uncut remains fixed-parameter tractable even when parameterized by the number $r$ of faces in the plane graph covering the terminals $S \cup T$, by providing an algorithm of running time $4^{r + O(\sqrt r)} n^{O(1)}$.

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 time n^{O(k)} if the input n-vertex graph is given together with a tree decomposition of independence number k. Yolov, in [SODA 2018], gave an algorithm that, given an n-vertex graph G and an integer k, in time n^{O(k^3)} either constructs a tree decomposition of G whose independence number is O(k^3) or correctly reports that the tree-independence number of G is larger than k. In this paper, we first give an algorithm for computing the tree-independence number with a better approximation ratio and running time and then prove that our algorithm is, in some sense, the best one can hope for. More precisely, our algorithm runs in time 2^{O(k^2)} n^{O(k)} and either outputs a tree decomposition of G with independence number at most $8k$, or determines that the tree-independence number of G is larger than k. This implies 2^{O(k^2)} n^{O(k)}-time algorithms for various problems, like maximum weight independent set, parameterized by the tree-independence number k without needing the decomposition as an input. Assuming Gap-ETH, an n^{Ω(k)} factor in the running time is unavoidable for any approximation algorithm for the tree-independence number. Our second result is that the exact computation of the tree-independence number is para-NP-hard: We show that for every constant k \ge 4 it is NP-hard to decide if a given graph has the tree-independence number at most k.

A graph G contains a graph H as an induced minor if H can be obtained from G by vertex deletions and edge contractions. The class of H-induced-minor-free graphs generalizes the class of H-minor-free graphs, but unlike H-minor-free graphs, it can contain dense graphs. We show that if an n-vertex m-edge graph G does not contain a graph H as an induced minor, then it has a balanced vertex separator of size , where the OH(·)-notation hides factors depending on H. More precisely, our upper bound for the size of the balanced separator is . We give an algorithm for finding either an induced minor model of H in G or such a separator in randomized polynomial-time. We apply this to obtain subexponential time algorithms on H-induced-minor-free graphs for a large class of problems including maximum independent set, minimum feedback vertex set, 3-coloring, and planarization.

The classic technique of Baker [J. ACM ‘94] is the most fundamental approach for designing approximation schemes on planar, or more generally topologically-constrained graphs, and it has been applied in a myriad of different variants and settings throughout the last 30 years. In this work we propose a dynamic variant of Baker's technique, where instead of finding an approximate solution in a given static graph, the task is to design a data structure for maintaining an approximate solution in a fully dynamic graph, that is, a graph that is changing over time by edge deletions and edge insertions. Specifically, we address the two most basic problems — Maximum Weight Independent Set and Minimum Weight Dominating Set — and we prove the following: for a fully dynamic n-vertex planar graph G, one can

We give an algorithm that given a graph G with n vertices and m edges and an integer k, in time Ok(n1+o(1)) + O(m) either outputs a rank decomposition of G of width at most k or determines that the rankwidth of G is larger than k; the Ok(·)-notation hides factors depending on k. Our algorithm returns also a (2k+1−1)-expression for cliquewidth, yielding a (2k+1−1)-approximation algorithm for cliquewidth with the same running time. This improves upon the Ok(n2) time algorithm of Fomin and Korhonen [STOC 2022].

Abstract. Branchwidth determines how graphs and, more generally, arbitrary connectivity (symmetric and submodular) functions can be decomposed into a tree-like structure by specific cuts. We develop a general framework for designing fixed-parameter tractable 2-approximation algorithms for branchwidth of connectivity functions. The first ingredient of our framework is combinatorial. We prove a structural theorem establishing that either a sequence of particular refinement operations can decrease the width of a branch decomposition or the width of the decomposition is already within a factor of 2 from the optimum. The second ingredient is an efficient implementation of the refinement operations for branch decompositions that support efficient dynamic programming. We present two concrete applications of our general framework. The first is an algorithm that, for a given [Formula: see text]-vertex graph [Formula: see text] and integer [Formula: see text], in time [Formula: see text] either constructs a rank decomposition of [Formula: see text] of width at most [Formula: see text] or concludes that the rankwidth of [Formula: see text] is more than [Formula: see text]. It also yields a [Formula: see text]-approximation algorithm for cliquewidth within the same time complexity, which in turn improves to [Formula: see text] the running times of various algorithms on graphs of cliquewidth [Formula: see text]. Breaking the “cubic barrier” for rankwidth and cliquewidth was an open problem in the area. The second application is an algorithm that, for a given [Formula: see text]-vertex graph [Formula: see text] and integer [Formula: see text], in time [Formula: see text] either constructs a branch decomposition of [Formula: see text] of width at most [Formula: see text] or concludes that the branchwidth of [Formula: see text] is more than [Formula: see text]. This improves over the 3-approximation that follows from the recent treewidth 2-approximation of Korhonen [FOCS 2021].

We introduce the following submodular generalization of the Shortest Cycle problem. For a nonnegative monotone submodular cost function f defined on the edges (or the vertices) of an undirected graph G , we seek for a cycle C in G of minimum cost 𝖮𝖯𝖳 = f(C) . We give an algorithm that given an n -vertex graph G , parameter ɛ > 0, and the function f represented by an oracle, in time n 𝒪 (log 1/ɛ) finds a cycle C in G with f(C) ≤ (1+ɛ). 𝖮𝖯𝖳. This is in sharp contrast with the non-approximability of the closely related Monotone Submodular Shortest ( s,t -Path problem, which requires exponentially many queries to the oracle for finding an n 2/3-ɛ -approximation Goel et al. [ 7 ], FOCS 2009. We complement our algorithm with a matching lower bound. We show that for every ɛ > 0, obtaining a (1+ɛ)-approximation requires at least n Ω (log 1/ ɛ) queries to the oracle. When the function f is integer-valued, our algorithm yields that a cycle of cost 𝖮𝖯𝖳 can be found in time n 𝒪(log 𝖮𝖯𝖳) . In particular, for 𝖮𝖯𝖳 = n 𝒪(1) this gives a quasipolynomial-time algorithm computing a cycle of minimum submodular cost. Interestingly, while a quasipolynomial-time algorithm often serves as a good indication that a polynomial time complexity could be achieved, we show a lower bound that n 𝒪(log n ) queries are required even when 𝖮𝖯𝖳= 𝒪( n ). We also consider special cases of monotone submodular functions, corresponding to the number of different color classes needed to cover a cycle in an edge-colored multigraph G . For special cases of the corresponding minimization problem, we obtain fixed-parameter tractable algorithms and polynomial-time algorithms, when restricted to certain classes of inputs.

We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is as follows. We give a randomized algorithm, that given a colored \(n\) -vertex undirected graph, vertices \(s\) and \(t\) , and an integer \(k\) , finds an \((s,t)\) -path containing at least \(k\) different colors in time \(2^{k}n^{\mathcal{O}(1)}\) . This is the first FPT algorithm for this problem, and it generalizes the algorithm of Björklund, Husfeldt, and Taslaman on finding a path through \(k\) specified vertices. It also implies the first \(2^{k}n^{\mathcal{O}(1)}\) time algorithm for finding an \((s,t)\) -path of length at least \(k\) . Our method yields FPT algorithms for even more general problems. For example, we consider the problem where the input consists of an \(n\) -vertex undirected graph \(G\) , a matroid \(M\) whose elements correspond to the vertices of \(G\) and which is represented over a finite field of order \(q\) , a positive integer weight function on the vertices of \(G\) , two sets of vertices \(S,T\subseteq V(G)\) , and integers \(p,k,w\) , and the task is to find \(p\) vertex-disjoint paths from \(S\) to \(T\) so that the union of the vertices of these paths contains an independent set of \(M\) of cardinality \(k\) and weight \(w\) , while minimizing the sum of the lengths of the paths. We give a \(2^{p+\mathcal{O}(k^{2}\log(q+k))}n^{\mathcal{O}(1)}w\) time randomized algorithm for this problem.

We present a data structure that for a dynamic graph G that is updated by edge insertions and deletions, maintains a tree decomposition of G of width at most $6 k+5$ under the promise that the treewidth of G never grows above k. The amortized update time is $\mathcal{O}_{k}\left(2^{\sqrt{\log n} \log \log n}\right)$, where n is the vertex count of G and the $\mathcal{O}_{k}(\cdot)$ notation hides factors depending on k. In addition, we also obtain the dynamic variant of Courcelle’s Theorem: for any fixed property $\varphi$ expressible in the CMSO2logic, the data structure can maintain whether G satisfies $\varphi$ within the same time complexity bounds. To a large extent, this answers a question posed by Bodlaender [WG 1993].

A framework consists of an undirected graph $G$ and a matroid $M$ whose elements correspond to the vertices of $G$. Recently, Fomin et al. [SODA 2023] and Eiben et al. [ArXiV 2023] developed parameterized algorithms for computing paths of rank $k$ in frameworks. More precisely, for vertices $s$ and $t$ of $G$, and an integer $k$, they gave FPT algorithms parameterized by $k$ deciding whether there is an $(s,t)$-path in $G$ whose vertex set contains a subset of elements of $M$ of rank $k$. These algorithms are based on Schwartz-Zippel lemma for polynomial identity testing and thus are randomized, and therefore the existence of a deterministic FPT algorithm for this problem remains open. We present the first deterministic FPT algorithm that solves the problem in frameworks whose underlying graph $G$ is planar. While the running time of our algorithm is worse than the running times of the recent randomized algorithms, our algorithm works on more general classes of matroids. In particular, this is the first FPT algorithm for the case when matroid $M$ is represented over rationals. Our main technical contribution is the nontrivial adaptation of the classic irrelevant vertex technique to frameworks to reduce the given instance to one of bounded treewidth. This allows us to employ the toolbox of representative sets to design a dynamic programming procedure solving the problem efficiently on instances of bounded treewidth.

We introduce the following submodular generalization of the SHORTEST CYCLE problem. For a nonnegative monotone submodular cost function f defined on the edges (or the vertices) of an undirected graph G, we seek for a cycle C in G of minimum cost OPT = f(C). We give an algorithm that given an n-vertex graph G, parameter ε > 0, and the function f represented by an oracle, in time n

We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is a randomized algorithm, that given a colored n-vertex undirected graph, vertices s and t, and an integer k, finds an (s,t)-path containing at least k different colors in time 2kn

We show that there is no $2^{o(k^2)} n^{O(1)}$ time algorithm for Independent Set on $n$-vertex graphs with rank-width $k$, unless the Exponential Time Hypothesis (ETH) fails. Our lower bound matches the $2^{O(k^2)} n^{O(1)}$ time algorithm given by Bui-Xuan, Telle, and Vatshelle [Discret. Appl. Math., 2010] and it answers the open question of Bergougnoux and Kanté [SIAM J. Discret. Math., 2021]. We also show that the known $2^{O(k^2)} n^{O(1)}$ time algorithms for Weighted Dominating Set, Maximum Induced Matching and Feedback Vertex Set parameterized by rank-width $k$ are optimal assuming ETH. Our results are the first tight ETH lower bounds parameterized by rank-width that do not follow directly from lower bounds for $n$-vertex graphs.

We give an algorithm that takes as input an n-vertex graph G and an integer k, runs in time 2O(k2) nO(1), and outputs a tree decomposition of G of width at most k, if such a decomposition exists. This resolves the long-standing open problem of whether there is a 2o(k3) nO(1) time algorithm for treewidth. In particular, our algorithm is the first improvement on the dependency on k in algorithms for treewidth since the 2O(k3) nO(1) time algorithm given by Bodlaender and Kloks [ICALP 1991] and Lagergren and Arnborg [ICALP 1991].

Branchwidth determines how graphs, and more generally, arbitrary connectivity (basically symmetric and submodular) functions could be decomposed into a tree-like structure by specific cuts. We develop a general framework for designing fixed-parameter tractable (FPT) 2-approximation algorithms for branchwidth of connectivity functions. The first ingredient of our framework is combinatorial. We prove a structural theorem establishing that either a sequence of particular refinement operations could decrease the width of a branch decomposition or that the width of the decomposition is already within a factor of 2 from the optimum. The second ingredient is an efficient implementation of the refinement operations for branch decompositions that support efficient dynamic programming. We present two concrete applications of our general framework.

Abstract We consider problems that can be formulated as a task of finding an optimal triangulation of a graph w.r.t. some notion of optimality. We present algorithms parameterized by the size of a minimum edge clique cover ( $$\texttt {cc}$$ cc ) to such problems. This parameterization occurs naturally in many problems in this setting, e.g., in the perfect phylogeny problem $$\texttt {cc}$$ cc is at most the number of taxa, in fractional hypertreewidth $$\texttt {cc}$$ cc is at most the number of hyperedges, and in treewidth of Bayesian networks $$\texttt {cc}$$ cc is at most the number of non-root nodes. We show that the number of minimal separators of graphs is at most $$2^\texttt {cc}$$ 2cc , the number of potential maximal cliques is at most $$3^\texttt {cc}$$ 3cc , and these objects can be listed in times $$O^*(2^\texttt {cc})$$ O∗(2cc) and $$O^*(3^\texttt {cc})$$ O∗(3cc) , respectively, even when no edge clique cover is given as input; the $$O^*(\cdot )$$ O∗(·) notation omits factors polynomial in the input size. These enumeration algorithms imply $$O^*(3^\texttt {cc})$$ O∗(3cc) time algorithms for problems such as treewidth, weighted minimum fill-in, and feedback vertex set. For generalized and fractional hypertreewidth we give $$O^*(4^m)$$ O∗(4m) time and $$O^*(3^m)$$ O∗(3m) time algorithms, respectively, wheremis the number of hyperedges. When an edge clique cover of size $$\texttt {cc}'$$ cc′ is given as a part of the input we give $$O^*(2^{\texttt {cc}'})$$ O∗(2cc′) time algorithms for treewidth, minimum fill-in, and chordal sandwich. This implies an $$O^*(2^n)$$ O∗(2n) time algorithm for perfect phylogeny, wherenis the number of taxa. We also give polynomial space algorithms with time complexities $$O^*(9^{\texttt {cc}'})$$ O∗(9cc′) and $$O^*(9^{\texttt {cc}+ O(\log ^2 \texttt {cc})})$$ O∗(9cc+O(log2cc)) for problems in this framework.

Peer reviewed

We give an algorithm, that given an n-vertex graph$G$and an integer k, in time 2O(k)n either outputs a tree decomposition of$G$of width at most 2k + 1 or determines that the treewidth of$G$is larger than k. This is the first 2-approximation algorithm for treewidth that is faster than the known exact algorithms. In particular, our algorithm improves upon both the previous best approximation ratio of 5 in time 2O(k)n and the previous best approximation ratio of 3 in time 2O(k)nO(1), both given by Bodlaender et al. [FOCS 2013, SICOMP 2016]. Our algorithm is based on a local improvement method adapted from a proof of Bellenbaum and Diestel [Comb. Probab. Comput. 2002].

We prove lower bounds on pure dynamic programming algorithms for maximum weight independent set (MWIS). We model such algorithms as tropical circuits, i.e., circuits that compute with $\max$ and $+$ operations. For a graph $G$, an MWIS-circuit of $G$ is a tropical circuit whose inputs correspond to vertices of $G$ and which computes the weight of a maximum weight independent set of $G$ for any assignment of weights to the inputs. We show that if $G$ has treewidth $w$ and maximum degree $d$, then any MWIS-circuit of $G$ has $2^{Ω(w/d)}$ gates and that if $G$ is planar, or more generally $H$-minor-free for any fixed graph $H$, then any MWIS-circuit of $G$ has $2^{Ω(w)}$ gates. An MWIS-formula is an MWIS-circuit where each gate has fan-out at most one. We show that if $G$ has treedepth $t$ and maximum degree $d$, then any MWIS-formula of $G$ has $2^{Ω(t/d)}$ gates. It follows that treewidth characterizes optimal MWIS-circuits up to polynomials for all bounded degree graphs and $H$-minor-free graphs, and treedepth characterizes optimal MWIS-formulas up to polynomials for all bounded degree graphs.

Many graph problems can be formulated as a task of finding an optimal triangulation of a given graph with respect to some notion of optimality. In this paper we give algorithms to such problems parameterized by the size of a minimum edge clique cover (cc) of the graph. The parameter cc is both natural and well-motivated in many problems on this setting. For example, in the perfect phylogeny problem cc is at most the number of taxa, in fractional hypertreewidth cc is at most the number of hyperedges, and in treewidth of Bayesian networks cc is at most the number of non-root nodes of the Bayesian network. Our results are based on the framework of potential maximal cliques. We show that the number of minimal separators of graphs is at most 2^cc and the number of potential maximal cliques is at most 3^cc. Furthermore, these objects can be listed in times O^*(2^cc) and O^*(3^cc), respectively, even when no edge clique cover is given as input; the O^*(⋅) notation omits factors polynomial in the input size. Using these enumeration algorithms we obtain O^*(3^cc) time algorithms for problems in the potential maximal clique framework, including for example treewidth, minimum fill-in, and feedback vertex set. We also obtain an O^*(3^m) time algorithm for fractional hypertreewidth, where m is the number of hyperedges. In the case when an edge clique cover of size cc' is given as an input we further improve the time complexity to O^*(2^cc') for treewidth, minimum fill-in, and chordal sandwich. This implies an O^*(2^n) time algorithm for perfect phylogeny, where n is the number of taxa. We also give polynomial space algorithms with time complexities O^*(9^cc') and O^*(9^(cc + O(log^2 cc))) for problems in this framework.

We describe SMS, our submission to the exact treedepth track of PACE 2020. SMS computes the treedepth of a graph by branching on the Small Minimal Separators of the graph.

The Bouchitté-Todinca algorithm (BT), operating dynamic programming over the so-called potential maximal cliques (PMCs), yields a practically efficient approach to treewidth and generalized hypertreewidth. The enumeration of PMCs is a scalability bottleneck for BT in practice. We propose the use of declarative solvers for PMC enumeration as a substitute for the specialized PMC enumeration algorithms employed in current BT implementations. The presented Boolean satisfiability (SAT) and answer set programming (ASP) based PMC enumeration approaches open up new possibilities for improving the efficiency of BT in practice.