advertisement

Fixed-Parameter Intractability

33 %
67 %
advertisement
Information about Fixed-Parameter Intractability
Technology
max

Published on March 5, 2014

Author: ASPAK2014

Source: slideshare.net

advertisement

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

Add a comment

Related presentations

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

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

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

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

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

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

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

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

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

CiteSeerX — Citation Query Fixed-parameter intractability

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

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

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

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

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

Fixed-parameter tractability and completeness IV: On ...

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

Fixed-parameter tractability, definability, and model checking

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