2016/09/22 by Michał Włodarczyk
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Combinatorics #Depth-first search #Discrete mathematics #Graph #Graph theory and applications #Interconnection Networks and Systems #Mathematics #Parameterized complexity #Pathwidth #Search algorithm #Steiner tree problem #Theory of computation #Treewidth #True quantified Boolean formula #acm:68W01 #cs.DS #msc:68W01
paper · pdf · doi:10.1007/s00453-018-0489-3
This work was presented at International Symposium on Parameterized and Exact Computation (IPEC) 2016
arxiv created 2016/09/22 · openalex publication_date 2018/07/30 · arxiv updated 2018/08/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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ω + 1)tw) -time algorithm for counting Steiner trees and an O^*((2ω + 2)tw) -time algorithm for counting Hamiltonian cycles, both of which improve the previously known upper bounds. These constitute also 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 ω = 2 .