in $P_{12}$, which yields a shorter path between $t_{1}$ and $t_{2}$, which is
a contradiction to the assumption that $P_{12}$ is a shortest path. In
summary, we have a subpath $P^{\prime}_{12}$ of $P_{12}$ such that the
endpoints of $P^{\prime}_{12}$, that is, $x_{1},x_{2}\in\mathsf{Reach}(t)$,
and $\emptyset\neq I\subseteq V(C_{t})$. Now we consider different cases and
arrive at a contradiction.
Case (1a): $x_{1}$ and $x_{2}$ are in the same part $P\in\mathcal{P}$. Then
$P$ is contracted into a single vertex $v_{P}$ in $G_{2}$. This implies that
there is also a path between $t_{1}$ and $t_{2}$ in $G_{2}-\hat{X}_{2}$, which
is a contradiction.
Case (1b): $x_{1}$ and $x_{2}$ are in different parts $P_{1}$ and $P_{2}$
respectively, which are identified into the vertices $v_{1},v_{2}$ in $G_{1}$,
respectively. However, this implies that there is a path $P^{\prime}_{12}$
between $v_{1}$ and $v_{2}$ in $G_{1}-\hat{X}_{1}$, which contradicts that
$X_{1}$ is a solution for $\mathcal{J}_{1}$.

Case 2

Now, we analyze the case where $t\in\\{t_{1},t_{2}\\}$. WLOG, assume that
$t=t_{1}$; therefore, $P_{12}$ is the shortest path between $t$ and $t_{2}$ in
$G-\hat{X}$. In this case, as $t\in V(C_{t})$ the path $P_{12}$ must use a
vertex from $(V(C_{t})\setminus\\{t\\})\cup\mathsf{Reach}(t)$. In path
$P_{12}$, let $x_{2}$ denote the vertex in $\mathsf{Reach}(t)$ such that all
the internal vertices of the subpath connecting $x_{2}$ to $t$ along $P_{2}$
are from $V(C_{t})$. Now we consider different cases and arrive at a
contradiction.
Case (2a): $x_{2}$ and $t$ are in the same part $P\in\mathcal{P}$. Then it
follows that there is a path from $t_{2}$ to $v_{P}$ in $G-\hat{X_{2}}$, which
contradicts the assumption that $\hat{X_{2}}$ is a solution for
$\mathcal{J}_{2}$.
Case (2b): $t$ and $x_{2}$ are in different parts. Now, we note that there is
a path between $t$ and $x_{2}$ in
$G[V(C_{t})\cup\mathsf{Reach}(t)]-\hat{X_{1}}$, it contradicts the assumption
that $\hat{X_{1}}$ is a solution for $\mathcal{J}_{1}$.

This completes the claim.

Here is a simple observation.

######  Claim 13.

Consider any $O\in\mathcal{F}(T,k,G)$ such that $O\cap S=\emptyset$. Then,
there is some guess $(C_{t},\mathcal{P},k_{1})$ with which $O$ is compatible.

Assuming that $O\cap S=\emptyset$, we know that at least one of the components
$C_{s}$ or $C_{t}$ has a nonempty intersection with the vertices of $O$. Now
we obtain a guess that is compatible with $O$. Assume that $|V(C_{t})\cap
O|=k_{1}>0$. Let $\mathcal{P}$ be the partition of the vertices in
$\mathsf{Reach}(t)\cup\\{t\\}$ defined as follows. A pair of vertices $u$ and
$v$ from $\mathsf{Reach}(t)\cup\\{t\\}$ belongs to a different part if they
are not connected in the graph $G[V[C_{t}]\cup\mathsf{Reach}(t)]-O$ and the
graph $G-(V(C_{t})\cup O)$. It is easy to see that guess
$(C_{t},\mathcal{P},k_{1})$ is compatible with $O$.

Step 5: Return as output

We return no if each of the branching steps returns no to their corresponding
instance. Otherwise, we do the following. Notice that in each branching step,
we have at most $k+2(k-1)d_{k+1}=k^{\mathcal{O}(k)}$ many recursive calls,
where $d_{k+1}$ denotes the $(k+1)$ th Bell’s number: number of possible
partitions of a set of $(k+1)$ elements. First we take union of all the
solution sets corresponding to every recursive calls, specifically, we compute

$\mathcal{F}^{1}(T,k,G)\coloneqq\bigcup_{v\in
S}\mathcal{F}^{1}_{v}\cup\bigcup_{(C_{t},\mathcal{P},k_{1})\in{\cal
G}_{t}}\mathcal{F}^{1}(C_{t},\mathcal{P},k_{1})\cup\bigcup_{(C_{s},\mathcal{P},k_{1})\in{\cal
G}_{s}}\mathcal{F}^{1}(C_{t},\mathcal{P},k_{1}).$ (1)

Then we compute

$\mathcal{F}^{\prime}(T,k,G)\subseteq^{q}_{\text{rep}}\mathcal{F}^{1}(T,k,G)$
(2)

using Proposition 2.2 and return the set $\mathcal{F}^{\prime}(T,k,G)$ as the
output for the instance $\mathcal{J}=(G,\mathcal{M},T,Q,k,q)$.

This finishes the description of IMWCut.

##### Correctness.

######  Lemma 5.10 (Safeness of IMWCut).

Our branching algorithm returns the set
$\mathcal{F}^{\prime}(T,k,G)\subseteq^{q}_{\text{rep}}\mathcal{F}(T,k,G)$ of
size $2^{k+q}$.

######  Proof 5.11.

Recall that $\mathcal{F}(T,k,G)$ is the set of all minimal independent
multiway cuts for $T$ of size $k$ in $G$. First, we consider base case, then
the correctness follows from Claim 9. Now, suppose that neither of the base
cases is applicable. If the graph $G$ is disconnected, then again the
correctness of the algorithm follows directly from Claim 10. Hence, finally
let us consider the case when $G$ is connected, $k\geq 2$, and $|T|\geq 3$.
First, by Lemma 5.6, we either correctly conclude that
$\mathcal{J}=(G,\mathcal{M},T,Q,k,q)$ is a no-instance, or we find a strong
separator $S$ and a pair of components $C_{s},C_{t}$ in time $2^{k}\cdot
n^{\mathcal{O}(1)}$, such that for any minimal solution
$O\in\mathcal{F}(G,T,k)$ of size $k$, either (i) $S\cap O=\emptyset$, (ii)
$1\leq|C_{s}\cap O|\leq k-1$, or (iii) $1\leq|C_{t}\cap O|\leq k-1$. Further,
any $O$ satisfying (ii) (resp. (iii)) must be compatible with some guess
$(C_{t},\mathcal{P},k_{1})\in{\cal G}_{t}$ (resp.
$(C_{s},\mathcal{P},k_{1})\in{\cal G}_{s}$) (by claim 13). This implies that,

$\displaystyle\mathcal{F}(T,k,G)=\bigcup_{v\in S}\mathcal{F}(T,k,v,G)\ \cup$
$\displaystyle\bigcup_{(C_{t},\mathcal{P},k_{1})\in{\cal
G}_{t}}\mathcal{F}(T,k,G,C_{t},\mathcal{P},k_{1})$
$\displaystyle\cup\bigcup_{(C_{s},\mathcal{P},k_{1})\in{\cal
G}_{s}}\mathcal{F}(T,k,G,C_{s},\mathcal{P},k_{1}).$ (3)

Then, by Claims 11 and 12, it follows that
$\mathcal{F}^{1}(T,k,G)\subseteq^{q}_{\text{rep}}\mathcal{F}(T,k,G)$, where
the former is defined in (1). Then, since
$\mathcal{F}^{\prime}(T,k,G)\subseteq^{q}_{\text{rep}}\mathcal{F}^{1}(T,k,G)$
as computed in (2), by Proposition 2.3, it follows that
$\mathcal{F}^{\prime}(T,k,G)\subseteq^{q}_{\text{rep}}\mathcal{F}(T,k,G)$.
Finally, by Proposition 2.2, it follows that
$|\mathcal{F}^{\prime}(T,k,G)|\leq 2^{k+q}$.

##### Time analysis.

Note that in each of the recursive calls to our branching steps, the parameter
$k$ decreases by at least $1$. The number of partition of the vertices in $S$
is bounded by $k^{k}$. So the degree at each node of the branching tree is
bounded by $k^{\mathcal{O}(k)}$. In the base case where $|T|=2$ or $k=1$ we
found the corresponding solution in time $f(r,k)\cdot n^{\mathcal{O}(1)}$. The
number of nodes in the tree is bounded by $k^{\mathcal{O}(k)}$. Now we
calculate the running to find a solution to each node assuming that we have
all the solution to its child node. For this, we have to take union of at most
$(k+2(k-1)(k+1)^{k+1})^{k}$ many sets where the size of each set is at most
$\binom{k+q}{k}$. This union takes
$\binom{k+q}{k}\cdot(k+2(k-1)(k+1)^{k+1})^{k}$ time. Then finding the
$q$-representative set will take time $\binom{k+q}{k}$ using at most
$\mathcal{O}(|{\cal
A}|(\binom{k+q}{k})k^{\omega}+(\binom{k+q}{k})^{\omega-1})$ (by Proposition
2.2, where $\cal A$ is the size of the set after taking the union.

Hence, we have the following theorem.

######  Theorem 5.12.

There exists a deterministic algorithm for Generalized Independent Multiway
Cut that runs in time $f(r,k)\cdot n^{\mathcal{O}(1)}$, and outputs
$\mathcal{F}^{\prime}(T,k,G)\subseteq^{q}_{\text{rep}}\mathcal{F}(T,k,G)$ such
that $|\mathcal{F}^{\prime}(T,k,G)|=2^{k+q}$. Here $\mathcal{F}(T,k,G)$
denotes the set of all $k$ size multiway cuts for $T$ in $G$, assuming that
there is no independent multiway cut of size $k^{\prime}<k$.

##  6 Lower bound

In this section, we show an unconditional lower bound for the Independent
$(s,t)$-Cut problem when the input matroid is given by the independence
oracle. The proof is inspired by the reductions used for the similar
statements in [10, Theorem 1].

######  Theorem 6.1.

There is no algorithm solving Independent $(s,t)$-Cut with matroids of rank
$k$ represented by the independence oracles using $f(k)\cdot n^{o(k)}$ oracle
calls for any computable function $f$.

######  Proof 6.2.

Let $p$ and $q$ be positive integers. We construct the graph $G_{p,q}$ as
follows (see Figure 9).

  * •

Construct two vertices $s$ and $t$.

  * •

For each $i\in[p]$, construct a set $A_{i}=\\{a_{1}^{i},\ldots,a_{q}^{i}\\}$
of $q$ vertices and a set $B_{i}=\\{b_{1}^{i},\ldots,b_{q}^{i}\\}$ of $q$
vertices.

  * •

For each $i\in[p]$, make $s$ adjacent to $a_{1}^{i}$ and $b_{1}^{i}$, and make
$t$ adjacent to $a_{q}^{i}$ and $b_{q}^{i}$.

  * •

For each $i\in[p]$ and $j\in[q-1]$, make $a_{j}^{i}$ adjacent to $a_{j+1}^{i}$
and $b_{j+1}^{i}$, and make $b_{j}^{i}$ adjacent to $a_{j+1}^{i}$ and
$b_{j+1}^{i}$.

We have that $G_{pq}$ has $2pq+2$ vertices. Notice that each minimum
$(s,t)$-cut in $G_{p,q}$ has size $2p$ and is of form
$\bigcup_{i=1}^{p}\\{a_{j_{i}}^{i},b_{j_{i}}^{i}\\}$ for some
$j_{1},\ldots,j_{p}\in[q]$.

$a_{q}^{p}$$s$$t$$b_{1}^{1}$$a_{1}^{1}$$a_{2}^{1}$$b_{2}^{1}$$b_{q}^{1}$$a_{q}^{1}$$b_{1}^{p}$$b_{2}^{p}$$b_{q}^{p}$$a_{1}^{p}$$a_{2}^{p}$

Figure 9: Construction of $G_{p,q}$.

Consider a family of indices $j_{1},\ldots,j_{p}\in[q]$ and set
$W=\bigcup_{i=1}^{p}\\{a_{j_{i}}^{i},b_{j_{i}}^{i}\\}$. We define the matroid
$\mathcal{M}_{W}$ with the ground set $V(G_{p,q})$ where each independent set
is a subset of $V(G_{p,q})\setminus\\{s,t\\}$ as follows for $k=2p$:

  * •

Each set $X\subseteq V(G_{p,q})\setminus\\{s,t\\}$ of size at most $k-1$ is
independent and any set of size at least $k+1$ is not independent.

  * •

A set $X\subseteq V(G_{p,q})\setminus\\{s,t\\}$ of size $k$ is independent if
and only if either $X=W$ or there is $i\in\\{1,\ldots,p\\}$ such that
$|A_{i}\cap X|\geq 2$ or $|B_{i}\cap X|\geq 2$ or there are distinct
$h,j\in[q]$ such that $a_{h}^{i},b_{j}^{i}\in X$.

We denote by $\mathcal{I}_{W}$ the constructed family of independent sets. In
fact, $\mathcal{M}_{W}$ is the same as the matroid constructed in the proof of
[10, Theorem 1]. We provide the proof of the following claim showing that
$\mathcal{M}_{W}$ is a matroid for completeness even if it identical to the
proof of [10, Claim 1.1] in the proof of Theorem 1 therein.

######  Claim 14 ([10, Claim 1.1]).

$\mathcal{M}_{W}=(V(G_{p,q}),\mathcal{I}_{W})$ is a matroid of rank $k=2p$.

######  Proof 6.3 (Proof of Claim 14).

We have to verify that $\mathcal{I}_{W}$ satisfies the independence axioms
(1)–(3). The axioms (1) and (2) for $\mathcal{I}_{W}$ follow directly from the
definition of $\mathcal{I}_{W}$. To establish (3), consider arbitrary
$X,Y\in\mathcal{I}_{W}$ such that $|X|<|Y|$. If $|X|<k-1$ then for any $v\in
Y\setminus X$, $Z=X\cup\\{v\\}\in\mathcal{I}_{W}$ because $|Z|\leq k-1$.

Suppose $|X|=k-1$ and $|Y|=k$. If there is $i\in[p]$ such that $|A_{i}\cap
X|\geq 2$ or $|B_{i}\cap X|\geq 2$ or there are distinct $h,j\in[q]$ such that
$a_{h}^{i},b_{j}^{i}\in X$ then for any $v\in Y\setminus X$, the set
$Z=X\cup\\{v\\}$ has the same property and, therefore, $Z\in\mathcal{I}_{W}$.
Assume that this is not the case. By the construction of $G_{p,q}$, we have
that for each $i\in[p]$, $|X\cap A_{i}|\leq 1$ and $|X\cap B_{i}|\leq 1$, and,
furthermore, there is $j\in[q]$ such that $X\cap(A_{i}\cup
B_{i})\subseteq\\{a_{j}^{i},b_{j}^{i}\\}$. Because $|X|=k-1$, we can assume
without loss of generality that there are indices $h_{1},\ldots,h_{p}\in[q]$
such that $X\cap(A_{i}\cup B_{i})=\\{a_{h_{i}}^{i},b_{h_{i}}^{i}\\}$ for
$i\in[p]$ and $X\cap(A_{p}\cup B_{p})=\\{a_{h_{p}}^{p}\\}$. Recall that
$W=\bigcup_{i=1}^{p}\\{a_{j_{i}}^{i},b_{j_{i}}^{i}\\}$ for
$j_{1},\ldots,j_{p}\in[q]$. If there is $v\in Y\setminus X$ such that $v\neq
b_{j_{p}}^{p}$ then consider $Z=X\cup\\{v\\}$. We have that there is $i\in[p]$
such that $|A_{i}\cap Z|\geq 2$ or $|B_{i}\cap Z|\geq 2$ or there are distinct
$h,j\in[q]$ such that $a_{h}^{i},b_{j}^{i}\in Z$, that is,
$Z\in\mathcal{I}_{W}$. Now we assume that $Y\setminus X=\\{b_{j_{p}}^{p}\\}$.
Then $Y=W$ and we can take $v=b_{j_{p}}^{p}$. We obtain that
$X\cup\\{v\\}=Y\in\mathcal{I}_{W}$.

By the construction of $\mathcal{I}$, the rank of $\mathcal{M}$ is $k$. This
concludes the proof.

We show the following lower bound for the number of oracle queries for
frameworks $(G_{p,q},\mathcal{M}_{W})$; the proof is similar to the proof of
[10, Claim 1.2] and we provide it for completeness.

######  Claim 15.

Solving Independent $(s,t)$-Cut for instances $(G_{p,q},\mathcal{M}_{W},s,t)$
with the matroids $\mathcal{M}_{W}$ defined by the independence oracle for an
(unknown) stable set $W$ of $G_{p,q}$ of size $k=2p$ demands at least
$q^{p}-1$ oracle queries.

######  Proof 6.4 (Proof of Claim 15).

Recall that any $(s,t)$-cut in $G_{p,q}$ has size at least $k$ and all sets
$X\subseteq V(G_{p,q})\setminus\\{s,t\\}$ of size at least $k+1$ are not
independent with respect to $\mathcal{M}$. Thus, we are looking for an
$(s,t)$-cut of size $k$. For every $(s,t)$-cut $X$ in $G_{p,q}$ of size $k$,
$X=\bigcup_{i=1}^{p}\\{a_{h_{i}}^{i},b_{h_{i}}^{i}\\}$ for some
$h_{1},\ldots,h_{p}\in[q]$. By the definition of $\mathcal{M}$, any $X$ of
this form is independent if and only if $X=W$. This means that the problem
boils down to identifying unknown $W$ using oracle queries. Querying the
oracle for sets $X$ of size at most $k-1$ or at least $k+1$ does not provide
any information about $W$. Also, querying the oracle for $X$ of size $k$ with
the property that there is $i\in[p]$ such that $|A_{i}\cap X|\geq 2$ or
$|B_{i}\cap X|\geq 2$ or there are distinct $h,j\in[q]$ such that
$a_{h}^{i},b_{j}^{i}\in X$ also does not give any information because all
these are independent. Hence, we can assume that the oracle is queried only
for sets $X$ of size $k$ with the property that for each $i\in[p]$, there is
$j\in[q]$ such that $X\cap V(G_{i})=\\{a_{j}^{i},b_{j}^{i}\\}$, that, is the
oracle is queried for $(s,k)$-cuts of size $k$. The graph $G_{p,q}$ has
$q^{p}$ such sets. Suppose that the oracle is queried for at most $q^{p}-2$
stable sets of size $k$ with the answer no. Then there are two distinct stable
sets $W$ and $W^{\prime}$ of size $k$ such that the oracle was queried neither
for $W$ nor $W^{\prime}$. The previous queries do not help to distinguish
between $W$ and $W^{\prime}$. Hence, at least one more query is needed. This
proves the claim.

To show the theorem, suppose that there is an algorithm $\mathcal{A}$ solving
Independent $(s,t)$-Cut with at most $f(k)\cdot n^{g(k)}$ oracle calls on
matroids of rank $k$ for computable functions $f$ and $g$ such that
$g(k)=o(k)$. Without loss of generality, we assume that $f$ and $g$ are
monotone non-decreasing functions. Because $g(k)=o(k)$, there is a positive
integer $K$ such that $g(k)<k/2$ for all $k\geq K$. Then for each $k\geq K$,
there is a positive integer $N_{k}$ such that for every $n\geq N_{k}$,
$(f(k)\cdot n^{g(k)}+1)k^{k/2}<(n-2)^{k/2}$.

Consider instances $(G_{p,q},\mathcal{M}_{W})$ for even $k\geq K$ where
$p=k/2$ and $q\geq(N_{k}-2)/k$. We have that $k=2p$ and $n=2pq+2$. Then
$\mathcal{A}$ applied to such instances would use at most $f(k)\cdot
n^{g(k)}<\big{(}\frac{n-2}{k}\big{)}^{k/2}-1=q^{p}-1$ oracle queries
contradicting Claim 15. This completes the proof.

##  7 Conclusion

In this paper we studied matroidal generalizations of several fundamental
graph separation problems, such as Vertex $(s,t)$-Cut and Vertex Multiway Cut.
We showed that these problems are FPT when parameterized by the size of the
solution. These results were obtained by combining several recent and old
techniques in the world of parameterized complexity. Our paper leaves several
interesting questions open. These include obtaining $2^{\mathcal{O}(k)}\cdot
n^{\mathcal{O}(1)}$ time algorithm for all the problems studied in this paper.
In addition, designing FPT algorithms for matroid versions of other problems
such as Vertex Multi-cut, Directed Feedback Vertex Set remains an interesting
research direction.

## References

  * [1] Noga Alon, Raphael Yuster, and Uri Zwick.  Color-coding.  J. ACM, 42(4):844–856, 1995.  URL: http://dx.doi.org/10.1145/210332.210337, doi:10.1145/210332.210337.
  * [2] Gruia Călinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák.  Maximizing a monotone submodular function subject to a matroid constraint.  SIAM J. Comput., 40(6):1740–1766, 2011.  doi:10.1137/080733991.
  * [3] William H. Cunningham.  Improved bounds for matroid partition and intersection algorithms.  SIAM J. Comput., 15(4):948–957, 1986.  doi:10.1137/0215066.
  * [4] M. Cygan, F. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh.  Parameterized Algorithms.  Springer, 2015.
  * [5] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer, 2015.  doi:10.1007/978-3-319-21275-3.
  * [6] Marek Cygan, Fabrizio Grandoni, and Danny Hermelin.  Tight kernel bounds for problems on graphs with small degeneracy.  ACM Trans. Algorithms, 13(3):43:1–43:22, 2017.  doi:10.1145/3108239.
  * [7] Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, and Jakub Onufry Wojtaszczyk.  On multiway cut parameterized above lower bounds.  ACM Trans. Comput. Theory, 5(1):3:1–3:11, 2013.  doi:10.1145/2462896.2462899.
  * [8] Uriel Feige and Mohammad Mahdian.  Finding small balanced separators.  In Jon M. Kleinberg, editor, Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pages 375–384. ACM, 2006.  doi:10.1145/1132516.1132573.
  * [9] F. V. Fomin, D. Lokshtanov, and S. Saurabh.  Efficient computation of representative sets with applications in parameterized and exact algorithms.  In proceedings of SODA, pages 142–151, 2014.
  * [10] Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, and Saket Saurabh.  Stability in graphs with matroid constraints, 2024.  arXiv:2404.03979.
  * [11] Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh.  Efficient computation of representative families with applications in parameterized and exact algorithms.  J. ACM, 63(4):29:1–29:60, 2016.  doi:10.1145/2886094.
  * [12] Gagan Goel, Chinmay Karande, Pushkar Tripathi, and Lei Wang.  Approximability of combinatorial problems with multi-agent submodular cost functions.  In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 755–764. IEEE Computer Society, 2009.  doi:10.1109/FOCS.2009.81.
  * [13] MohammadTaghi Hajiaghayi, Rohit Khandekar, and Guy Kortsarz.  Local search algorithms for the red-blue median problem.  Algorithmica, 63(4):795–814, 2012.  URL: https://doi.org/10.1007/s00453-011-9547-9, doi:10.1007/S00453-011-9547-9.
  * [14] Zhong Huang and Xueliang Li.  Hardness results for rainbow disconnection of graphs.  CoRR, abs/1811.11939, 2018.  URL: http://arxiv.org/abs/1811.11939, arXiv:1811.11939.
  * [15] Stefanie Jegelka and Jeff Bilmes.  Notes on graph cuts with submodular edge weights.  In NIPS 2009 Workshop on Discrete Optimization in Machine Learning: Submodularity, Sparsity Polyhedra (DISCML), pages 1–6, 2009.
  * [16] Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström.  Flow-augmentation i: Directed graphs.  arXiv preprint arXiv:2111.03450, 2021.
  * [17] Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström.  Solving hard cut problems via flow-augmentation.  In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 \- 13, 2021, pages 149–168. SIAM, 2021.  doi:10.1137/1.9781611976465.11.
  * [18] Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström.  Directed flow-augmentation.  In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 \- 24, 2022, pages 938–947. ACM, 2022.  doi:10.1145/3519935.3520018.
  * [19] Ravishankar Krishnaswamy, Shi Li, and Sai Sandeep.  Constant approximation for k-median and k-means with outliers via iterative rounding.  In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 646–659. ACM, 2018.  doi:10.1145/3188745.3188882.
  * [20] Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, and Saket Saurabh.  Deterministic truncation of linear matroids.  In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, ICALP 2015, pages 922–934, 2015.  doi:10.1007/978-3-662-47672-7\\_75.
  * [21] Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, and Saket Saurabh.  Deterministic truncation of linear matroids.  ACM Trans. Algorithms, 14(2):14:1–14:20, 2018.  doi:10.1145/3170444.
  * [22] László Lovász.  Flats in matroids and geometric graphs.  In Combinatorial Surveys (Proc. 6th British Combinatorial Conference, pages 45–86, 1977.
  * [23] László Lovász.  Graphs and geometry, volume 65 of American Mathematical Society Colloquium Publications.  American Mathematical Society, Providence, RI, 2019.  doi:10.1090/coll/065.
  * [24] Pasin Manurangsi, Erel Segal-Halevi, and Warut Suksompong.  On maximum bipartite matching with separation.  Inf. Process. Lett., 182:106388, 2023.  URL: https://doi.org/10.1016/j.ipl.2023.106388, doi:10.1016/J.IPL.2023.106388.
  * [25] Dániel Marx.  Parameterized graph separation problems.  Theor. Comput. Sci., 351(3):394–406, 2006.  URL: https://doi.org/10.1016/j.tcs.2005.10.007, doi:10.1016/J.TCS.2005.10.007.
  * [26] Dániel Marx.  A parameterized view on matroid optimization problems.  In Hajo Broersma, Stefan S. Dantchev, Matthew Johnson, and Stefan Szeider, editors, ACiD 2006, volume 7 of Texts in Algorithmics, page 158. King’s College, London, 2006.
  * [27] Dániel Marx.  A parameterized view on matroid optimization problems.  Theor. Comput. Sci., 410(44):4471–4479, 2009.  doi:10.1016/j.tcs.2009.07.027.
  * [28] Dániel Marx, Barry O’Sullivan, and Igor Razgon.  Treewidth reduction for constrained separation and bipartization problems.  In Jean-Yves Marion and Thomas Schwentick, editors, 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, March 4-6, 2010, Nancy, France, volume 5 of LIPIcs, pages 561–572. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010.  URL: https://doi.org/10.4230/LIPIcs.STACS.2010.2485, doi:10.4230/LIPICS.STACS.2010.2485.
  * [29] Dániel Marx, Barry O’Sullivan, and Igor Razgon.  Finding small separators in linear time via treewidth reduction.  ACM Trans. Algorithms, 9(4):30:1–30:35, 2013.  doi:10.1145/2500119.
  * [30] Syed Mohammad Meesum, Fahad Panolan, Saket Saurabh, and Meirav Zehavi.  Rank vertex cover as a natural problem for algebraic compression.  SIAM J. Discret. Math., 33(3):1277–1296, 2019.  doi:10.1137/17M1154370.
  * [31] Rolf Niedermeier and Peter Rossmanith.  On efficient fixed-parameter algorithms for weighted vertex cover.  J. Algorithms, 47(2):63–77, 2003.  doi:10.1016/S0196-6774(03)00005-1.
  * [32] Bruce A. Reed, Kaleigh Smith, and Adrian Vetta.  Finding odd cycle transversals.  Oper. Res. Lett., 32(4):299–301, 2004.  URL: https://doi.org/10.1016/j.orl.2003.10.009, doi:10.1016/J.ORL.2003.10.009.
  * [33] Hadas Shachnai and Meirav Zehavi.  A multivariate framework for weighted FPT algorithms.  J. Comput. Syst. Sci., 89:157–189, 2017.  URL: https://doi.org/10.1016/j.jcss.2017.05.003, doi:10.1016/J.JCSS.2017.05.003.
  * [34] Laurence A Wolsey.  An analysis of the greedy algorithm for the submodular set covering problem.  Combinatorica, 2(4):385–393, 1982.