7 jours d'essai offerts
Cet ouvrage et des milliers d'autres sont disponibles en abonnement pour 8,99€/mois
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 ?