Multi-budgeted directed cuts (Q786027)

Given a directed graph with two disjoint sets of vertices \(X, Y \subseteq V(G)\), an integer \(l\) and for every \(i\in \{1,\ldots, l\}\) a set of arcs \(E_i\subseteq E(G)\) and an integer \(k_i\geq 1\), the multi-budget cut problem is to decide whether there exists a set of arcs \(C\subseteq \bigcup_{i=1}^{l} E_i\) such that \begin{itemize} \item \(C\) is an \(X\)-\(Y\) cut in \(G\) (i.e., there is no directed path from any vertex in \(X\) to any vertex in \(Y\) in the graph \((V(G),E(G)\setminus C)\)) and, moreover, \item for every \(i\in \{1,\ldots,l\}\), \(|C\cap E_i|\leq k_i\). \end{itemize} Note that for \(l=1\) the problem coincides with the classical \(X\)-\(Y\) cut problem; for \(l\geq 2\), the problem is NP-complete, as proved by the authors. Multi-budgeted skew multicut and multi-budgeted directed feedback arc set are analogous generalizations of skew multicut and directed feedback arc set. The paper describes an FPT algorithm for the multi-budget cut problem parameterized by \(k=k_1+k_2+\cdots+k_l\). The branching strategy of the algorithm is similar to the branching strategy used in the FPT algorithm for enumeration of all important separators of a given size and this fact makes it possible to extend the algorithm to the multi-budgeted skew multicut and multi-budgeted directed feedback arc set. The paper also provides a graph-theoretical result about the structure of minimum weight \(s\)-\(t\) cuts of a bounded cardinality in directed graphs, which is another NP-complete generalization of the classical \(s\)-\(t\) cut problem. A result of a similar favour is proved also for the Chain \(l\)-SAT problem.