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 ) 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.
展开▼
