Document Open Access Logo

Patching Colors with Tensors

Author Cornelius Brand

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.25.pdf
  • Filesize: 487 kB
  • 16 pages

Document Identifiers

Author Details

Cornelius Brand
  • Saarland University (MMCI), Saarland Informatics Campus, Germany

Acknowledgements

I want to thank Sarah Berger, Markus Bläser, Radu Curticapean, Holger Dell, Thore Husfeldt, Christian Ikenmeyer, Fahad Panolan, Petteri Kaski, Mikko Koivisto and Meirav Zehavi for helpful discussions and valuable suggestions. I also thank the anonymous referees for their proposed improvements of the manuscript.

Cite As Get BibTex

Cornelius Brand. Patching Colors with Tensors. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 25:1-25:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ESA.2019.25

Abstract

We describe a generic way of exponentially speeding up algorithms which rely on Color-Coding by using the recently introduced technique of Extensor-Coding (Brand, Dell and Husfeldt, STOC 2018). To demonstrate the usefulness of this "patching" of Color-Coding algorithms, we apply it ad hoc to the exponential-space algorithms given in Gutin et al. (Journal Comp. Sys. Sci. 2018) and obtain the fastest known deterministic algorithms for, among others, the k-internal out-branching and k-internal spanning tree problems. To realize these technical advances, we make qualitative progress in a special case of the detection of multilinear monomials in multivariate polynomials: We give the first deterministic fixed-parameter tractable algorithm for the k-multilinear detection problem on a class of arithmetic circuits that may involve cancellations, as long as the computed polynomial is promised to satisfy a certain natural condition.
Furthermore, we explore the limitations of using this very approach to speed up algorithms by determining exactly the dimension of a crucial subalgebra of extensors that arises naturally in the instantiation of the technique: It is equal to F_{2k+1}, the kth odd term in the Fibonacci sequence. To determine this dimension, we use tools from the theory of Gröbner bases, and the studied algebraic object may be of independent interest.
We note that the asymptotic bound of F_{2k+1} ~~ phi^(2k) = O(2.619^k) curiously coincides with the running time bound on one of the fastest algorithms for the k-path problem based on representative sets due to Fomin et al. (JACM 2016). Here, phi is the golden ratio.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Graph algorithms analysis
  • Computing methodologies → Algebraic algorithms
Keywords
  • Color-Coding
  • Extensor-Coding
  • internal out-branching
  • colorful problems
  • algebraic algorithms
  • multilinear detection
  • deterministic algorithms
  • exterior algebra

Metrics

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

References

  1. Noga Alon, Raphael Yuster, and Uri Zwick. Color-Coding. J. ACM, 42(4):844-856, 1995. URL: https://doi.org/10.1145/210332.210337.
  2. Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhopadhyay. Fast Exact Algorithms Using Hadamard Product of Polynomials. CoRR, abs/1807.04496, 2018. URL: http://arxiv.org/abs/1807.04496.
  3. Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhopadhyay. Univariate Ideal Membership Parameterized by Rank, Degree, and Number of Generators. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018, December 11-13, 2018, Ahmedabad, India, pages 7:1-7:18, 2018. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2018.7.
  4. Garrett Birkhoff and Saunders Mac Lane. Algebra. AMS, 1999. Google Scholar
  5. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Fourier meets Möbius: Fast subset convolution. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pages 67-74, 2007. URL: https://doi.org/10.1145/1250790.1250801.
  6. Andreas Björklund, Vikram Kamat, Lukasz Kowalik, and Meirav Zehavi. Spotting Trees with Few Leaves. SIAM J. Discrete Math., 31(2):687-713, 2017. URL: https://doi.org/10.1137/15M1048975.
  7. Andreas Björklund, Petteri Kaski, and Ioannis Koutis. Directed Hamiltonicity and Out-Branchings via Generalized Laplacians. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pages 91:1-91:14, 2017. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.91.
  8. Cornelius Brand. Paths and Walks, Forests and Planes. PhD thesis, Saarland University, 2019. Google Scholar
  9. Cornelius Brand, Holger Dell, and Thore Husfeldt. Extensor-coding. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 151-164, New York, NY, USA, 2018. ACM. URL: https://doi.org/10.1145/3188745.3188902.
  10. Jianer Chen, Songjian Lu, Sing-Hoi Sze, and Fenghui Zhang. Improved algorithms for path, matching, and packing problems. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, pages 298-307, 2007. URL: http://dl.acm.org/citation.cfm?id=1283383.1283415.
  11. Nathann Cohen, Fedor V. Fomin, Gregory Z. Gutin, Eun Jung Kim, Saket Saurabh, and Anders Yeo. Algorithm for finding k-vertex out-trees and its application to k-internal out-branching problem. J. Comput. Syst. Sci., 76(7):650-662, 2010. URL: https://doi.org/10.1016/j.jcss.2010.01.001.
  12. Artur Czumaj, editor. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.
  13. Jean Daligault. Techniques combinatoires pour les algorithmes paramétrés et les noyaux, avec applications aux problèmes de multicoupe. (Combinatorial Techniques for Parameterized Algorithms and Kernels, with Applications to Multicut.). PhD thesis, Montpellier 2 University, France, 2011. URL: https://tel.archives-ouvertes.fr/tel-00804206.
  14. Henning Fernau, Serge Gaspers, and Daniel Raible. Exact and parameterized algorithms for max internal spanning tree. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 100-111. Springer, 2009. Google Scholar
  15. Uffe Flarup, Pascal Koiran, and Laurent Lyaudet. On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices. In Algorithms and Computation, 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2007, Proceedings, pages 124-136, 2007. URL: https://doi.org/10.1007/978-3-540-77120-3_13.
  16. Fedor V Fomin, Serge Gaspers, Saket Saurabh, and Stéphan Thomassé. A linear vertex kernel for maximum internal spanning tree. Journal of Computer and System Sciences, 79(1):1-6, 2013. Google Scholar
  17. Fedor V. Fomin, Fabrizio Grandoni, Daniel Lokshtanov, and Saket Saurabh. Sharp Separation and Applications to Exact and Parameterized Algorithms. Algorithmica, 63(3):692-706, 2012. URL: https://doi.org/10.1007/s00453-011-9555-9.
  18. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Representative Sets of Product Families. In Andreas S. Schulz and Dorothea Wagner, editors, Algorithms - ESA 2014 - 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings, volume 8737 of Lecture Notes in Computer Science, pages 443-454. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-44777-2_37.
  19. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms. J. ACM, 63(4):29:1-29:60, 2016. URL: https://doi.org/10.1145/2886094.
  20. Ira M. Gessel and Richard P. Stanley. Algebraic Enumeration. In R. L. Graham, M. Grötschel, and L. Lovász, editors, Handbook of Combinatorics (Vol. 2), pages 1021-1061. MIT Press, Cambridge, MA, USA, 1995. URL: http://dl.acm.org/citation.cfm?id=233228.233231.
  21. Gregory Gutin, Igor Razgon, and Eun Jung Kim. Minimum leaf out-branching and related problems. Theoretical Computer Science, 410(45):4571-4579, 2009. Google Scholar
  22. Gregory Z. Gutin, Felix Reidl, Magnus Wahlström, and Meirav Zehavi. Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials. J. Comput. Syst. Sci., 95:69-85, 2018. URL: https://doi.org/10.1016/j.jcss.2018.01.004.
  23. Mark Jerrum and Marc Snir. Some Exact Complexity Results for Straight-Line Computations over Semirings. J. ACM, 29(3):874-897, 1982. URL: https://doi.org/10.1145/322326.322341.
  24. Ioannis Koutis. Faster Algebraic Algorithms for Path and Packing Problems. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games, volume 5125 of Lecture Notes in Computer Science, pages 575-586. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-70575-8_47.
  25. Ioannis Koutis and Ryan Williams. Algebraic fingerprints for faster algorithms. Commun. ACM, 59(1):98-105, 2016. URL: https://doi.org/10.1145/2742544.
  26. Ioannis Koutis and Ryan Williams. Limits and Applications of Group Algebras for Parameterized Problems. ACM T. Algorithms, 12(3):31:1-31:18, 2016. URL: https://doi.org/10.1145/2885499.
  27. Wenjun Li, Yixin Cao, Jianer Chen, and Jianxin Wang. Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree. Inf. Comput., 252:187-200, 2017. URL: https://doi.org/10.1016/j.ic.2016.11.003.
  28. Kevin Pratt. Faster Algorithms via Waring Decompositions. CoRR, abs/1807.06194, 2018. URL: http://arxiv.org/abs/1807.06194.
  29. Elena Prieto and Christian Sloper. Reducing to independent set structure: the case of k-internal spanning tree. Nordic Journal of Computing, 12(3):308-318, 2005. Google Scholar
  30. Andrew James Stothers. On the complexity of matrix multiplication. PhD thesis, The University of Edinburgh, 2010. Google Scholar
  31. Seinosuke Toda. Classes of arithmetic circuits capturing the complexity of computing the determinant. IEICE Transactions on Information and Systems, 75(1):116-124, 1992. Google Scholar
  32. Chris Umans. Fast generalized DFTs for all finite groups. CoRR, abs/1901.02536, 2019. URL: http://arxiv.org/abs/1901.02536.
  33. Ryan Williams. Finding paths of length k in O(2^k) time. Inform. Process. Lett., 109(6):315-318, 2009. URL: https://doi.org/10.1016/j.ipl.2008.11.004.
  34. Virginia Vassilevska Williams. Multiplying matrices faster than coppersmith-winograd. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 887-898, 2012. URL: https://doi.org/10.1145/2213977.2214056.
  35. Michał Włodarczyk. Clifford Algebras Meet Tree Decompositions. 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 29:1-29:18. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.IPEC.2016.29.
  36. Meirav Zehavi. Mixing Color Coding-Related Techniques. In Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, pages 1037-1049, 2015. URL: https://doi.org/10.1007/978-3-662-48350-3_86.
  37. Meirav Zehavi. Mixing Color Coding-Related Techniques. In Proceedings of the 23rd Annual European Symposium on Algorithms (ESA), volume 9294, pages 1037-1049. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48350-3_86.
  38. Meirav Zehavi. Algorithms for k-Internal Out-Branching and k-Tree in Bounded Degree Graphs. Algorithmica, 78(1):319-341, May 2017. URL: https://doi.org/10.1007/s00453-016-0166-3.
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