License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2013.341
URN: urn:nbn:de:0030-drops-39465
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/3946/
Go to the corresponding LIPIcs Volume Portal

Wahlström, Magnus

Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem

pdf-format:
34.pdf (0.6 MB)

Abstract

We give an algebraic, determinant-based algorithm for the K-Cycle problem, i.e., the problem of finding a cycle through a set of specified elements. Our approach gives a simple FPT algorithm for the problem, matching the O^*(2^|K|) running time of the algorithm of Björklund et al. (SODA, 2012). Furthermore, our approach is open for treatment by classical algebraic tools (e.g., Gaussian elimination), and we show that it leads to a polynomial compression of the problem, i.e., a polynomial-time reduction of the K-Cycle problem into an algebraic problem with coding size O(|K|^3).
This is surprising, as several related problems (e.g., k-Cycle and the Disjoint Paths problem) are known not to admit such a reduction unless the polynomial hierarchy collapses. Furthermore, despite the result, we are not aware of any witness for the K-Cycle problem of size polynomial in |K|+ log n, which seems (for now) to separate the notions of polynomial compression and polynomial kernelization (as a polynomial kernelization for a problem in NP necessarily implies a small witness).

BibTeX - Entry

@InProceedings{wahlstrm:LIPIcs:2013:3946,
  author =	{Magnus Wahlstr{\"o}m},
  title =	{{Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{341--352},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Natacha Portier and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/3946},
  URN =		{urn:nbn:de:0030-drops-39465},
  doi =		{10.4230/LIPIcs.STACS.2013.341},
  annote =	{Keywords: Parameterized complexity, graph theory, kernelization, algebraic algorithms}
}

Keywords: Parameterized complexity, graph theory, kernelization, algebraic algorithms
Collection: 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Issue Date: 2013
Date of publication: 26.02.2013

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