License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2018.18
URN: urn:nbn:de:0030-drops-102194
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10219/
Kratsch, Stefan ;
Li, Shaohua ;
Marx, Dániel ;
Pilipczuk, Marcin ;
Wahlström, Magnus
Multi-Budgeted Directed Cuts
Abstract
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,...,l to some edges and give separate budgets k_1,k_2,...,k_l for colors 1,2,...,l. For every color i in {1,...,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 (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| <= k_i for every i in {1,...,l}.
Contrary to the classic minimum cut problem, the multi-budgeted variant turns out to be NP-hard even for l = 2. We propose FPT algorithms parameterized by k=k_1 +...+ k_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 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.
BibTeX - Entry
@InProceedings{kratsch_et_al:LIPIcs:2019:10219,
author = {Stefan Kratsch and Shaohua Li and D{\'a}niel Marx and Marcin Pilipczuk and Magnus Wahlstr{\"o}m},
title = {{Multi-Budgeted Directed Cuts}},
booktitle = {13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
pages = {18:1--18:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-084-2},
ISSN = {1868-8969},
year = {2019},
volume = {115},
editor = {Christophe Paul and Michal Pilipczuk},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10219},
URN = {urn:nbn:de:0030-drops-102194},
doi = {10.4230/LIPIcs.IPEC.2018.18},
annote = {Keywords: important separators, multi-budgeted cuts, Directed Feedback Vertex Set, fixed-parameter tractability, minimum cut}
}
|
Keywords: |
|
important separators, multi-budgeted cuts, Directed Feedback Vertex Set, fixed-parameter tractability, minimum cut |
|
Collection: |
|
13th International Symposium on Parameterized and Exact Computation (IPEC 2018) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
05.02.2019 |
