Document Open Access Logo

Randomised Enumeration of Small Witnesses Using a Decision Oracle

Author Kitty Meeks

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2016.22.pdf
  • Filesize: 479 kB
  • 12 pages

Document Identifiers

Author Details

Kitty Meeks

Cite As Get BibTex

Kitty Meeks. Randomised Enumeration of Small Witnesses Using a Decision Oracle. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 22:1-22:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.IPEC.2016.22

Abstract

Many combinatorial problems involve determining whether a universe of n elements contains a witness consisting of k elements which have some specified property. In this paper we investigate the relationship between the decision and enumeration versions of such problems: efficient methods are known for transforming a decision algorithm into a search procedure that finds a single witness, but even finding a second witness is not so straightforward in general. In this paper we show that, if the decision version of the problem belongs to FPT, there is a randomised algorithm which enumerates all witnesses in time f(k)*poly(n)*N, where N is the total number of witnesses and f is a computable function. This also gives rise to an efficient algorithm to count the total number of witnesses when this number is small.

Subject Classification

Keywords
  • enumeration algorithms
  • parameterized complexity
  • randomized algorithms
  • color coding

Metrics

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

References

  1. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM, 42(4):844-856, 1995. Google Scholar
  2. V. Arvind and Venkatesh Raman. Approximation algorithms for some parameterized counting problems. In ISAAC 2002, volume 2518 of LNCS, pages 453-464. Springer-Verlag Berlin Heidelberg, 2002. Google Scholar
  3. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Narrow sieves for parameterized paths and packings. arXiv:1007.1161 [cs.DS], 2010. Google Scholar
  4. Andreas Björklund, Petteri Kaski, and Łukasz Kowalik. Probably Optimal Graph Motifs. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), volume 20 of LIPIcs, pages 20-31. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2013. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2013.20.
  5. Andreas Björklund, Petteri Kaski, and Łukasz Kowalik. Fast witness extraction using a decision oracle. In Algorithms - ESA 2014, volume 8737 of LNCS, pages 149-160. Springer Berlin Heidelberg, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44777-2_13.
  6. Andreas Björklund, Petteri Kaski, Łukasz Kowalik, and Juho Lauri. Engineering motif search for large graphs. In 2015 Proc. of the Seventeenth Workshop on Algorithm Engineering and Experiments (ALENEX), pages 104-118. SIAM, 2015. URL: http://dx.doi.org/10.1137/1.9781611973754.10.
  7. Nadia Creignou, Raïda Ktari, Arne Meier, Julian-Steffen Müller, Frédéric Olive, and Heribert Vollmer. Parameterized enumeration for modification problems. In Language and Automata Theory and Applications, volume 8977 of LNCS, pages 524-536. Springer International Publishing, 2015. URL: http://dx.doi.org/10.1007/978-3-319-15579-1_41.
  8. Nadia Creignou, Arne Meier, Julian-Steffen Müller, Johannes Schmidt, and Heribert Vollmer. Paradigms for parameterized enumeration. In Mathematical Foundations of Computer Science 2013, volume 8087 of LNCS, pages 290-301. Springer Berlin Heidelberg, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40313-2_27.
  9. Radu Curticapean. Counting matchings of size k is #W[1]-hard. In Automata, Languages, and Programming, volume 7965 of LNCS, pages 352-363. Springer Berlin Heidelberg, 2013. Google Scholar
  10. Radu Curticapean and Dániel Marx. Complexity of counting subgraphs: Only the boundedness of the vertex-cover number counts. In 55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014, 2014. Google Scholar
  11. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Springer London, 2013. Google Scholar
  12. Henning Fernau. On parameterized enumeration. In Computing and Combinatorics, volume 2387 of LNCS, pages 564-573. Springer Berlin Heidelberg, 2002. URL: http://dx.doi.org/10.1007/3-540-45655-4_60.
  13. Jörg Flum and Martin Grohe. The parameterized complexity of counting problems. SIAM Journal on Computing, 33(4):892-922, 2004. Google Scholar
  14. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Springer, 2006. Google Scholar
  15. Mark Jerrum and Kitty Meeks. The parameterised complexity of counting even and odd induced subgraphs. arXiv:1410.3375 [math.CO], to appear in Combinatorica, 2014. Google Scholar
  16. Mark Jerrum and Kitty Meeks. The parameterised complexity of counting connected subgraphs and graph motifs. Journal of Computer and System Sciences, 81(4):702-716, 2015. URL: http://dx.doi.org/10.1016/j.jcss.2014.11.015.
  17. Mark Jerrum and Kitty Meeks. Some hard families of parameterised counting problems. ACM Transactions on Computation Theory, 7(3), June 2015. URL: http://dx.doi.org/10.1145/2786017.
  18. Samir Khuller and Vijay V. Vazirani. Planar graph coloring is not self-reducible, assuming P ≠ NP. Theoretical Computer Science, 88(1):183-189, 1991. URL: http://dx.doi.org/10.1016/0304-3975(91)90081-C.
  19. Eugene L. Lawler. A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem. Management Science, 18(7):401-405, 1972. URL: http://dx.doi.org/10.1287/mnsc.18.7.401.
  20. Kitty Meeks. The challenges of unbounded treewidth in parameterised subgraph counting problems. Discrete Applied Mathematics, 198:170-194, 2016. URL: http://dx.doi.org/10.1016/j.dam.2015.06.019.
  21. C. P. Schnorr. Optimal algorithms for self-reducible problems. In Proc. of the 3rd ICALP, pages 322-337. Edinburgh University Press, 1976. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact