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

Author Magnus Wahlström



PDF
Thumbnail PDF

File

LIPIcs.STACS.2013.341.pdf
  • Filesize: 0.55 MB
  • 12 pages

Document Identifiers

Author Details

Magnus Wahlström

Cite AsGet BibTex

Magnus Wahlström. Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 341-352, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
https://doi.org/10.4230/LIPIcs.STACS.2013.341

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).
Keywords
  • Parameterized complexity
  • graph theory
  • kernelization
  • algebraic algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail