Clifford Algebras Meet Tree Decompositions

Author Michal Wlodarczyk



PDF
Thumbnail PDF

File

LIPIcs.IPEC.2016.29.pdf
  • Filesize: 0.53 MB
  • 18 pages

Document Identifiers

Author Details

Michal Wlodarczyk

Cite AsGet BibTex

Michal Wlodarczyk. Clifford Algebras Meet Tree Decompositions. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 29:1-29:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.IPEC.2016.29

Abstract

We introduce the Non-commutative Subset Convolution - a convolution of functions useful when working with determinant-based algorithms. In order to compute it efficiently, we take advantage of Clifford algebras, a generalization of quaternions used mainly in the quantum field theory. We apply this tool to speed up algorithms counting subgraphs parameterized by the treewidth of a graph. We present an O^*((2^omega + 1)^{tw})-time algorithm for counting Steiner trees and an O^*((2^omega + 2)^{tw})-time algorithm for counting Hamiltonian cycles, both of which improve the previously known upper bounds. The result for Steiner Tree also translates into a deterministic algorithm for Feedback Vertex Set. All of these constitute the best known running times of deterministic algorithms for decision versions of these problems and they match the best obtained running times for pathwidth parameterization under assumption omega = 2.
Keywords
  • fixed-parameter tractability
  • treewidth
  • Clifford algebra
  • algebra isomorphism

Metrics

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

References

  1. John A. Beachy. Introductory lectures on rings and modules, volume 47. Cambridge University Press, 1999. Google Scholar
  2. 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, STOC'07, pages 67-74, New York, NY, USA, 2007. ACM. URL: http://dx.doi.org/10.1145/1250790.1250801.
  3. Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on computing, 25(6):1305-1317, 1996. Google Scholar
  4. Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput., 243(C):86-111, August 2015. URL: http://dx.doi.org/10.1016/j.ic.2014.12.008.
  5. Marek Cygan. Private communication, 2016. Google Scholar
  6. Marek Cygan, Fedor Fomin, Bart MP Jansen, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Open problems for fpt school 2014. URL: http://fptschool.mimuw.edu.pl/opl.pdf.
  7. Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Fast hamiltonicity checking via bases of perfect matchings. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing, pages 301-310. ACM, 2013. Google Scholar
  8. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, pages 150-159. IEEE, 2011. Google Scholar
  9. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Representative sets of product families. In Algorithms - ESA 2014, pages 443-454. Springer, 2014. Google Scholar
  10. Ton Kloks. Treewidth: computations and approximations, volume 842. Springer Science &Business Media, 1994. Google Scholar
  11. Paul Leopardi. A generalized FFT for Clifford algebras. Bulletin of the Belgian Mathematical Society, 11(5):663-688, 03 2005. Google Scholar
  12. David K. Maslen and Daniel N. Rockmore. Generalized ffts - a survey of some recent results. In Groups and Computation II, volume 28, pages 183-287. American Mathematical Soc., 1997. Google Scholar
  13. Neil Robertson and Paul D. Seymour. Graph minors. III. Planar tree-width. Journal of Combinatorial Theory, Series B, 36(1):49-64, 1984. Google Scholar
  14. Johan M. M. van Rooij, Hans L. Bodlaender, and Peter Rossmanith. Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution, pages 566-577. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009. URL: http://dx.doi.org/10.1007/978-3-642-04128-0_51.
  15. Virginia Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing, pages 887-898. ACM, 2012. 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