Abstract
In this paper, we study multibudgeted 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 multibudgeted 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 multibudgeted variant turns out to be NPhard 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 multibudgeted 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 sourcetosink 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 flowguided branching and show an FPT bound on the number of (appropriately defined) important multibudgeted separators. This allows us to extend our algorithm to the Skew Multicut and Directed Feedback Arc Set problems.
Furthermore, we show connections of the multibudgeted variants with weighted variants of the directed cut problems and the Chain lSAT problem, whose parameterized complexity remains an open problem. We show that these problems admit a boundedinparameter 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 = {{MultiBudgeted Directed Cuts}},
booktitle = {13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
pages = {18:118:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770842},
ISSN = {18688969},
year = {2019},
volume = {115},
editor = {Christophe Paul and Michal Pilipczuk},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10219},
URN = {urn:nbn:de:0030drops102194},
doi = {10.4230/LIPIcs.IPEC.2018.18},
annote = {Keywords: important separators, multibudgeted cuts, Directed Feedback Vertex Set, fixedparameter tractability, minimum cut}
}
Keywords: 

important separators, multibudgeted cuts, Directed Feedback Vertex Set, fixedparameter tractability, minimum cut 
Collection: 

13th International Symposium on Parameterized and Exact Computation (IPEC 2018) 
Issue Date: 

2019 
Date of publication: 

05.02.2019 