Document Open Access Logo

Computing Kernels in Parallel: Lower and Upper Bounds

Authors Max Bannach , Till Tantau

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2018.13.pdf
  • Filesize: 462 kB
  • 14 pages

Document Identifiers

Author Details

Max Bannach
  • Institute for Theoretical Computer Science, Universität zu Lübeck, Lübeck, Germany
Till Tantau
  • Institute for Theoretical Computer Science, Universität zu Lübeck, Lübeck, Germany

Cite As Get BibTex

Max Bannach and Till Tantau. Computing Kernels in Parallel: Lower and Upper Bounds. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.IPEC.2018.13

Abstract

Parallel fixed-parameter tractability studies how parameterized problems can be solved in parallel. A surprisingly large number of parameterized problems admit a high level of parallelization, but this does not mean that we can also efficiently compute small problem kernels in parallel: known kernelization algorithms are typically highly sequential. In the present paper, we establish a number of upper and lower bounds concerning the sizes of kernels that can be computed in parallel. An intriguing finding is that there are complex trade-offs between kernel size and the depth of the circuits needed to compute them: For the vertex cover problem, an exponential kernel can be computed by AC^0-circuits, a quadratic kernel by TC^0-circuits, and a linear kernel by randomized NC-circuits with derandomization being possible only if it is also possible for the matching problem. Other natural problems for which similar (but quantitatively different) effects can be observed include tree decomposition problems parameterized by the vertex cover number, the undirected feedback vertex set problem, the matching problem, or the point line cover problem. We also present natural problems for which computing kernels is inherently sequential.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • parallel computation
  • fixed-parameter tractability
  • kernelization

Metrics

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

Related Versions

References

  1. E. Allender, M. Bauland, N. Immerman, H. Schnoor, and H. Vollmer. The complexity of satisfiability problems: Refining Schaefer’s theorem. J. Comput. Syst. Sci., 75(4):245-254, 2009. URL: http://dx.doi.org/10.1016/j.jcss.2008.11.001.
  2. M. Bannach, C. Stockhusen, and T. Tantau. Fast Parallel Fixed-parameter Algorithms via Color Coding. In Proceedings of IPEC 2015, pages 224-235, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2015.224.
  3. M. Bannach and T. Tantau. Parallel Multivariate Meta-Theorems. In Proceedings of IPEC 2016, pages 4:1-4:17, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2016.4.
  4. H. L. Bodlaender. A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth. SIAM J. Comput., 25(6):1305-1317, 1996. URL: http://dx.doi.org/10.1137/S0097539793251219.
  5. H. L. Bodlaender, B. M. P. Jansen, and S. Kratsch. Kernel Bounds for Structural Parameterizations of Pathwidth. In Proceedings of SWAT 2012, pages 352-363, 2012. URL: http://dx.doi.org/10.1007/978-3-642-31155-0_31.
  6. H. L. Bodlaender, B. M. P. Jansen, and S. Kratsch. Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization. SIAM J. Discrete Math., 27(4):2108-2142, 2013. URL: http://dx.doi.org/10.1137/120903518.
  7. H. L. Bodlaender and T. C. van Dijk. A Cubic Kernel for Feedback Vertex Set and Loop Cutset. Theory Comput. Syst., 46(3):566-597, 2010. URL: http://dx.doi.org/10.1007/s00224-009-9234-2.
  8. Kevin Burrage, Vladimir Estivill-Castro, Michael R. Fellows, Michael A. Langston, Shev Mac, and Frances A. Rosamond. The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel. In Proceedings of IWPEC 2006, pages 192-202, 2006. URL: http://dx.doi.org/10.1007/11847250_18.
  9. L. Cai, J. Chen, R. G. Downey, and M. R. Fellows. Advice Classes of Parameterized Tractability. Ann. Pure Appl. Logic, 84(1):119-138, 1997. URL: http://dx.doi.org/10.1016/S0168-0072(95)00020-8.
  10. J. Chen, I. A. Kanj, and W. Jia. Vertex Cover: Further Observations and Further Improvements. J. Algorithms, 41(2):280-301, 2001. URL: http://dx.doi.org/10.1006/jagm.2001.1186.
  11. Y. Chen and J. Flum. Some Lower Bounds in Parameterized AC⁰. In Proceedings of MFCS 2016, pages 27:1-27:14, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.27.
  12. Yijia Chen, Jörg Flum, and Xuangui Huang. Slicewise Definability in First-Order Logic with Bounded Quantifier Rank. In Valentin Goranko and Mads Dam, editors, Proceedings of CSL 2017, volume 82, pages 19:1-19:16, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.CSL.2017.19.
  13. Stephen A. Cook and Pierre McKenzie. Problems Complete for Deterministic Logarithmic Space. J. Algorithms, 8(3):385-394, 1987. URL: http://dx.doi.org/10.1016/0196-6774(87)90018-6.
  14. M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer Berlin Heidelberg, 2015. Google Scholar
  15. R. G. Downey and M. R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: http://dx.doi.org/10.1007/978-1-4471-5559-1.
  16. M. Elberfeld, C. Stockhusen, and T. Tantau. On the Space and Circuit Complexity of Parameterized Problems: Classes and Completeness. Algorithmica, 71(3):661-701, 2015. URL: http://dx.doi.org/10.1007/s00453-014-9944-y.
  17. S. A. Fenner, R. Gurjar, and T. Thierauf. Bipartite perfect matching is in quasi-NC. In Proceedings of STOC 2016, pages 754-763, 2016. URL: http://dx.doi.org/10.1145/2897518.2897564.
  18. J. Flum and M. Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. URL: http://dx.doi.org/10.1007/3-540-29953-X.
  19. M. L. Furst, J. B. Saxe, and M. Sipser. Parity, Circuits, and the Polynomial-Time Hierarchy. Mathematical Systems Theory, 17(1):13-27, 1984. URL: http://dx.doi.org/10.1007/BF01744431.
  20. S. Gaspers and S. Szeider. Backdoors to Satisfaction. In H.L. Bodlaender, R. Downey, F. V. Fomin, and D. Marx, editors, The Multivariate Algorithmic Revolution and Beyond, pages 287-317. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-30891-8_15.
  21. D. Haugland, M. Eleyat, and M. Lie Hetland. The Maximum Flow Problem with Minimum Lot Sizes. In Proceedings of ICCL 2011, pages 170-182, 2011. URL: http://dx.doi.org/10.1007/978-3-642-24264-9_13.
  22. Yoichi Iwata. Linear-Time Kernelization for Feedback Vertex Set. In Proceedings of ICALP 2017, pages 68:1-68:14, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.68.
  23. Jon M. Kleinberg and Éva Tardos. Algorithm design. Addison-Wesley, 2006. Google Scholar
  24. Y. Kobayashi and H. Tamaki. Treedepth Parameterized by Vertex Cover Number. In Proceedings of IPEC 2016, pages 18:1-18:11, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2016.18.
  25. D. König. Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Mathematische Annalen, 77(4):453-465, 1916. URL: http://dx.doi.org/10.1007/BF01456961.
  26. S. Kratsch, G. Philip, and S. Ray. Point Line Cover: The Easy Kernel is Essentially Tight. ACM Trans. Algorithms, 12(3):40:1-40:16, 2016. URL: http://dx.doi.org/10.1145/2832912.
  27. M. Lampis. A kernel of order 2 k-c log k for vertex cover. Inf. Process. Lett., 111(23-24):1089-1091, 2011. URL: http://dx.doi.org/10.1016/j.ipl.2011.09.003.
  28. K. Mulmuley, U. V. Vazirani, and V. V. Vazirani. Matching is as easy as matrix inversion. Combinatorica, 7(1):105-113, 1987. URL: http://dx.doi.org/10.1007/BF02579206.
  29. G. L. Nemhauser and L. E. Trotter Jr. Properties of vertex packing and independence system polyhedra. Math. Program., 6(1):48-61, 1974. URL: http://dx.doi.org/10.1007/BF01580222.
  30. I. Newman, P. Ragde, and A. Wigderson. Perfect Hashing, Graph Entropy, and Circuit Complexity. In Proceedings of STC 1990, pages 91-99. IEEE Computer Society, Los Alamitos, California, 1990. URL: http://dx.doi.org/10.1109/SCT.1990.113958.
  31. A. Soleimanfallah and A. Yeo. A kernel of order 2k-c for Vertex Cover. Discrete Mathematics, 311(10-11):892-895, 2011. URL: http://dx.doi.org/10.1016/j.disc.2011.02.014.
  32. Clemens Thielen and Stephan Westphal. Complexity and approximability of the maximum flow problem with minimum quantities. Networks, 62(2):125-131, 2013. URL: http://dx.doi.org/10.1002/net.21502.
  33. Stéphan Thomassé. A 4k² kernel for feedback vertex set. ACM Trans. Algorithms, 6(2):32:1-32:8, 2010. URL: http://dx.doi.org/10.1145/1721837.1721848.
  34. Jacobo Toran. P-completeness. In Alan Gibbons and Paul Spirakis, editors, Lectures on parallel computation, pages 177-196. Cambridge University Press, 1993. 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