W-Hierarchies defined by symmetric gates

Title: W-Hierarchies defined by symmetric gates
Creator: Fellows, Michael; Flum, Jörg; Hermelin, Danny; Müller, Moritz; Rosamond, Frances
Relation: Theory of Computing Systems Vol. 46, Issue 2, p. 311-339
Publisher Link: http://dx.doi.org/10.1007/s00224-008-9138-6
Publisher: Springer
Resource Type: journal article
Date: 2010
Description: The classes of the W-hierarchy are the most important classes of intractable problems in parameterized complexity. These classes were originally defined via the weighted satisfiability problem for Boolean circuits. Here, besides the Boolean connectives we consider connectives such as majority, not-all-equal, and unique. For example, a gate labelled by the majority connective outputs true if more than half of its inputs are true. For any finite set C of connectives we construct the corresponding W( C )-hierarchy. We derive some general conditions which guarantee that the W-hierarchy and the W( C )-hierarchy coincide levelwise. If C only contains the majority connective then the first levels of the hierarchies coincide. We use this to show that a variant of the parameterized vertex cover problem, the majority vertex cover problem, is W[1]-complete.
Subject: parameterized complexity; W-hierarchy; symmetric gates; bounded weft circuits
Identifier: http://hdl.handle.net/1959.13/922189
Identifier: uon:9504
Identifier: ISSN:1432-4350
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format