Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-157 | 1st September 2015 18:20

Representation-Independent Fixed Parameter Tractability for Vertex Cover and Weighted Monotone Satisfiability


Authors: Thomas O'Neil
Publication: 28th September 2015 00:45
Downloads: 1420


A symmetric representation for a set of objects requires the same amount of space for the set as for its complement. Complexity classifications that are based on the length of the input can depend on whether the representation is symmetric. In this article we describe a symmetric representation scheme for graphs and show that published parameterized algorithms for Vertex Cover do not provide a representation-independent proof that Vertex Cover is Fixed Parameter Tractable. In response to this challenge, a simple specialized backtracking algorithm is given for Vertex Cover that maintains $f(|y|)\cdot|x|$ complexity even if the input $x$ is a symmetric representation of length $O((\lg n)^2)$ for a very sparse or very dense graph with $n$ vertices. The algorithm is then generalized to solve the Weighted Monotone q-Satisfiability problem, constituting representation-independent proof that these two problems are in FPT.

ISSN 1433-8092 | Imprint