2026-07-26T03:22:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21088 2024-09-23T09:13:16Z ddc:004 open_access

Cuts in Graphs with Matroid Constraints Banik, Aritra Fomin, Fedor V. Golovach, Petr A. Inamdar, Tanmay Jana, Satyabrata Saurabh, Saket s-t-cut multiway Cut matroid odd cycle transversal feedback vertex set fixed-parameter tractability Vertex (s, t)-Cut and 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 ∈ 𝔽^{r × n} of a linear matroid ℳ = (V(G), ℐ) of rank r in the input, and the goal is to determine whether there exists a vertex subset S ⊆ V(G) that has the required cut properties, as well as is independent in the matroid ℳ. We refer to these problems as Independent Vertex (s, t){-cut}, and Independent Multiway Cut, respectively. We show that these problems are fixed-parameter tractable (FPT) when parameterized by the solution size (which can be assumed to be equal to the rank of the matroid ℳ). 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 á 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 FPT algorithms for the independent version of Odd Cycle Transversal. Further, our results can be generalized to other variants of the problems, e.g., weighted versions, or edge-deletion versions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aritra Banik and Fedor V. Fomin and Petr A. Golovach and Tanmay Inamdar and Satyabrata Jana and Saket Saurabh 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.17 urn:nbn:de:0030-drops-210887 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.17 eng https://creativecommons.org/licenses/by/4.0/legalcode