Multi-budgeted directed cuts

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

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.

Recommendations

Cites work

Cited in

(7)

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)