LIPIcs.STACS.2018.9.pdf
- Filesize: 0.58 MB
- 14 pages
Document
Computing Hitting Set Kernels By AC^0-Circuits
Authors
-
Part of:
Volume:
35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-02-27
Cite As Get BibTex
Max Bannach and Till Tantau. Computing Hitting Set Kernels By AC^0-Circuits. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.STACS.2018.9
Abstract
Given a hypergraph H = (V,E), what is the smallest subset X of V such that e and X are not disjoint for all e in E? This problem, known as the hitting set problem, is a basic problem in parameterized complexity theory. There are well-known kernelization algorithms for it, which get a hypergraph H and a number k as input and output a hypergraph H' such that (1) H has a hitting set of size k if, and only if, H' has such a hitting set and (2) the size of H' depends only on k and on the maximum cardinality d of edges in H. The algorithms run in polynomial time, but are highly sequential. Recently, it has been shown that one of them can be parallelized to a certain degree: one can compute hitting set kernels in parallel time O(d) - but it was conjectured that this is the best parallel algorithm possible. We refute this conjecture and show how hitting set kernels can be computed in constant parallel time. For our proof, we introduce a new, generalized notion of hypergraph sunflowers and show how iterated applications of the color coding technique can sometimes be collapsed into a single application.
Subject Classification
Keywords
- parallel computation
- fixed-parameter tractability
- kernelization
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Faisal N. Abu-Khzam, Michael A. Langston, Pushkar Shanbhag, and Christopher T. Symons. Scalable parallel algorithms for FPT problems. Algorithmica, 45(3):269-284, 2006. URL: http://dx.doi.org/10.1007/s00453-006-1214-1.
- Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844-856, 1995. URL: http://dx.doi.org/10.1145/210332.210337.
- Max Bannach, Christoph Stockhusen, and Till Tantau. Fast parallel fixed-parameter algorithms via color coding. In Thore Husfeldt and Iyad A. Kanj, editors, 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, September 16-18, 2015, Patras, Greece, volume 43 of LIPIcs, pages 224-235. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2015.224.
- Max Bannach and Till Tantau. Parallel multivariate meta-theorems. In Jiong Guo and Danny Hermelin, editors, 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, August 24-26, 2016, Aarhus, Denmark, volume 63 of LIPIcs, pages 4:1-4:17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2016.4.
- Max Bannach and Till Tantau. Computing hitting set kernels by AC⁰-circuits. Technical Report arxiv:1801.00716 [cs.CC], ArXiv e-prints, 2018. URL: http://arxiv.org/abs/1801.00716.
- David A. Mix Barrington, Neil Immerman, and Howard Straubing. On uniformity within nc^1. In Proceedings: Third Annual Structure in Complexity Theory Conference, Georgetown University, Washington, D. C., USA, June 14-17, 1988, pages 47-59. IEEE Computer Society, 1988. URL: http://dx.doi.org/10.1109/SCT.1988.5262.
- Liming Cai, Jianer Chen, Rodney G. Downey, and Michael 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.
- Marco Cesati and Miriam Di Ianni. Parameterized parallel complexity. In David J. Pritchard and Jeff Reeve, editors, Euro-Par '98 Parallel Processing, 4th International Euro-Par Conference, Southampton, UK, September 1-4, 1998, Proceedings, volume 1470 of Lecture Notes in Computer Science, pages 892-896. Springer, 1998. URL: http://dx.doi.org/10.1007/BFb0057945.
- Yijia Chen and Jörg Flum. Some lower bounds in parameterized ac^0. In Piotr Faliszewski, Anca Muscholl, and Rolf Niedermeier, editors, 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26, 2016 - Kraków, Poland, volume 58 of LIPIcs, pages 27:1-27:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.27.
- Yijia Chen, Jörg Flum, and Martin Grohe. Bounded nondeterminism and alternation in parameterized complexity theory. In 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 7-10 July 2003, Aarhus, Denmark, pages 13-29. IEEE Computer Society, 2003. URL: http://dx.doi.org/10.1109/CCC.2003.1214407.
- 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, 26th EACSL Annual Conference on Computer Science Logic, CSL 2017, August 20-24, 2017, Stockholm, Sweden, volume 82 of LIPIcs, pages 19:1-19:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.CSL.2017.19.
- Michael Elberfeld, Christoph Stockhusen, and Till 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.
-
P. Erdős and R. Rado. Intersection theorems for systems of sets. Journal of the London Mathematical Society, 1(1):85-90, 1960.
- Jörg Flum and Martin Grohe. Describing parameterized complexity classes. In Helmut Alt and Afonso Ferreira, editors, STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes - Juan les Pins, France, March 14-16, 2002, Proceedings, volume 2285 of Lecture Notes in Computer Science, pages 359-371. Springer, 2002. URL: http://dx.doi.org/10.1007/3-540-45841-7_29.
- Jörg Flum and Martin 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.
- Rolf Niedermeier and Peter Rossmanith. An efficient fixed-parameter algorithm for 3-hitting set. J. Discrete Algorithms, 1(1):89-102, 2003. URL: http://dx.doi.org/10.1016/S1570-8667(03)00009-1.
- René van Bevern. Towards optimal and expressive kernelization for d-hitting set. Algorithmica, 70(1):129-147, 2014. URL: http://dx.doi.org/10.1007/s00453-013-9774-3.