Magnus Wahlström
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Magnus Wahlström has a total of 102 co-authors. Here are the top co-authors by number of shared publications:
- Marcin Pilipczuk
Institute of Informatics, University of Warsaw, Poland
15 shared publications Stefan Kratsch
Humboldt-Universität zu Berlin, Germany
15 shared publicationsGregory Gutin
Royal Holloway, University of London, Egham, Surrey, UK
13 shared publications- Gregory Gutin
Department of Computer Science School of Math- ematical Sciences and LPMC Royal Holloway University of London Nankai University
10 shared publications Benjamin Doerr
Ecole Polytechnique de Paris
7 shared publications- Michał Pilipczuk
University of Warsaw, Warsaw, Poland
7 shared publications
Latest Publications
- Open Access
- 3 February 2026
- Published by Elsevier in SSRN Electronic Journal
Kernelization for list H-coloring for graphs with small vertex cover
For two graphs $G$ and $H$, a \emph{homomorphism} from $G$ to $H$ is a mapping$\varphi \colon V(G) \to V(H)$ such that edges of $G$ map to edges of $H$.Additionally, given a list $\cL(v) \subseteq V(H)$ for every vertex $v \in V(G)$,a \emph{list homomorphism} from $(G,\cL)$ to $H$ is a homomorphism $\varphi$from $G$ to $H$ such that for every vertex $v \in V(G)$, it holds that $\varphi(v) \in \cL(v)$. \textsc{List $H$-Coloring} is then the following problem: For a fixed graph $H$,given $(G,\cL)$ as input, is there a list homomorphism from $(G,\cL)$ to $H$? Note that if $H$ is the complete graph on $q$ vertices, the problem is equivalent to \textsc{List $q$-Coloring}. We investigate the kernelization properties of \textsc{List $H$-Coloring} parameterized by the vertex cover number of $G$. That is, given an instance $(G,\cL)$ and a vertex cover of $G$ of size $k$, can we reduce $(G,\cL)$ to an equivalent instance $(G',\cL')$ of \textsc{List $H$-Coloring} where the size of $G'$ is bounded by a low-degree polynomial $p(k)$ in $k$? This question has been investigated previously by Jansen and Pieterse [Algorithmica 2019], who provided an upper bound, which turns out to be optimal if $H$ is a complete graph, i.e., for \textsc{List $q$-Coloring}. This result was one of the first surprising applications of the method of kernelization via bounded-degree polynomials. More generally, the kernelization of \textsc{List $H$-Coloring} parameterized by $k$ turns out to be equivalent to the kernelization of a related CSP (constraint satisfaction problem) on domain $V(H)$, parameterized by the number of variables; the limits of kernelization for CSPs under this parameter is an important but poorly understood question. We define two new integral graph invariants, denoted by $c^*(H)$ and $d^*(H)$, with $d^*(H) \leq c^*(H) \leq d^*(H)+1$, and show that the following hold. \begin{itemize} \item For every graph $H$, \textsc{List $H$-Coloring} has a kernel with $\mathcal{O}(k^{c^*(H)})$ vertices, hence size $\mathcal{O}(k^{c^*(H)} \log k)$, via a simple marking scheme. \item For every graph $H$, there is no kernel of size $\mathcal{O}(k^{d^*(H)-\varepsilon})$ for any $\varepsilon > 0$, unless the polynomial hierarchy collapses. \item Furthermore, if $c^*(H) > d^*(H)$, then there is a kernel with $\mathcal{O}(k^{c^*(H)-\varepsilon})$ vertices where $\varepsilon \geq 2^{1-c^*(H)}$. \end{itemize} Additionally, we show that for some classes of graphs, including powers of cycles and graphs $H$ where $\Delta(H) \leq c^*(H)$ (which in particular includes cliques), the bound $d^*(H)$ is tight, i.e., there is a kernel with $\mathcal{O}(k^{d^*(H)})$ vertices using the polynomial method. We conjecture that this holds in general.- 3 February 2026
- Published by Elsevier in SSRN Electronic Journal
Open AccessKernelization for list H-coloring for graphs with small vertex cover
For two graphs $G$ and $H$, a \emph{homomorphism} from $G$ to $H$ is a mapping$\varphi \colon V(G) \to V(H)$ such that edges of $G$ map to edges of $H$.Additionally, given a list $\cL(v) \subseteq V(H)$ for every vertex $v \in V(G)$,a \emph{list homomorphism} from $(G,\cL)$ to $H$ is a homomorphism $\varphi$from $G$ to $H$ such that for every vertex $v \in V(G)$, it holds that $\varphi(v) \in \cL(v)$. \textsc{List $H$-Coloring} is then the following problem: For a fixed graph $H$,given $(G,\cL)$ as input, is there a list homomorphism from $(G,\cL)$ to $H$? Note that if $H$ is the complete graph on $q$ vertices, the problem is equivalent to \textsc{List $q$-Coloring}. We investigate the kernelization properties of \textsc{List $H$-Coloring} parameterized by the vertex cover number of $G$. That is, given an instance $(G,\cL)$ and a vertex cover of $G$ of size $k$, can we reduce $(G,\cL)$ to an equivalent instance $(G',\cL')$ of \textsc{List $H$-Coloring} where the size of $G'$ is bounded by a low-degree polynomial $p(k)$ in $k$? This question has been investigated previously by Jansen and Pieterse [Algorithmica 2019], who provided an upper bound, which turns out to be optimal if $H$ is a complete graph, i.e., for \textsc{List $q$-Coloring}. This result was one of the first surprising applications of the method of kernelization via bounded-degree polynomials. More generally, the kernelization of \textsc{List $H$-Coloring} parameterized by $k$ turns out to be equivalent to the kernelization of a related CSP (constraint satisfaction problem) on domain $V(H)$, parameterized by the number of variables; the limits of kernelization for CSPs under this parameter is an important but poorly understood question. We define two new integral graph invariants, denoted by $c^*(H)$ and $d^*(H)$, with $d^*(H) \leq c^*(H) \leq d^*(H)+1$, and show that the following hold. \begin{itemize} \item For every graph $H$, \textsc{List $H$-Coloring} has a kernel with $\mathcal{O}(k^{c^*(H)})$ vertices, hence size $\mathcal{O}(k^{c^*(H)} \log k)$, via a simple marking scheme. \item For every graph $H$, there is no kernel of size $\mathcal{O}(k^{d^*(H)-\varepsilon})$ for any $\varepsilon > 0$, unless the polynomial hierarchy collapses. \item Furthermore, if $c^*(H) > d^*(H)$, then there is a kernel with $\mathcal{O}(k^{c^*(H)-\varepsilon})$ vertices where $\varepsilon \geq 2^{1-c^*(H)}$. \end{itemize} Additionally, we show that for some classes of graphs, including powers of cycles and graphs $H$ where $\Delta(H) \leq c^*(H)$ (which in particular includes cliques), the bound $d^*(H)$ is tight, i.e., there is a kernel with $\mathcal{O}(k^{d^*(H)})$ vertices using the polynomial method. We conjecture that this holds in general. - Open Access
- 2 October 2025
- Published by Centre pour la Communication Scientifique Directe (CCSD) in TheoretiCS
- Vol. ume 4
Determinantal Sieving
We introduce determinantal sieving, a new, remarkably powerful tool in the toolbox of algebraic FPT algorithms. Given a polynomial $P(X)$ on a set of variables $X=\{x_1,\ldots,x_n\}$ and a linear matroid $M=(X,\mathcal{I})$ of rank $k$, both over a field $\mathbb{F}$ of characteristic 2, in $2^k$ evaluations we can sieve for those terms in the monomial expansion of $P$ which are multilinear and whose support is a basis for $M$. Alternatively, using $2^k$ evaluations of $P$ we can sieve for those monomials whose odd support spans $M$. Applying this framework, we improve on a range of algebraic FPT algorithms, such as: 1. Solving $q$-Matroid Intersection in time $O^*(2^{(q-2)k})$ and $q$-Matroid Parity in time $O^*(2^{qk})$, improving on $O^*(4^{qk})$ over general fields (Brand and Pratt, ICALP 2021) 2. Long $(s,t)$-Path in $O^*(1.66^k)$ time, improving on $O^*(2^k)$, and Rank $k$ $(S,T)$-Linkage in so-called frameworks in $O^*(2^k)$ time, improving on $O^*(2^{|S|+O(k^2 \log(k+|\mathbb{F}|))})$ over general fields (Fomin et al., SODA 2023). 3. Many instances of the Diverse X paradigm, finding a collection of $r$ solutions to a problem with a minimum mutual distance of $d$ in time $O^*(2^{r(r-1)d/2})$, improving solutions for $k$-Distinct Branchings from time $2^{O(k \log k)}$ to $O^*(2^k)$ (Bang-Jensen et al., ESA 2021), and for Diverse Perfect Matchings from $O^*(2^{2^{O(rd)}})$ to $O^*(2^{r^2d/2})$ (Fomin et al., STACS 2021). Here, all matroids are assumed to be represented over fields of characteristic 2. Over general fields, we achieve similar results at the cost of using exponential space by working over the exterior algebra. For a class of arithmetic circuits we call strongly monotone, this is even achieved without any loss of running time. However, the odd support sieving result appears to be specific to working over characteristic 2.75 pages. This is the TheoretiCS journal version- 2 October 2025
- Published by Centre pour la Communication Scientifique Directe (CCSD) in TheoretiCS
- Vol. ume 4
Open AccessDeterminantal Sieving
We introduce determinantal sieving, a new, remarkably powerful tool in the toolbox of algebraic FPT algorithms. Given a polynomial $P(X)$ on a set of variables $X=\{x_1,\ldots,x_n\}$ and a linear matroid $M=(X,\mathcal{I})$ of rank $k$, both over a field $\mathbb{F}$ of characteristic 2, in $2^k$ evaluations we can sieve for those terms in the monomial expansion of $P$ which are multilinear and whose support is a basis for $M$. Alternatively, using $2^k$ evaluations of $P$ we can sieve for those monomials whose odd support spans $M$. Applying this framework, we improve on a range of algebraic FPT algorithms, such as: 1. Solving $q$-Matroid Intersection in time $O^*(2^{(q-2)k})$ and $q$-Matroid Parity in time $O^*(2^{qk})$, improving on $O^*(4^{qk})$ over general fields (Brand and Pratt, ICALP 2021) 2. Long $(s,t)$-Path in $O^*(1.66^k)$ time, improving on $O^*(2^k)$, and Rank $k$ $(S,T)$-Linkage in so-called frameworks in $O^*(2^k)$ time, improving on $O^*(2^{|S|+O(k^2 \log(k+|\mathbb{F}|))})$ over general fields (Fomin et al., SODA 2023). 3. Many instances of the Diverse X paradigm, finding a collection of $r$ solutions to a problem with a minimum mutual distance of $d$ in time $O^*(2^{r(r-1)d/2})$, improving solutions for $k$-Distinct Branchings from time $2^{O(k \log k)}$ to $O^*(2^k)$ (Bang-Jensen et al., ESA 2021), and for Diverse Perfect Matchings from $O^*(2^{2^{O(rd)}})$ to $O^*(2^{r^2d/2})$ (Fomin et al., STACS 2021). Here, all matroids are assumed to be represented over fields of characteristic 2. Over general fields, we achieve similar results at the cost of using exponential space by working over the exterior algebra. For a class of arithmetic circuits we call strongly monotone, this is even achieved without any loss of running time. However, the odd support sieving result appears to be specific to working over characteristic 2.75 pages. This is the TheoretiCS journal version - Open Access
- 8 September 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 21 (4) , 1-55
Almost Consistent Systems of Linear Equations
Checking whether a system of linear equations is consistent is a basic computational problem with ubiquitous applications. When dealing with inconsistent systems, one may seek an assignment that minimises the number of unsatisfied equations. This problem is NP-hard and UGC-hard to approximate within any constant even for two-variable equations over the two-element field. We study this problem from the point of view of parameterized complexity, with the parameter being the number of unsatisfied equations. We consider equations defined over a family of commutative domains (i.e. rings without zero divisors) with a particular Helly property. This set contains, for instance, finite and infinite fields, the ring of integers and univariate polynomial rings with coefficients from a field; more generally, it contains the important class of Prüfer domains. We show that if every equation contains at most two variables, the problem is fixed-parameter tractable. This generalises many eminent graph separation problems such as Bipartization, Multiway Cut and Multicut parameterized by the size of the cutset. To complement this, we show that the problem is W[1]-hard when three or more variables are allowed in an equation, as well as for many commutative rings that are not covered by our fpt result. On the technical side, we introduce the notion of important balanced subgraphs, generalising the important separators of Marx to the setting of biased graphs. Furthermore, we use recent results of Kim, Kratsch, Pilipczuk and Wahlström on parameterized MinCSP to efficiently solve a generalisation of Multicut with disjunctive cut requests.
- 8 September 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 21 (4) , 1-55
Open AccessAlmost Consistent Systems of Linear Equations
Checking whether a system of linear equations is consistent is a basic computational problem with ubiquitous applications. When dealing with inconsistent systems, one may seek an assignment that minimises the number of unsatisfied equations. This problem is NP-hard and UGC-hard to approximate within any constant even for two-variable equations over the two-element field. We study this problem from the point of view of parameterized complexity, with the parameter being the number of unsatisfied equations. We consider equations defined over a family of commutative domains (i.e. rings without zero divisors) with a particular Helly property. This set contains, for instance, finite and infinite fields, the ring of integers and univariate polynomial rings with coefficients from a field; more generally, it contains the important class of Prüfer domains. We show that if every equation contains at most two variables, the problem is fixed-parameter tractable. This generalises many eminent graph separation problems such as Bipartization, Multiway Cut and Multicut parameterized by the size of the cutset. To complement this, we show that the problem is W[1]-hard when three or more variables are allowed in an equation, as well as for many commutative rings that are not covered by our fpt result. On the technical side, we introduce the notion of important balanced subgraphs, generalising the important separators of Marx to the setting of biased graphs. Furthermore, we use recent results of Kim, Kratsch, Pilipczuk and Wahlström on parameterized MinCSP to efficiently solve a generalisation of Multicut with disjunctive cut requests.
- 13 August 2025
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 54 (4) , 1065-1137
Flow-Augmentation III: Complexity Dichotomy for Boolean CSPs Parameterized by the Number of Unsatisfied Constraints
We study the parameterized problem of satisfying “almost all” constraints of a given formula [Formula: see text] over a fixed, finite Boolean constraint language [Formula: see text], with or without weights. More precisely, for each finite Boolean constraint language [Formula: see text], we consider the following two problems. In Min SAT([Formula: see text]), the input is a formula [Formula: see text] over [Formula: see text] and an integer [Formula: see text], and the task is to find an assignment [Formula: see text] that satisfies all but at most [Formula: see text] constraints of [Formula: see text], or determine that no such assignment exists. In Weighted Min SAT([Formula: see text]), the input additionally contains a weight function [Formula: see text] and an integer [Formula: see text], and the task is to find an assignment [Formula: see text] such that (1) [Formula: see text] satisfies all but at most [Formula: see text] constraints of [Formula: see text], and (2) the total weight of the violated constraints is at most [Formula: see text]. We give a complete dichotomy for the fixed-parameter tractability of these problems: We show that for every Boolean constraint language [Formula: see text], either Weighted Min SAT([Formula: see text]) is [Formula: see text]; or Weighted Min SAT([Formula: see text]) is [Formula: see text]-hard but Min SAT([Formula: see text]) is [Formula: see text]; or Min SAT([Formula: see text]) is [Formula: see text]-hard. This generalizes recent work of Kim et al. [in SODA 2021, SIAM, Philadelphia, 2021, pp. 149–168], which did not consider weighted problems and only considered languages [Formula: see text] that cannot express implications [Formula: see text] (as is used to, e.g., model digraph cut problems). Our result generalizes and subsumes multiple previous results, including the FPT algorithms for Weighted Almost 2-SAT, weighted and unweighted [Formula: see text]-Chain SAT, and Coupled Min-Cut, as well as weighted and directed versions of the latter. The main tool used in our algorithms is the recently developed method of directed flow-augmentation [E. J. Kim et al., in STOC 2022, ACM, 2022, pp. 938–947].
- 13 August 2025
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 54 (4) , 1065-1137
Flow-Augmentation III: Complexity Dichotomy for Boolean CSPs Parameterized by the Number of Unsatisfied Constraints
We study the parameterized problem of satisfying “almost all” constraints of a given formula [Formula: see text] over a fixed, finite Boolean constraint language [Formula: see text], with or without weights. More precisely, for each finite Boolean constraint language [Formula: see text], we consider the following two problems. In Min SAT([Formula: see text]), the input is a formula [Formula: see text] over [Formula: see text] and an integer [Formula: see text], and the task is to find an assignment [Formula: see text] that satisfies all but at most [Formula: see text] constraints of [Formula: see text], or determine that no such assignment exists. In Weighted Min SAT([Formula: see text]), the input additionally contains a weight function [Formula: see text] and an integer [Formula: see text], and the task is to find an assignment [Formula: see text] such that (1) [Formula: see text] satisfies all but at most [Formula: see text] constraints of [Formula: see text], and (2) the total weight of the violated constraints is at most [Formula: see text]. We give a complete dichotomy for the fixed-parameter tractability of these problems: We show that for every Boolean constraint language [Formula: see text], either Weighted Min SAT([Formula: see text]) is [Formula: see text]; or Weighted Min SAT([Formula: see text]) is [Formula: see text]-hard but Min SAT([Formula: see text]) is [Formula: see text]; or Min SAT([Formula: see text]) is [Formula: see text]-hard. This generalizes recent work of Kim et al. [in SODA 2021, SIAM, Philadelphia, 2021, pp. 149–168], which did not consider weighted problems and only considered languages [Formula: see text] that cannot express implications [Formula: see text] (as is used to, e.g., model digraph cut problems). Our result generalizes and subsumes multiple previous results, including the FPT algorithms for Weighted Almost 2-SAT, weighted and unweighted [Formula: see text]-Chain SAT, and Coupled Min-Cut, as well as weighted and directed versions of the latter. The main tool used in our algorithms is the recently developed method of directed flow-augmentation [E. J. Kim et al., in STOC 2022, ACM, 2022, pp. 938–947].
- Open Access
FPT algorithms over linear delta-matroids with applications
Matroids, particularly linear ones, have been a powerful tool in parameterized complexity for algorithms and kernelization. They have sped up or replaced dynamic programming. Delta-matroids generalize matroids by encapsulating structures such as non-maximum matchings in general graphs and various path-packing and topological configurations. Linear delta-matroids (represented by skew-symmetric matrices) offer significant expressive power and enable powerful algorithms. We investigate parameterized complexity aspects of problems defined over linear delta-matroids or with delta-matroid constraints. Our analysis of basic intersection and packing problems reveals a different complexity landscape compared to the familiar matroid case. In particular, there is a stark contrast between the cardinality parameter $k$ and the rank parameter $r$. For example, finding an intersection of size $k$ of three linear delta-matroids is W[1]-hard when parameterized by $k$, while more general problems (e.g., finding a set packing of size $k$ feasible in a linear delta-matroid) are FPT when parameterized by $r$. We extend the recent determinantal sieving procedure of Eiben, Koana and Wahlström (SODA 2024) to sieve a polynomial for a monomial whose support is feasible in a linear delta-matroid by $r$. Second, we investigate a class of problems that remains FPT when parameterized by $k$, even on delta-matroids of unbounded rank. We begin with Delta-matroid Triangle Cover - finding a feasible set of size $k$ that can be covered by a vertex-disjoint packing of triangles (sets of size 3) from a given collection. This approach allows us to find a packing of $K_3$'s and $K_2$'s in a graph with a maximum number of edges, parameterized above the matching number. As applications, we settle questions on the FPT status of Cluster Subgraph and Strong Triadic Closure parameterized above the matching number.Open AccessFPT algorithms over linear delta-matroids with applications
Matroids, particularly linear ones, have been a powerful tool in parameterized complexity for algorithms and kernelization. They have sped up or replaced dynamic programming. Delta-matroids generalize matroids by encapsulating structures such as non-maximum matchings in general graphs and various path-packing and topological configurations. Linear delta-matroids (represented by skew-symmetric matrices) offer significant expressive power and enable powerful algorithms. We investigate parameterized complexity aspects of problems defined over linear delta-matroids or with delta-matroid constraints. Our analysis of basic intersection and packing problems reveals a different complexity landscape compared to the familiar matroid case. In particular, there is a stark contrast between the cardinality parameter $k$ and the rank parameter $r$. For example, finding an intersection of size $k$ of three linear delta-matroids is W[1]-hard when parameterized by $k$, while more general problems (e.g., finding a set packing of size $k$ feasible in a linear delta-matroid) are FPT when parameterized by $r$. We extend the recent determinantal sieving procedure of Eiben, Koana and Wahlström (SODA 2024) to sieve a polynomial for a monomial whose support is feasible in a linear delta-matroid by $r$. Second, we investigate a class of problems that remains FPT when parameterized by $k$, even on delta-matroids of unbounded rank. We begin with Delta-matroid Triangle Cover - finding a feasible set of size $k$ that can be covered by a vertex-disjoint packing of triangles (sets of size 3) from a given collection. This approach allows us to find a packing of $K_3$'s and $K_2$'s in a graph with a maximum number of edges, parameterized above the matching number. As applications, we settle questions on the FPT status of Cluster Subgraph and Strong Triadic Closure parameterized above the matching number. - Open Access
- 24 January 2025
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 72 (1) , 1-38
Flow-augmentation I: Directed graphs
We show a flow-augmentation algorithm in directed graphs: There exists a randomized polynomial-time algorithm that, given a directed graph G , two vertices s, t ∈ V(G) , and an integer k , adds (randomly) to G a number of arcs such that for every minimal st -cut Z in G of size at most k , with probability 2 −poly( k ) the set Z becomes a minimum st -cut in the resulting graph. We also provide a deterministic counterpart of this procedure. The directed flow-augmentation tool allows us to prove fixed-parameter tractability of a number of problems parameterized by the cardinality of the deletion set whose parameterized complexity status was repeatedly posed as open problems: Chain SAT , defined by Chitnis, Egri, and Marx [ESA’13, Algorithmica’17], a number of weighted variants of classic directed cut problems, such as Weighted st - Cut or Weighted Directed Feedback Vertex Set . By proving that Chain SAT is FPT, we confirm a conjecture of Chitnis, Egri, and Marx that, for any graph H , if the List H - Coloring problem is polynomial-time solvable, then the corresponding vertex-deletion problem is fixed-parameter tractable.
- 24 January 2025
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 72 (1) , 1-38
Open AccessFlow-augmentation I: Directed graphs
We show a flow-augmentation algorithm in directed graphs: There exists a randomized polynomial-time algorithm that, given a directed graph G , two vertices s, t ∈ V(G) , and an integer k , adds (randomly) to G a number of arcs such that for every minimal st -cut Z in G of size at most k , with probability 2 −poly( k ) the set Z becomes a minimum st -cut in the resulting graph. We also provide a deterministic counterpart of this procedure. The directed flow-augmentation tool allows us to prove fixed-parameter tractability of a number of problems parameterized by the cardinality of the deletion set whose parameterized complexity status was repeatedly posed as open problems: Chain SAT , defined by Chitnis, Egri, and Marx [ESA’13, Algorithmica’17], a number of weighted variants of classic directed cut problems, such as Weighted st - Cut or Weighted Directed Feedback Vertex Set . By proving that Chain SAT is FPT, we confirm a conjecture of Chitnis, Egri, and Marx that, for any graph H , if the List H - Coloring problem is polynomial-time solvable, then the corresponding vertex-deletion problem is fixed-parameter tractable.
- Open Access
- 13 March 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 20 (2) , 1-26
Flow-augmentation II: Undirected Graphs
We present an undirected version of the recently introduced flow-augmentation technique: Given an undirected multigraph G with distinguished vertices s,t ∈ V(G) and an integer k , one can in randomized k ????(1) ⋅ (|V(G)| + |E(G)|) time sample a set A ⊆ \(\binom{V(G)}{2}\) such that the following holds: for every inclusion-wise minimal st -cut Z in G of cardinality at most k , Z becomes a minimum-cardinality cut between s and t in G+A (i.e., in the multigraph G with all edges of A added) with probability 2 -????( k log k ). Compared to the version for directed graphs [STOC 2022], the version presented here has improved success probability (2 -????( k log k ) instead of 2 -𝒪( k 4 log k ) ), linear dependency on the graph size in the running time bound, and an arguably simpler proof. An immediate corollary is that the Bi-objective st -Cut problem can be solved in randomized FPT time 2 ????( k log k ) (|V(G)|+|E(G)|) on undirected graphs.- 13 March 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 20 (2) , 1-26
Open AccessFlow-augmentation II: Undirected Graphs
We present an undirected version of the recently introduced flow-augmentation technique: Given an undirected multigraph G with distinguished vertices s,t ∈ V(G) and an integer k , one can in randomized k ????(1) ⋅ (|V(G)| + |E(G)|) time sample a set A ⊆ \(\binom{V(G)}{2}\) such that the following holds: for every inclusion-wise minimal st -cut Z in G of cardinality at most k , Z becomes a minimum-cardinality cut between s and t in G+A (i.e., in the multigraph G with all edges of A added) with probability 2 -????( k log k ). Compared to the version for directed graphs [STOC 2022], the version presented here has improved success probability (2 -????( k log k ) instead of 2 -𝒪( k 4 log k ) ), linear dependency on the graph size in the running time bound, and an arguably simpler proof. An immediate corollary is that the Bi-objective st -Cut problem can be solved in randomized FPT time 2 ????( k log k ) (|V(G)|+|E(G)|) on undirected graphs. - Open Access
Faster algorithms on linear delta-matroids
We show new algorithms and constructions over linear delta-matroids. We observe an alternative representation for linear delta-matroids, as a contraction representation over a skew-symmetric matrix. This is equivalent to the more standard "twist representation" up to $O(n^ω)$-time transformations, but is much more convenient for algorithmic tasks. For instance, the problem of finding a max-weight feasible set now reduces directly to the problem of finding a max-weight basis in a linear matroid. Supported by this representation, we provide new algorithms and constructions over linear delta-matroids. We show that the union and delta-sum of linear delta-matroids define linear delta-matroids, and a representation for the resulting delta-matroid can be constructed in randomized time $O(n^ω)$. Previously, it was only known that these operations define delta-matroids. We also note that every projected linear delta-matroid can be represented as an elementary projection. This implies that several optimization problems over (projected) linear delta-matroids, including the coverage, delta-coverage, and parity problems, reduce (in their decision versions) to a single $O(n^ω)$-time matrix rank computation. Using the methods of Harvey, previously used by Cheung, Lao and Leung for linear matroid parity, we furthermore show how to solve the search versions in the same time. This improves on the $O(n^4)$-time augmenting path algorithm of Geelen, Iwata and Murota. Finally, we consider the maximum-cardinality delta-matroid intersection problem. Using Storjohann's algorithms for symbolic determinants, we show that such a solution can be found in $O(n^{ω+1})$ time. This is the first polynomial-time algorithm for the problem, solving an open question of Kakimura and Takamatsu.Open AccessFaster algorithms on linear delta-matroids
We show new algorithms and constructions over linear delta-matroids. We observe an alternative representation for linear delta-matroids, as a contraction representation over a skew-symmetric matrix. This is equivalent to the more standard "twist representation" up to $O(n^ω)$-time transformations, but is much more convenient for algorithmic tasks. For instance, the problem of finding a max-weight feasible set now reduces directly to the problem of finding a max-weight basis in a linear matroid. Supported by this representation, we provide new algorithms and constructions over linear delta-matroids. We show that the union and delta-sum of linear delta-matroids define linear delta-matroids, and a representation for the resulting delta-matroid can be constructed in randomized time $O(n^ω)$. Previously, it was only known that these operations define delta-matroids. We also note that every projected linear delta-matroid can be represented as an elementary projection. This implies that several optimization problems over (projected) linear delta-matroids, including the coverage, delta-coverage, and parity problems, reduce (in their decision versions) to a single $O(n^ω)$-time matrix rank computation. Using the methods of Harvey, previously used by Cheung, Lao and Leung for linear matroid parity, we furthermore show how to solve the search versions in the same time. This improves on the $O(n^4)$-time augmenting path algorithm of Geelen, Iwata and Murota. Finally, we consider the maximum-cardinality delta-matroid intersection problem. Using Storjohann's algorithms for symbolic determinants, we show that such a solution can be found in $O(n^{ω+1})$ time. This is the first polynomial-time algorithm for the problem, solving an open question of Kakimura and Takamatsu. - 8 January 2024
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 38 (1) , 170-189
On Weighted Graph Separation Problems and Flow Augmentation
One of the first applications of the recently introduced technique of flow augmentation [Kim et al., STOC 2022] is a fixed-parameter algorithm for the weighted version of Directed Feedback Vertex Set, a landmark problem in parameterized complexity. In this article, we explore the applicability of flow augmentation to other weighted graph separation problems parameterized by the size of the cutset. We show the following: In weighted undirected graphs, Multicut is fixed-parameter tractable (FPT) in both the edge- and the vertex-deletion version. The weighted version of Group Feedback Vertex Set is FPT, even with oracle access to group operations. The weighted version of Directed Subset Feedback Vertex Set is FPT. Our study reveals Directed Symmetric Multicut as the next important graph separation problem whose parameterized complexity remains unknown, even in the unweighted setting.
- 8 January 2024
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 38 (1) , 170-189
On Weighted Graph Separation Problems and Flow Augmentation
One of the first applications of the recently introduced technique of flow augmentation [Kim et al., STOC 2022] is a fixed-parameter algorithm for the weighted version of Directed Feedback Vertex Set, a landmark problem in parameterized complexity. In this article, we explore the applicability of flow augmentation to other weighted graph separation problems parameterized by the size of the cutset. We show the following: In weighted undirected graphs, Multicut is fixed-parameter tractable (FPT) in both the edge- and the vertex-deletion version. The weighted version of Group Feedback Vertex Set is FPT, even with oracle access to group operations. The weighted version of Directed Subset Feedback Vertex Set is FPT. Our study reveals Directed Symmetric Multicut as the next important graph separation problem whose parameterized complexity remains unknown, even in the unweighted setting.
- Open Access
Parameterized Complexity of Equality MinCSP
We study the parameterized complexity of MinCSP for so-called equality languages, i.e., for finite languages over an infinite domain such as $\mathbb{N}$, where the relations are defined via first-order formulas whose only predicate is $=$. This is an important class of languages that forms the starting point of all study of infinite-domain CSPs under the commonly used approach pioneered by Bodirsky, i.e., languages defined as reducts of finitely bounded homogeneous structures. Moreover, MinCSP over equality languages forms a natural class of optimisation problems in its own right, covering such problems as Edge Multicut, Steiner Multicut and (under singleton expansion) Edge Multiway Cut. We classify MinCSP$(Γ)$ for every finite equality language $Γ$, under the natural parameter, as either FPT, W[1]-hard but admitting a constant-factor FPT-approximation, or not admitting a constant-factor FPT-approximation unless FPT=W[2]. In particular, we describe an FPT case that slightly generalises Multicut, and show a constant-factor FPT-approximation for Disjunctive Multicut, the generalisation of Multicut where the ``cut requests'' come as disjunctions over $d = O(1)$ individual cut requests $s_i \neq t_i$. We also consider singleton expansions of equality languages, i.e., enriching an equality language with the capability for assignment constraints $(x=i)$ for either finitely or infinitely many constants $i \in \mathbb{N}$, and fully characterize the complexity of the resulting MinCSP.Open AccessParameterized Complexity of Equality MinCSP
We study the parameterized complexity of MinCSP for so-called equality languages, i.e., for finite languages over an infinite domain such as $\mathbb{N}$, where the relations are defined via first-order formulas whose only predicate is $=$. This is an important class of languages that forms the starting point of all study of infinite-domain CSPs under the commonly used approach pioneered by Bodirsky, i.e., languages defined as reducts of finitely bounded homogeneous structures. Moreover, MinCSP over equality languages forms a natural class of optimisation problems in its own right, covering such problems as Edge Multicut, Steiner Multicut and (under singleton expansion) Edge Multiway Cut. We classify MinCSP$(Γ)$ for every finite equality language $Γ$, under the natural parameter, as either FPT, W[1]-hard but admitting a constant-factor FPT-approximation, or not admitting a constant-factor FPT-approximation unless FPT=W[2]. In particular, we describe an FPT case that slightly generalises Multicut, and show a constant-factor FPT-approximation for Disjunctive Multicut, the generalisation of Multicut where the ``cut requests'' come as disjunctions over $d = O(1)$ individual cut requests $s_i \neq t_i$. We also consider singleton expansions of equality languages, i.e., enriching an equality language with the capability for assignment constraints $(x=i)$ for either finitely or infinitely many constants $i \in \mathbb{N}$, and fully characterize the complexity of the resulting MinCSP.