Information about Fixed-Parameter Intractability

Vertex Cover Feedback Vertex Set Max Sat Odd Cycle Transversal Point Line Cover Feedback Arc Set on Tournaments 3-Hitting Set Closest String d-Clustering

Vertex Cover Feedback Vertex Set Max Sat Odd Cycle Transversal Point Line Cover Feedback Arc Set on Tournaments 3-Hitting Set Closest String d-Clustering f(k) n

Vertex Cover Feedback Vertex Set Max Sat O(1) Odd Cycle Transversal Point Line Cover Feedback Arc Set on Tournaments 3-Hitting Set Closest String d-Clustering f(k) n

Some problems tend to be harder than others.

FPT

FPT “Hard”

Your Problem

Your Problem Clique

solveClique{ blah blah Your Problem ! } Clique

Independent Set Clique

Independent Set Clique

SolveClique(G,k) { Return IndependentSet(Gc,k ); } Independent Set Clique

solveClique{ blah blah ! }

(x, k) (x , k ) A known “hard” problem Instance of “your problem” solveClique{ blah blah ! }

(x, k) (x , k ) A known “hard” problem Instance of “your problem” solveClique{ blah blah ! } The reduction itself must run in FPT time.

(x, k) (x , k ) A known “hard” problem Instance of “your problem” solveClique{ blah blah ! } The reduction itself must run in FPT time. The time taken to solve the generated instance will be f(k )p(|x |)

(x, k) (x , k ) A known “hard” problem Instance of “your problem” solveClique{ blah blah ! } The reduction itself must run in FPT time. So the parameter of the output is constrained to being a function of the original parameter.

SolveIndSet(G,k) { Return VertexCover(G,n-k ); }

SolveIndSet(G,k) { Return VertexCover(G,n-k ); }

NP-hardness reductions are not necessarily FPT reductions.

Given a graph G and a number k: ! return YES if k ≤ log n and G has a clique on k vertices.

Instance of CLIQUE, (G,k) Instance of log-CLIQUE, (G,k)

Instance of CLIQUE, (G,k) Instance of log-CLIQUE, (G,k)

Instance of CLIQUE, (G,k) Instance of log-CLIQUE, (G,k) Add 2k isolated vertices.

FPT reductions are not always NP-hardness reductions.

Multi-Colored Clique

Multi-Colored Clique

Multi-Colored Clique

Multi-Colored Clique

Multi-Colored Clique

Clique

Multi-Colored Clique

Multi-Colored Clique

Fixed-Parameter Intractability. on ResearchGate, the professional network for scientists.

Read more

The authors consider the complexity behavior of parametrized problems that they term fixed-parameter tractability: for each fixed parameter value y the ...

Read more

In this chapter, we use parameterized reductions and W[1]-hardness to provide evidence that certain parameterized problems are unlikely to be fixed ...

Read more

The authors consider the complexity behavior of parametrized problems that they term fixed-parameter tractability: for each fixed parameter value y the ...

Read more

CiteSeerX - Scientific documents that cite the following paper: Fixed-parameter intractability

Read more

K. Abrahamson, R. Downey, and M. Fellows, “Fixed Parameter Tractability and Completeness IV: W[P] and PSPACE,” to appear.

Read more

CiteSeerX - Scientific documents that cite the following paper: Fixed parameter intractability (extended abstract), in

Read more

SIAM Journal on Computing 31:1, ... Fixed-parameter intractability. [1992] Proceedings of the Seventh Annual Structure in Complexity Theory Conference, ...

Read more

Fixed-parameter tractability and completeness IV: ... address the apparent fixed-parameter intractability of problems such as Example 6.

Read more

Title: Fixed-parameter tractability, definability, and model checking Authors: Jörg Flum and Martin Grohe ... On the intractability side ...

Read more

## Add a comment