Wahlström, Magnus
Abusing the Tutte Matrix: An Algebraic Instance Compression for the Ksetcycle Problem
Abstract
We give an algebraic, determinantbased algorithm for the KCycle 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 polynomialtime reduction of the KCycle problem into an algebraic problem with coding size O(K^3).
This is surprising, as several related problems (e.g., kCycle 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 KCycle 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 Ksetcycle Problem}},
booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
pages = {341352},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897507},
ISSN = {18688969},
year = {2013},
volume = {20},
editor = {Natacha Portier and Thomas Wilke},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2013/3946},
URN = {urn:nbn:de:0030drops39465},
doi = {10.4230/LIPIcs.STACS.2013.341},
annote = {Keywords: Parameterized complexity, graph theory, kernelization, algebraic algorithms}
}
26.02.2013
Keywords: 

Parameterized complexity, graph theory, kernelization, algebraic algorithms 
Seminar: 

30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Issue date: 

2013 
Date of publication: 

26.02.2013 