Gaspers, Serge ;
Lee, Edward J.
Exact Algorithms via Multivariate Subroutines
Abstract
We consider the family of PhiSubset problems, where the input consists of an instance I of size N over a universe U_I of size n and the task is to check whether the universe contains a subset with property Phi (e.g., Phi could be the property of being a feedback vertex set for the input graph of size at most k). Our main tool is a simple randomized algorithm which solves PhiSubset in time (1+b(1/c))^n N^(O(1)), provided that there is an algorithm for the PhiExtension problem with running time b^{nX} c^k N^{O(1)}. Here, the input for PhiExtension is an instance I of size N over a universe U_I of size n, a subset X \subseteq U_I, and an integer k, and the task is to check whether there is a set Y with X \subseteq Y \subseteq U_I and Y \ X <= k with property Phi.
We derandomize this algorithm at the cost of increasing the running time by a subexponential factor in n, and we adapt it to the enumeration setting where we need to enumerate all subsets of the universe with property Phi. This generalizes the results of Fomin et al. [STOC 2016] who proved the case where b=1.
As case studies, we use these results to design faster deterministic algorithms for:
 checking whether a graph has a feedback vertex set of size at most k
 enumerating all minimal feedback vertex sets
 enumerating all minimal vertex covers of size at most k, and
 enumerating all minimal 3hitting sets.
We obtain these results by deriving new b^{nX} c^k N^{O(1)}time algorithms for the corresponding PhiExtension problems (or enumeration variant). In some cases, this is done by adapting the analysis of an existing algorithm, or in other cases by designing a new algorithm. Our analyses are based on Measure and Conquer, but the value to minimize, 1+b(1/c), is unconventional and requires nonconvex optimization.
BibTeX  Entry
@InProceedings{gaspers_et_al:LIPIcs:2017:7425,
author = {Serge Gaspers and Edward J. Lee},
title = {{Exact Algorithms via Multivariate Subroutines}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {69:169:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7425},
URN = {urn:nbn:de:0030drops74251},
doi = {10.4230/LIPIcs.ICALP.2017.69},
annote = {Keywords: enumeration algorithms, exponential time algorithms, feedback vertex set, hitting set}
}
2017
Keywords: 

enumeration algorithms, exponential time algorithms, feedback vertex set, hitting set 
Seminar: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Issue date: 

2017 
Date of publication: 

2017 