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.