Multi-budgeted directed cuts

DOI10.1007/S00453-019-00609-1zbMATH Open1477.68236arXiv1810.06848OpenAlexW2965452024WikidataQ127408777 ScholiaQ127408777MaRDI QIDQ786027FDOQ786027

Authors: Stefan Kratsch, Dániel Marx, Marcin Pilipczuk, Magnus Wahlström, Shao-Hua Li 

Publication date: 12 August 2020

Published in: Algorithmica (Search for Journal in Brave)

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,\mathrm{...},ell$ to some edges and give separate budgets $k_1,k_2,\mathrm{...},k_{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, but also needs to satisfy that $|Ccap{E}_i|leq{k}_i$ for every $iin1,\mathrm{...},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+\mathrm{...}+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.

Full work available at URL: https://arxiv.org/abs/1810.06848

Recommendations

• Multi-budgeted directed cuts
• Cut Problems in Graphs with a Budget Constraint
• Cut problems in graphs with a budget constraint
• Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset

zbMATH Keywords

fixed-parameter tractabilityminimum cutdirected feedback vertex setimportant separatorsmulti-budgeted cuts

Mathematics Subject Classification ID

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)

Cites Work

• Almost 2-SAT is fixed-parameter tractable
• Half-integrality, LP-branching, and FPT algorithms
• Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
• A fixed-parameter algorithm for the directed feedback vertex set problem
• FPT algorithms for path-transversal and cycle-transversal problems
• Multiway cuts in node weighted graphs
• Multi-budgeted directed cuts
• Parameterized algorithms
• Parameterized graph separation problems
• Finding small separators in linear time via treewidth reduction
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• Approximating minimum feedback sets and multicuts in directed graphs
• The multivariate algorithmic revolution and beyond. Essays dedicated to Michael R. Fellows on the occasion of his 60th birthday
• Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms
• Improved approximation for directed cut problems
• Designing FPT algorithms for cut problems using randomized contractions
• Directed Subset Feedback Vertex Set is fixed-parameter tractable
• Compression via Matroids
• Linear time parameterized algorithms for \textsc{Subset Feedback Vertex Set}
• Linear-time kernelization for feedback vertex set
• The Steiner k-Cut Problem

Cited In (7)

• Extended cuts
• Multi-budgeted directed cuts
• Cut Problems in Graphs with a Budget Constraint
• A survey of parameterized algorithms and the complexity of edge modification
• Directed flow-augmentation
• Covering directed and odd cuts
• Cut problems in graphs with a budget constraint

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)