LIPIcs.STACS.2019.11.pdf
- Filesize: 0.5 MB
- 16 pages
Document
On the Descriptive Complexity of Color Coding
Authors
-
Part of:
Volume:
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
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: 2019-03-12
Cite As Get BibTex
Max Bannach and Till Tantau. On the Descriptive Complexity of Color Coding. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.STACS.2019.11
Abstract
Color coding is an algorithmic technique used in parameterized complexity theory to detect "small" structures inside graphs. The idea is to derandomize algorithms that first randomly color a graph and then search for an easily-detectable, small color pattern. We transfer color coding to the world of descriptive complexity theory by characterizing - purely in terms of the syntactic structure of describing formulas - when the powerful second-order quantifiers representing a random coloring can be replaced by equivalent, simple first-order formulas. Building on this result, we identify syntactic properties of first-order quantifiers that can be eliminated from formulas describing parameterized problems. The result applies to many packing and embedding problems, but also to the long path problem. Together with a new result on the parameterized complexity of formula families involving only a fixed number of variables, we get that many problems lie in fpt just because of the way they are commonly described using logical formulas.
Subject Classification
ACM Subject Classification
- Theory of computation → Finite Model Theory
- Theory of computation → Fixed parameter tractability
Keywords
- color coding
- descriptive complexity
- fixed-parameter tractability
- quantifier elimination
- para-AC^0
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Noga Alon, Raphael Yuster, and Uri Zwick. Color-Coding. Journal of the 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 Proceedings of the Tenth International Symposium on Parameterized and Exact Computation (IPEC 2015), pages 224-235, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2015.224.
- Max Bannach and Till Tantau. Parallel Multivariate Meta-Theorems. In Proceedings of the Eleventh International Symposium on Parameterized and Exact Computation (IPEC 2016), pages 4:1-4:17, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2016.4.
- Max Bannach and Till Tantau. Computing Hitting Set Kernels By AC⁰-Circuits. In Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), pages 9:1-9:14, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2018.9.
- Hubie Chen and Moritz Müller. The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space. ACM Transactions on Computation Theory, 7(2):7:1-7:27, 2015. URL: http://dx.doi.org/10.1145/2751316.
- Yijia Chen, Jörg Flum, and Xuangui Huang. Slicewise Definability in First-Order Logic with Bounded Quantifier Rank. In Proceedings of the 26th EACSL Annual Conference on Computer Science Logic (CSL 2017), pages 19:1-19:16, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.CSL.2017.19.
- Yijia Chen and Jörg Flum. Tree-depth, quantifier elimination, and quantifier rank. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2018), pages 225-234. ACM, 2018. URL: http://dx.doi.org/10.1145/3209108.3209160.
- Bireswar Das, Murali Krishna Enduri, and I. Vinod Reddy. On the Parallel Parameterized Complexity of the Graph Isomorphism Problem. In Proceedings of the Twelfth International Conference and Workshop on Algorithms and Computation (WALCOM 2018), pages 252-264. Springer, 2018. URL: http://dx.doi.org/10.1007/978-3-319-75172-6_22.
-
Ronald Fagin. Generalized First-Order Spectra and Polynomial-Time Recognizable Sets. Complexity of Computation, 7:43-74, 1974.
- Jörg Flum and Martin Grohe. Describing Parameterized Complexity Classes. Information and Computation, 187(2):291-319, December 2003. URL: http://dx.doi.org/10.1016/S0890-5401(03)00161-5.
- Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. Springer, 2006. URL: http://dx.doi.org/10.1007/3-540-29953-X.
- Falk Hüffner, Sebastian Wernicke, and Thomas Zichner. Algorithm Engineering for Color-Coding with Applications to Signaling Pathway Detection. Algorithmica, 52(2):114-132, 2008. URL: http://dx.doi.org/10.1007/s00453-007-9008-7.
- Neil Immerman. DSPACE[n^k] = VAR[k+1]. In Proceedings of the Sixth Annual Structure in Complexity Theory Conference, pages 334-340, 1991. URL: http://dx.doi.org/10.1109/SCT.1991.160278.
- Michał Pilipczuk, Sebastian Siebertz, and Szymon Toruńczyk. Parameterized circuit complexity of model-checking on sparse structures. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2018), pages 789-798, 2018. URL: http://dx.doi.org/10.1145/3209108.3209136.
- Heribert Vollmer. Introduction to Circuit Complexity - A Uniform Approach. Texts in Theoretical Computer Science. An EATCS Series. Springer, 1999. URL: http://dx.doi.org/10.1007/978-3-662-03927-4.