Research Article: Clifford Algebras Meet Tree Decompositions

Date Published: July 30, 2018

Publisher: Springer US

Author(s): Michał Włodarczyk.

http://doi.org/10.1007/s00453-018-0489-3

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 documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$O^*((2^omega + 1)^{tw})$$end{document}O∗((2ω+1)tw)-time algorithm for counting Steiner trees and an documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$O^*((2^omega + 2)^{tw})$$end{document}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 documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$omega = 2$$end{document}ω=2.

Partial Text

The concept of treewidth has been introduced by Robertson and Seymour in their work on graph minors [13]. The treewidth of a graph is the smallest possible width of its tree decomposition, i.e., a tree-like representation of the graph. Its importance follows from the fact that many NP-hard graph problems become solvable on trees with a simple dynamical programming algorithm. A similar idea of pathwidth captures the width of a graph in case we would like to have a path decomposition. Formal definitions can be found in Sect. 2.2.

We will start with notation conventions.documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$A uplus B = C$$end{document}A⊎B=C stands for documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$(A cup B = C) wedge (A cap B = emptyset )$$end{document}(A∪B=C)∧(A∩B=∅).documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$A triangle B = (A backslash B) cup (B backslash A)$$end{document}A▵B=(AB)∪(BA).documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$[alpha ]$$end{document}[α] equals 1 if condition documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$alpha $$end{document}α holds and 0 otherwise.For permutation f of a linearly ordered set Udocumentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$begin{aligned} text {sgn}(f) = (-1)^{|{(a,b) in U times U ,wedge , a < b ,wedge , f(a) > f(b)}|}. end{aligned}$$end{document}sgn(f)=(-1)|{(a,b)∈U×U∧af(b)}|.For A, B being subsets of a linearly ordered set 1documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$begin{aligned} I_{A,B} = (-1)^{|{(a,b) in A times B ,wedge , a > b}|}. end{aligned}$$end{document}IA,B=(-1)|{(a,b)∈A×B∧a>b}|.Let us note two simple properties of I.

Some terms used in this section originate from the advanced algebra. For better understanding we suggest reading “Appendix A”.

We consider a linearly ordered universe U of size n and functions documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$f,g:2^U longrightarrow mathbb {Z}$$end{document}f,g:2U⟶Z.

We will revisit the theorem stated in the aforementioned work.

Likewise in the previous section, we will start with a previously known theorem.

We have presented the Non-commutative Subset Convolution, a new algebraic tool in algorithmics based on the theory of Clifford algebras. This allowed us to construct faster deterministic algorithms for Steiner Tree, Feedback Vertex Set, and Hamiltonian Cycle, parameterized by the treewidth. As the determinant-based approach applies to all problems solvable by the Cut & Count technique [4, 8], the NSC can improve running times for a larger class of problems.

 

Source:

http://doi.org/10.1007/s00453-018-0489-3

 

0 0 vote
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments