Fixed-parameter Intractability II (extended Abstract) |
Common terms and phrases
algorithm apparent fixed-parameter intractability Army Research Office AW complete basic module block boolean choice component Cholak chooses a member computable constants conjunctive normal form CORNELL UNIVERSITY decision circuit Definition density theorem Dominating Set Downey-Fellows EXTENDED ABSTRACT f.p. tractable fan-in fixed parameter tractable formula testing component fpp-reduces gates Geography is AW graph G Graph Minor hence hierarchy independent set input a pair literal vertex m-reduction Maximal Irredundant Set natural problems nonuniformly NP-complete number of rows pair G parame parameterized game problems parameterized problem parameterized reducibilities pertains polynomial problem takes proof of Ladner's prove PSPACE-complete recursive sets relevant Reset k(0 set in G Set is complete Short Geography shown single output standard enumeration strong uniform reducibilities strongly uniformly structure takes as input techniques three flavors uniformly f.p. tractable uniformly fixed-parameter tractable uniformly P-reducible variables vector version of R₁ Vertex Cover vertices in G weft weight