{ \sc Vertex $(s, t)$-Cut} and { \sc Vertex Multiway Cut} are two fundamental graph separation problems in algorithmic graph theory. We study matroidal generalizations of these problems, where in addition to the usual input, we are given a representation $R \in \mathbb{ F}^{ r \times n}$ of a linear matroid $\mathcal{ M} = (V(G), \mathcal{ I})$ of rank $r$ in the input, and the goal is to determine whether there exists a vertex subset $S \subseteq V(G)$ that has the required cut properties, as well as is independent in the matroid $\mathcal{ M}$. We refer to these problems as { \sc Independent Vertex $(s, t)$-cut}, and { \sc Independent Multiway Cut}, respectively. We show that these problems are fixed-parameter tractable ({ \sf FPT}) when parameterized by the solution size (which can be assumed to be equal to the rank of the matroid $\mathcal{ M}$). These results are obtained by exploiting the recent technique of flow augmentation [Kim et al.~STOC '22], combined with a dynamic programming algorithm on flow-paths \'a la [Feige and Mahdian,~STOC '06] that maintains a representative family of solutions w.r.t.~the given matroid [Marx, TCS '06; Fomin et al., JACM]. As a corollary, we also obtain { \sf FPT} algorithms for the independent version of { \sc Odd Cycle Transversal}. Further, our results can be generalized to other variants of the problems, e.g., weighted versions, or edge-deletion versions.
Categories: cs.DM cs.DS math.CO