# Fixed-Parameter Intractability

33 %
67 %
Technology

Published on March 5, 2014

Author: ASPAK2014

Source: slideshare.net

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”

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

 User name: Comment:

## Related presentations

#### Neuquén y el Gobierno Abierto

October 30, 2014

Presentación que realice en el Evento Nacional de Gobierno Abierto, realizado los ...

#### Decision CAMP 2014 - Erik Marutian - Using rules-b...

October 16, 2014

In this presentation we will describe our experience developing with a highly dyna...

#### Schema.org: What It Means For You and Your Library

November 7, 2014

Presentation to the LITA Forum 7th November 2014 Albuquerque, NM

#### WearableTech: Una transformación social de los p...

November 3, 2014

Un recorrido por los cambios que nos generará el wearabletech en el futuro

#### O Impacto de Wearable Computers na vida das pessoa...

November 5, 2014

Um paralelo entre as novidades & mercado em Wearable Computing e Tecnologias Assis...

#### All you need to know about the Microsoft Band

November 6, 2014

Microsoft finally joins the smartwatch and fitness tracker game by introducing the...

## Related pages

### Fixed-Parameter Intractability.

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

### IEEE Xplore Abstract - Fixed-parameter intractability

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

### Fixed-parameter intractability - Springer

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

### Fixed-Parameter Intractability | Michael Fellows ...

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

### CiteSeerX — Citation Query Fixed-parameter intractability

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

### Fixed-parameter intractability II (extended abstract ...

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

### Fixed parameter intractability (extended abstract), in (1992)

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

### SIAM Journal on Computing - Fixed-Parameter Tractability ...

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