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/
Go to the corresponding LIPIcs Volume Portal


Kratsch, Stefan ; Li, Shaohua ; Marx, Dániel ; Pilipczuk, Marcin ; Wahlström, Magnus

Multi-Budgeted Directed Cuts

pdf-format:
LIPIcs-IPEC-2018-18.pdf (0.7 MB)


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


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI