LIPIcs.CPM.2020.1.pdf
- Filesize: 200 kB
- 1 pages
Document
Algebraic Algorithms for Finding Patterns in Graphs (Invited Talk)
Author
Thore Husfeldt 
-
Part of:
Volume:
31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Annual Symposium on Combinatorial Pattern Matching (CPM) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-06-09
File
Document Identifiers
Author Details
Acknowledgements
Based on joint work with Cornelius Brand and Holger Dell.
Cite As Get BibTex
Thore Husfeldt. Algebraic Algorithms for Finding Patterns in Graphs (Invited Talk). In 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 161, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.CPM.2020.1
Abstract
I will give a gentle introduction to algebraic graph algorithms by showing how to determine if a given graph contains a simple path of length k. This is a famous problem admitting a beautiful and widely-known algorithm, namely the colour-coding method of Alon, Yuster and Zwick (1995). Starting from this entirely combinatorial approach, I will carefully develop an algebraic perspective on the same problem. First, I will explain how the colour-coding algorithm can be understood as the evaluation of a well-known expression (sometimes called the "walk-sum" of the graph) in a commutative algebra called the zeon algebra. From there, I will introduce the exterior algebra and present the algebraic framework recently developed with Brand and Dell (2018). The presentation is aimed at a combinatorially-minded audience largely innocent of abstract algebra.
Subject Classification
ACM Subject Classification
- Theory of computation → Fixed parameter tractability
- Mathematics of computing → Paths and connectivity problems
- Mathematics of computing → Graph algorithms
Keywords
- paths
- exterior algebra
- wedge product
- color-coding
- parameterized complexity
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844-856, 1995. URL: https://doi.org/10.1145/210332.210337.
-
Cornelius Brand, Holger Dell, and Thore Husfeldt. Extensor-coding. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, page 151–164, New York, NY, USA, 2018. Association for Computing Machinery.
