Document Open Access Logo

Fast Parallel Fixed-parameter Algorithms via Color Coding

Authors Max Bannach, Christoph Stockhusen, Till Tantau

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2015.224.pdf
  • Filesize: 0.5 MB
  • 12 pages

Document Identifiers

Author Details

Max Bannach
Christoph Stockhusen
Till Tantau

Cite As Get BibTex

Max Bannach, Christoph Stockhusen, and Till Tantau. Fast Parallel Fixed-parameter Algorithms via Color Coding. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 224-235, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.IPEC.2015.224

Abstract

Fixed-parameter algorithms have been successfully applied to solve numerous difficult problems within acceptable time bounds on large inputs. However, most fixed-parameter algorithms are inherently sequential and, thus, make no use of the parallel hardware present in modern computers. We show that parallel fixed-parameter algorithms do not only exist for numerous parameterized problems from the literature - including vertex cover, packing problems, cluster editing, cutting vertices, finding embeddings, or finding matchings - but that there are parallel algorithms working in constant time or at least in time depending only on the parameter (and not on the size of the input) for these problems. Phrased in terms of complexity classes, we place numerous natural parameterized problems in parameterized versions of AC^0. On a more technical level, we show how the color coding method can be implemented in constant time and apply it to embedding problems for graphs of bounded tree-width or tree-depth and to model checking first-order formulas in graphs of bounded degree.

Subject Classification

Keywords
  • color coding
  • parallel computation
  • fixed-parameter tractability
  • graph packing
  • cutting $ell$ vertices
  • cluster editing
  • tree-width
  • tree-depth,

Metrics

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

References

  1. F. N. Abu-Khzam, M. A. Langston, P. Shanbhag, and C. T. Symons. Scalable Parallel Algorithms for FPT Problems. Algorithmica, 45(3):269-284, 2006. Google Scholar
  2. N. Alon, R. Yuster, and U. Zwick. Color-Coding. Journal of the ACM, 42(4):844-856, 1995. Google Scholar
  3. Kazuyuki Amano. k-Subgraph Isomorphism on AC⁰ Circuits. Computational Complexity, 19(2):1016-3328, 2010. Google Scholar
  4. David A. Mix Barrington and Neil Immerman. On uniformity within \mathchoice \fontsize9pt 10pt\selectfontNC \fontsize9pt 10pt\selectfontNC NC NC¹. Journal of Computer and System Sciences, 41(3):274-306, 1990. Google Scholar
  5. Paul Beame, Russell Impagliazzo, and Toniann Pitassi. Improved depth lower bounds for small distance connectivity. Computational Complexity, 7(4):325-345, 1998. Google Scholar
  6. S. Böcker. A Golden Ratio Parameterized Algorithm for Cluster Editing. In Proceedings of the Twenty-Second International Workshop on Combinatorial Algorithms, volume 7056 of IWOCA'11, pages 85-95. Springer Berlin Heidelberg, 2011. Google Scholar
  7. S. Böcker and J. Baumbach. Cluster Editing. In Proceedings of the Ninth Conference on Computability in Europe, volume 7921 of CiE'13, pages 33-44. Springer Berlin Heidelberg, 2013. Google Scholar
  8. L. Cai, J. Chen, R. G. Downey, and M. R. Fellows. Advice Classes of Parameterized Tractability. Annals of Pure and Applied Logic, 84(1):119-138, 1997. Google Scholar
  9. Marco Cesati and Miriam Di Ianni. Parameterized parallel complexity. In Proceedings of the Fourth International Euro-Par Conference, volume 1470 of Euro-Par'89, pages 892-896. Springer Berlin Heidelberg, 1998. Google Scholar
  10. H. Chen and M. Müller. The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space. ACM Transactions on Computation Theory, 7(2):7:1-7:27, 2014. Google Scholar
  11. Y. Chen, J. Flum, and M. Grohe. Bounded Nondeterminism and Alternation in Parameterized Complexity Theory. In Proceedings of the Eighteenth IEEE Conference on Computational Complexity, CCC'03, pages 13-29. IEEE Computer Society, Los Alamitos, California, 2003. Google Scholar
  12. R.G. Downey and M.R. Fellows. Parameterized Complexity. Springer, 1999. Google Scholar
  13. Rodney G. Downey, Michael R. Fellows, and Kenneth W. Regan. Parameterized Circuit Complexity and the W Hierarchy. Theoretical Computer Science, 191(1-2):97-115, 1998. Google Scholar
  14. M. Elberfeld, C. Stockhusen, and T. Tantau. On the Space Complexity of Parameterized Problems: Classes and Completness. Algorithmica, 71(3):661-701, 2014. Google Scholar
  15. M. Fellows, P. Heggernes, F. Rosamond, C. Sloper, and J. A. Telle. Finding k Disjoint Triangles in an Arbitrary Graph. In Proceedings of the Thirtieth International Workshop on Graph-Theoretic Concepts in Computer Science, volume 3353 of WG'04, pages 235-244. Springer Berlin Heidelberg, 2004. Google Scholar
  16. J. Flum and M. Grohe. Describing Parameterized Complexity Classes. In Proceedings of the Nineteenth Annual Symposium on Theoretical Aspects of Computer Science, volume 2285 of STACS'02, pages 359-371. Springer Berlin Heidelberg, 2002. Google Scholar
  17. J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, 2006. Google Scholar
  18. F. V. Fomin, P. A. Golovach, and J. H. Korhonen. On the Parameterized Complexity of Cutting a Few Vertices from a Graph. In Proceedings of the Thirty-Eight International Symposium of Mathematical Foundations of Computer Science, volume 8087 of MFCS '13, pages 421-432. Springer, Heidelberg, Germany, 2013. Google Scholar
  19. F. V. Fomin, S. Kratsch, M. Pilipczuk, M. Pilipczuk, and Y. Villanger. Tight Bounds for Parameterized Complexity of Cluster Editing. In Proceedings of the Thirtieth International Symposium on Theoretical Aspects of Computer Science, volume 20 of STACS'13, pages 30-43. International Symposium on Theoretical Aspects of Computer Science, 2013. Google Scholar
  20. H. Gaifman. On Local and Non-Local Properties. In Proceedings of the Herbrand Symposium, Logic Colloquium 1981, pages 105-135. North Holland, 1982. Google Scholar
  21. J. Gramm, J. Guo, F. Hüffner, and R. Niedermeier. Graph-Modeled Data Clustering: Fixed-Parameter Algorithms for Clique Generation. In Proceedings of the Fifth Italian Conference of Algorithms and Complexity, volume 2653 of CIAC'03, pages 108-119. Springer Berlin Heidelberg, 2003. Google Scholar
  22. D. Marx. Parameterized Graph Separation Problems. Theoretical Computer Science, 351(3):394-406, 2006. Google Scholar
  23. I. Newman, P. Ragde, and A. Wigderson. Perfect Hashing, Graph Entropy, and Circuit Complexity. In Proceedings of the Fifth Annual Structure in Complexity Theory Conference, pages 91-99. IEEE Computer Society, Los Alamitos, California, 1990. Google Scholar
  24. H. Vollmer. Introduction to Circuit Complexity. Springer, 1999. 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