Introduction A polynomial instance

Nicolas Bousquet

Description

Introduction A polynomial instance Reduction to the polynomial instance Conclusion Multicut is FPT Nicolas Bousquet Joint work with: Jean Daligault, Stephan Thomasse Nicolas Bousquet Multicut is FPT

• attachment vertices


• parameterized complexity


• instance


• binary tree


• introduction parameterized complexity


• fixed parameter


• can branch


• vertex


• cover

Sujets

• Bousquet
• Parameterized complexity
• Instance
• Binary tree
• Vertex

Informations

• Publié par: pefav
• Nombre de lectures: 31
• Langue: English

Extrait

Introduction Apoylonimlanitsnaec duReioctotntpoheonyllaimtsniecna lusiConcon asBousquNicolsituTPFuMtecitl

work

Joint

Thomass´e

with:JeanDaligault,Ste´phan

Multicut is FPT

Nicolas Bousquet

cutiulti

Introduction Parameterized complexity Multicut

1

2

sFPT

3

A polynomial instance

Reduction to the polynomial instance Vertex Multicut Reductions for one attachment vertex Two attachment vertices components

I poly ion A ductntro eR ecnatsnilaimon lypoheotntioctdu ulcnnois araPetem minoinalanst Co celuituct rizedcomplexity M uetMousqlasBNico isnocnul 4 oC

ucedontithtoolepmonyilaiatsn C ecn Introduction Apolnymoaiilsnatcn R e tucitluM mateP n ra suoinolc xitympleedcoeriz losaNciuqteoBsultMuuticFPis

FPT A parameterized problem isFPT(Fixed Parameter Tractable) iff there is an algorithm which runs in timePoly(n)∙f(k) for an instance of sizenand of parameterk.

T

oryaxy:xedgeckanCxvoreethtVeerni ranbca weceen.Her hcihwedicedothcn oorP iP :f tt t ocane ooesehhctex.nver rytrBinatpedfoeesomta:khncra k bt2 coNi s.he noiessleceetidtnheVertex Cover.Deaercbkesenoyddnaetelheetgeeddjsa

Theorem Vertex Cover parameterized by the

Example

Parameterized complexity Multicut

FPT.

is

size of the solution

itucTPFstMuetiulsBlasqou olynthepontouctiR e de atcnilsnmoaiynolAp ontiucodtrnI usclnio cnat noC eaimosnil

R ecnatsnilaimonyolAp ontiucodtrIn cn C esnataiilnymoepoltothtioneduc izercoedlemptyxi lcnooisu raP n tema uMtlcitu itucitFsTP

Example

Proof : Pick an edgexy:xoryare in the Vertex Cover. Hence we can branch to decide which one is selected in the Vertex Cover. Decreasekby one and delete the edges adjacent to the choosen vertex.

Theorem Vertex Cover parameterized by the size of the solution is FPT.

arb k 2tso iN .sehcn ousBlacoultMuesq anyriBofdetree:atmpthk

T

Example

Theorem Vertex Cover parameterized by the size of the solution is FPT.

Proof : Pick an edgexy:xoryare in the Vertex Cover. Hence we can branch to decide which one is selected in the Vertex Cover. Decreasekby one and delete the edges adjacent to the choosen vertex. Binary tree of depthk: at most 2 k branches.

citusiPFuqteuMtlciNsuoBsalo ulticut plexity M ezirmocdaraPetem lunconsi anst Co celanionimopyltoehiontduct ce Re stannilaimonylopA noictdurontI