LIPIcs.IPEC.2016.4.pdf
- Filesize: 0.53 MB
- 17 pages
Document
Parallel Multivariate Meta-Theorems
Authors
-
Part of:
Volume:
11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Parameterized and Exact Computation (IPEC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-02-09
Cite As Get BibTex
Max Bannach and Till Tantau. Parallel Multivariate Meta-Theorems. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.IPEC.2016.4
Abstract
Fixed-parameter tractability is based on the observation that many hard problems become tractable even on large inputs as long as certain input parameters are small. Originally, "tractable" just meant "solvable in polynomial time," but especially modern hardware raises the question of whether we can also achieve "solvable in polylogarithmic parallel time." A framework for this study of parallel fixed-parameter tractability is available and a number of isolated algorithmic results have been obtained in recent years, but one of the unifying core tools of classical FPT theory has been missing: algorithmic meta-theorems. We establish two such theorems by giving new upper bounds on the circuit depth necessary to solve the model checking problem for monadic second-order logic, once parameterized by the tree width and the formula (this is a parallel version of Courcelle's Theorem) and once by the tree depth and the formula. For our proofs we refine the analysis of earlier algorithms, especially of Bodlaender's, but also need to add new ideas, especially in the context where the parallel runtime is bounded by a function of the parameter and does not depend on the length of the input.
Subject Classification
Keywords
- Parallel computation
- FPT
- meta-theorems
- tree width
- tree depth
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- M. Bannach, C. Stockhusen, and T. Tantau. Fast parallel fixed-parameter algorithms via color coding. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015), pages 224-235. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2015.224.
- H. Bodlaender and T. Hagerup. Parallel algorithms with optimal speedup for bounded treewidth. SIAM Journal on Computing, 27(6):1725-1746, 1998. URL: http://dx.doi.org/10.1137/S0097539795289859.
- Hans L. Bodlaender. NC-algorithms for graphs with small treewidth. In Graph-Theoretic Concepts in Computer Science: International Workshop, WG'88, pages 1-10. Springer Berlin Heidelberg, 1989. URL: http://dx.doi.org/10.1007/3-540-50728-0_32.
- H. L. Bodlaender. A linear time algorithm for finding tree-decompositions of small treewidth. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, STOC'93, pages 226-234. ACM, New York, USA, 1993. URL: http://dx.doi.org/10.1145/167088.167161.
- B. Courcelle. Graph rewriting: An algebraic and logic approach. In Formal Models and Semantics, volume B of Handbook of Theoretical Computer Science, pages 193-242. Elsevier, Amsterdam, Netherlands and MIT Press, Cambridge, Massachusetts, 1990. URL: http://dx.doi.org/10.1016/B978-0-444-88074-1.50010-X.
- M. Elberfeld, A. Jakoby, and T. Tantau. Logspace Versions of the Theorems of Bodleander and Courcelle. In Proceedings of the Annual IEEE Symposium on Foundations of Computer Science, October 23-26, 2010, Las Vegas, USA, FOCS'10, pages 143-152. IEEE Computer Society, Los Alamitos, California, 2010. URL: http://dx.doi.org/10.1109/FOCS.2010.21.
- M. Elberfeld, A. Jakoby, and T. Tantau. Algorithmic meta theorems for circuit classes of constant and logarithmic depth. In Proceedings of the Twenty-Ninth International Symposium on Theoretical Aspects of Computer Science, February 29 - March 3, 2012, Prais, France, STACS'12, pages 66-77. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2012.66.
- J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, Heidelberg, Germany, 2006. URL: http://dx.doi.org/10.1007/3-540-29953-X.
- A. Goldberg, S. Plotkin, and G. Shannon. Parallel symmetry-breaking in sparse graphs. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC'87, pages 315-324. ACM, New York, USA, 1987. URL: http://dx.doi.org/10.1145/28395.28429.
- M. Grohe and S. Kreutzer. Methods for algorithmic meta theorems. In Model Theoretic Methods in Finite Combinatorics, pages 181-206. AMS, Contemporary Mathematics Series, 2011. URL: http://dx.doi.org/10.1090/conm/558/11051.
- Neil Immerman. Languages which capture complexity classes. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC'83, pages 347-354. ACM New York, NY, 1983. URL: http://dx.doi.org/10.1145/800061.808765.
- Stephan Kreutzer. Algorithmic meta-theorems. CoRR, abs/0902.3616, 2009. URL: http://arxiv.org/abs/0902.3616.
- Jens Lagergren. Efficient parallel algorithms for graphs of bounded tree-width. Journal of Algorithms, 20:20-44, 1996. URL: http://dx.doi.org/10.1006/jagm.1996.0002.
- Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity. Springer Berlin Heidelberg, 2012. URL: http://dx.doi.org/10.1007/978-3-642-27875-4.
- Egon Wanke. Bounded tree-width and logcfl. Graph-Theoretic Concepts in Computer Science, 790:33-44, 2005. URL: http://dx.doi.org/10.1006/jagm.1994.1022.