License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2016.29
URN: urn:nbn:de:0030-drops-69260
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/6926/
Go to the corresponding LIPIcs Volume Portal

Wlodarczyk, Michal

Clifford Algebras Meet Tree Decompositions

pdf-format:
LIPIcs-IPEC-2016-29.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{wlodarczyk:LIPIcs:2017:6926,
  author =	{Michal Wlodarczyk},
  title =	{{Clifford Algebras Meet Tree Decompositions}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{29:1--29:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Jiong Guo and Danny Hermelin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/6926},
  URN =		{urn:nbn:de:0030-drops-69260},
  doi =		{10.4230/LIPIcs.IPEC.2016.29},
  annote =	{Keywords: fixed-parameter tractability, treewidth, Clifford algebra, algebra isomorphism}
}

Keywords: fixed-parameter tractability, treewidth, Clifford algebra, algebra isomorphism
Collection: 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Issue Date: 2017
Date of publication: 09.02.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI