Exact Algorithms via Multivariate Subroutines

Authors Serge Gaspers, Edward J. Lee



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.69.pdf
  • Filesize: 0.54 MB
  • 13 pages

Document Identifiers

Author Details

Serge Gaspers
Edward J. Lee

Cite AsGet BibTex

Serge Gaspers and Edward J. Lee. Exact Algorithms via Multivariate Subroutines. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 69:1-69:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ICALP.2017.69

Abstract

We consider the family of Phi-Subset 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 Phi-Subset in time (1+b-(1/c))^n N^(O(1)), provided that there is an algorithm for the Phi-Extension problem with running time b^{n-|X|} c^k N^{O(1)}. Here, the input for Phi-Extension 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 3-hitting sets. We obtain these results by deriving new b^{n-|X|} c^k N^{O(1)}-time algorithms for the corresponding Phi-Extension 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 non-convex optimization.
Keywords
  • enumeration algorithms
  • exponential time algorithms
  • feedback vertex set
  • hitting set

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Jesper Makholm Byskov. Enumerating maximal independent sets with applications to graph colouring. Oper. Res. Lett., 32(6):547-556, 2004. URL: http://dx.doi.org/10.1016/j.orl.2004.03.002.
  2. Manfred Cochefert, Jean-François Couturier, Serge Gaspers, and Dieter Kratsch. Faster algorithms to enumerate hypergraph transversals. In Latin American Symposium on Theoretical Informatics, pages 306-318. Springer, 2016. Google Scholar
  3. Rodney G. Downey and Michael R. Fellows. Fundamentals of parameterized complexity, volume 4. Springer, 2013. Google Scholar
  4. David Eppstein. Small maximal independent sets and faster exact graph coloring. J. Graph Algorithms Appl., 7(2):131-140, 2003. Google Scholar
  5. Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, and Saket Saurabh. Exact algorithms via monotone local search. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016), pages 764-775. ACM, 2016. URL: http://dx.doi.org/10.1145/2897518.2897551.
  6. Fedor V. Fomin, Serge Gaspers, Artem V. Pyatkin, and Igor Razgon. On the minimum feedback vertex set problem: Exact and enumeration algorithms. Algorithmica, 52(2):293-307, 2008. Google Scholar
  7. Fedor V. Fomin, Fabrizio Grandoni, and Dieter Kratsch. A measure & conquer approach for the analysis of exact algorithms. Journal of the ACM, 56(5), 2009. URL: http://dx.doi.org/10.1145/1552285.1552286.
  8. Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms. Springer, 2010. An EATCS Series: Texts in Theoretical Computer Science. Google Scholar
  9. Fedor V. Fomin, Ioan Todinca, and Yngve Villanger. Large induced subgraphs via triangulations and cmso. SIAM Journal on Computing, 44(1):54-87, 2015. Google Scholar
  10. Serge Gaspers. Exponential Time Algorithms - Structures, Measures, and Bounds. VDM, 2010. URL: http://amzn.com/3639218256.
  11. Serge Gaspers and Edward Lee. Exact algorithms via multivariate subroutines, April 2017. arXiv e-prints. URL: https://arxiv.org/abs/1704.07982, URL: http://arxiv.org/abs/1704.07982.
  12. Serge Gaspers and Gregory B. Sorkin. A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between. Journal of Computer and System Sciences, 78(1):305-335, 2012. URL: http://dx.doi.org/10.1016/j.jcss.2011.05.010.
  13. Igor Razgon. Exact computation of maximum induced forest. In Scandinavian Workshop on Algorithm Theory, pages 160-171. Springer, 2006. Google Scholar
  14. Mingyu Xiao and Hiroshi Nagamochi. Exact algorithms for maximum independent set. In International Symposium on Algorithms and Computation, pages 328-338. Springer, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail