Complexite parametree Recherche de noyaux bornes inferieures

Complexite parametree Recherche de noyaux bornes inferieures

89

pages

Français

Documents

Écrit par
Christophe Paul

Publié par
pefav

Lire un extrait

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Découvre YouScribe en t'inscrivant gratuitement

89

pages

Français

Ebook

Lire un extrait

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

Nombre de lectures

29

Langue

Français

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é par

Nombre de lectures

29

Langue

Français

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´eﬁnitionetexemple R´eductionsnon-triviales

Compositionscrois´ees D´eﬁnitionetthe´ore`mes Dominating set

Observation Lethe´ore`meprouvant,pourunprobl`emepara´tr´e(Q, κ), me l’e´quivalenceentrel’existenced’unnoyauetsonappartenance`ala classedecomplexite´FPT,nepermetquedede´duiredesnoyaux de tailles exponentiels.

I

Peut-onde´montrerquecertainsprobl`emesn’admettentpasde noyau polynomial ?

L exemple deEdge ’

I I

Clique-Cover

Un grapheG= (V,Ete`mer)unetrapak∈N Peut-oncouvrirlesar`etesEpar au pluskcliques ?

L’exemple deEdge

Clique-Cover

Theore`me[Gramm,Guo,H¨uﬀner,Niedermeier] ´ Edge Clique-Coveradmet un noyau de taille 2ksommets.

L’exemple deEdge

Clique-Cover

The´ore`me[Gramm,Guo,H¨uﬀner,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 ?

Univers
Ebooks
Livres audio
Presse
Podcasts
BD
Documents

© 2010-2024 YouScribe

Livre audio en ligne - Développement personnel Livre en ligne Tout le catalogue Tous les Intérêts