2026-08-06T13:13:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10219 2024-03-06T10:44:17Z ddc:004 open_access

Multi-Budgeted Directed Cuts Kratsch, Stefan Li, Shaohua Marx, Dániel Pilipczuk, Marcin Wahlström, Magnus important separators multi-budgeted cuts Directed Feedback Vertex Set fixed-parameter tractability minimum cut In this paper, we study multi-budgeted variants of the classic minimum cut problem and graph separation problems that turned out to be important in parameterized complexity: Skew Multicut and Directed Feedback Arc Set. In our generalization, we assign colors 1,2,...,l to some edges and give separate budgets k_1,k_2,...,k_l for colors 1,2,...,l. For every color i in {1,...,l}, let E_i be the set of edges of color i. The solution C for the multi-budgeted variant of a graph separation problem not only needs to satisfy the usual separation requirements (i.e., be a cut, a skew multicut, or a directed feedback arc set, respectively), but also needs to satisfy that |C cap E_i| <= k_i for every i in {1,...,l}. Contrary to the classic minimum cut problem, the multi-budgeted variant turns out to be NP-hard even for l = 2. We propose FPT algorithms parameterized by k=k_1 +...+ k_l for all three problems. To this end, we develop a branching procedure for the multi-budgeted minimum cut problem that measures the progress of the algorithm not by reducing k as usual, by but elevating the capacity of some edges and thus increasing the size of maximum source-to-sink flow. Using the fact that a similar strategy is used to enumerate all important separators of a given size, we merge this process with the flow-guided branching and show an FPT bound on the number of (appropriately defined) important multi-budgeted separators. This allows us to extend our algorithm to the Skew Multicut and Directed Feedback Arc Set problems. Furthermore, we show connections of the multi-budgeted variants with weighted variants of the directed cut problems and the Chain l-SAT problem, whose parameterized complexity remains an open problem. We show that these problems admit a bounded-in-parameter number of "maximally pushed" solutions (in a similar spirit as important separators are maximally pushed), giving somewhat weak evidence towards their tractability. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stefan Kratsch and Shaohua Li and Dániel Marx and Marcin Pilipczuk and Magnus Wahlström 2019 Is Part Of LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2018.18 urn:nbn:de:0030-drops-102194 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.18 eng https://creativecommons.org/licenses/by/3.0/legalcode