Multi-budgeted directed cuts

Directed graphs (digraphs), tournaments (05C20) Flows in graphs (05C21) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Abstract: 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, ..., e l l

to some edges and give separate budgets

k_{1}, k_{2}, ..., k_{e l 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, but also needs to satisfy that

| C c a p E_{i} | l e q k_{i}

for every

i i n 1, ..., e l l

. Contrary to the classic minimum cut problem, the multi-budgeted variant turns out to be NP-hard even for

e l l = 2

. We propose FPT algorithms parameterized by

k = k_{1} + ... + k_{e l 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

e l 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.

Review text

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.

Recommendations

Cites work

Cited in

(11)

This page was built for publication: Multi-budgeted directed cuts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q786027)