Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with fixed parameter tractability:
TR01-023 | 13th March 2001
Jochen Alber, Henning Fernau, Rolf Niedermeier

Parameterized Complexity: Exponential Speed-Up for Planar Graph Problems

Revisions: 1

A parameterized problem is called fixed parameter tractable
if it admits a solving algorithm whose running time on
input instance $(I,k)$ is $f(k) \cdot |I|^\alpha$, where $f$
is an arbitrary function depending only on~$k$. Typically,
$f$ is some exponential function, e.g., $f(k)=c^k$ for ... more >>>

TR07-055 | 22nd May 2007
Oliver Kullmann

Constraint satisfaction problems in clausal form: Autarkies and minimal unsatisfiability

Revisions: 1

We consider the next step from boolean conjunctive normal forms to
arbitrary constraint satisfaction problems (with arbitrary constraints), namely "generalised clause-sets" (or "sets of no-goods"), which allow negative literals "v <> e" for variables v and values e --- this level of generality appears to be the right level for ... more >>>

TR09-093 | 8th October 2009
Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda

Colored Hypergraph Isomorphism is Fixed Parameter Tractable

Revisions: 1

We describe a fixed parameter tractable (fpt) algorithm for Colored Hypergraph Isomorphism} which has running time $b!2^{O(b)}N^{O(1)}$, where the parameter $b$ is the maximum size of the color classes of the given hypergraphs and $N$ is the input size. We also describe fpt algorithms for certain permutation group problems that ... more >>>

TR15-013 | 28th January 2015
Subhash Khot, Igor Shinkar

On Hardness of Approximating the Parameterized Clique Problem

In the $Gap-clique(k, \frac{k}{2})$ problem, the input is an $n$-vertex graph $G$, and the goal is to decide whether $G$ contains a clique of size $k$ or contains no clique of size $\frac{k}{2}$. It is an open question in the study of fixed parameterized tractability whether the $Gap-clique(k, \frac{k}{2})$ problem ... more >>>

TR15-157 | 1st September 2015
Thomas O'Neil

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

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 ... more >>>

TR21-112 | 30th July 2021
Vikraman Arvind, Venkatesan Guruswami

CNF Satisfiability in a Subspace and Related Problems

We introduce the problem of finding a satisfying assignment to a CNF formula that must further belong to a prescribed input subspace. Equivalent formulations of the problem include finding a point outside a union of subspaces (the Union-of-Subspace Avoidance (USA) problem), and finding a common zero of a system of ... more >>>

ISSN 1433-8092 | Imprint