Complexite parametree Recherche de noyaux bornes inferieures

De
Publié par

Complexite parametree (3) Recherche de noyaux - bornes inferieures Christophe PAUL (CNRS - LIRMM)

  • algorithmes de distillation et de composition conjecture

  • probleme ouvert

  • classe de complexite fpt

  • deduire des noyaux de tailles exponentiels

  • noyau polynomial


Publié le : mardi 19 juin 2012
Lecture(s) : 29
Source : lirmm.fr
Nombre de pages : 89
Voir plus Voir moins
Complexit´eparam´etr´ee(3) Recherchedenoyaux-bornesinfe´rieures
Christophe PAUL (CNRS - LIRMM)
Noyaux exponentiels Edge Clique-Cover Longest Path
Algorithmes de distillation et de composition Conjecture deou-distillation Non-existence de noyau polynomial Exemples
Transformationsparame´tre´espolynomiales D´enitionetexemple R´eductionsnon-triviales
Compositionscrois´ees D´enitionetthe´ore`mes Dominating set
Observation Lethe´ore`meprouvant,pourunprobl`emepara´tr´e(Q, κ), me le´quivalenceentrelexistencedunnoyauetsonappartenance`ala classedecomplexite´FPT,nepermetquedede´duiredesnoyaux de tailles exponentiels.
I
Peut-onde´montrerquecertainsprobl`emesnadmettentpasde noyau polynomial ?
L exemple deEdge
I I
Clique-Cover
Un grapheG= (V,Ete`mer)unetrapakN Peut-oncouvrirlesar`etesEpar au pluskcliques ?
L’exemple deEdge
Clique-Cover
Theore`me[Gramm,Guo,H¨uner,Niedermeier] ´ Edge Clique-Coveradmet un noyau de taille 2ksommets.
L’exemple deEdge
Clique-Cover
The´ore`me[Gramm,Guo,H¨uner,Niedermeier] Edge Clique-Coveradmet un noyau de taille 2ksommets.
R`eglesder´eduction 1.sselremisistemmos´eolupprS 2.S’il existe deux sommetsxetytels queN[x] =N[y], supprimer l’un des deux sommets.
L’ emple deEdge ex
Clique-Cover
Th´eor`eme[Gramm,Guo,Hu¨ner,Niedermeier] Edge Clique-Coveradmet un noyau de taille 2ksommets.
Preuve :Supposons qu’il existekcliquesC1. . .Ck A chaque sommetxon asscocie un verteurCdek
Observation :
C[x,i] = 1
⇐⇒
x
Ci
couvrantE. bits tel que
i[k]C[x,i] =C[y,i] ssiN[x] =N[y]
L’exemple deEdge
Clique-Cover
The´ore`me[Gramm,Guo,Hu¨ner,Niedermeier] Edge Clique-Coveradmet un noyau de taille 2ksommets.
Preuve :Supposons qu’il existekcliquesC1. . .Ck A chaque sommetxon asscocie un verteurCdek
Observation :
C[x,i] = 1
⇐⇒
x
Ci
couvrantE. bits tel que
i[k]C[x,i] =C[y,i] ssiN[x] =N[y]
Probl`emeouvert Edge Clique-Coveradmet-il un noyau polynomial ?
Longest
I
I
Path
Un grapheG= (V,Eetm`re)nutearapkN Gcontient-il un chemin de taillek?
Longest PathestNP-Complet(cf. chemin hamiltonien) mais peut-etrere´soluentempsO(ck.nO(1))grˆca`eaColor Coding. ˆ
Longest
Path
Hypothe`seIl existe un algorithme de kernelizationApour Longest Pathqui retourne un noyau polynomial.
I
construisons une instance (G,k) avectesntre´eisdscteiann (G,k) = (G1,k)(G2,k). . .(Gt,k)
Longest
Path
Hypoth`eseIl existe un algorithme de kernelizationApour Longest Pathqui retourne un noyau polynomial.
I
construisons une instance (G,k) avects´ecindnaetrseniset (G,k) = (G1,k)(G2,k). . .(Gt,k)
Observation :(G,k) admet un chemin de longueurkssiitqGi admet un chemin de taillek.
Question : Est-il possible queAidentifie en temps polynomial quelGi, parmi les 22nopssbielrueugnoledniemchunde`esspos,k?
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.