Multi-budgeted Directed Cuts

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,\ldots ,\ell \) to some edges and give separate budgets \(k_{1},k_{2},\ldots ,k_{\ell }\) for colors \(1,2,\ldots ,\ell \). For every color \(i\in \{1,\ldots ,\ell \}\), 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}|\le k_{i}\) for every \(i\in \{1,\ldots ,\ell \}\). Contrary to the classic minimum cut problem, the multi-budgeted variant turns out to be NP-hard even for \(\ell = 2\). We propose FPT algorithms parameterized by \(k=k_{1}+\cdots +k_{\ell }\) 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\(\ell \)-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.