La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

# 4ème Cours Cours MPRI 2010–2011

De
45 pages
4eme Cours Cours MPRI 2010{20114eme CoursCours MPRI 2010{2011Michel Habibhabib@liafa.jussieu.frhttp://www.liafa.jussieu.fr/ habib~Chevaleret, october 20104eme Cours Cours MPRI 2010{2011ScheduleSome NP-hard problemsPartition re nementInterval graph recognitionBack to graph searching4eme Cours Cours MPRI 2010{2011Some NP-hard problemsAnswer to one exerciceThe following decision problem is NP-completeD. Corneil, E. Kohler, J-M. Lanlignel, Discrete Applied Math. 2010Data: a graph G = (V; E ) and a given vertex x2 VResult: Does there exist a LexBFS of G ending in x ?Easy reduction from 3-SAT.4eme Cours Cours MPRI 2010{2011Some NP-hard problemsBack to chordal graphsChordal graph sumary1. Apply a graph search MNS (LexBFS or MCS) on G, in themeantime construct a tree T based on the strictly increasingsequences of labels.O(n + m). This step is greedy, i.e. with no backtrack.2. Check if the reverse ordering is a simplicial eliminationscheme. In case of success T is a maximal clique tree.Furthermore, using this simplicial elimination scheme manyoptimisation problems on G can be solved (minimum coloring,maximum clique . . .).O(n + m)3. In case of failure, exhibit a certi cate : i.e. a cycle of length 4, without a chord.O(n)4eme Cours Cours MPRI 2010{2011Some NP-hard problemsBack to chordal graphs IIMaximal cliques and minimal spearators1. One can extract in linear time the set of all maximal cliquesJust using a simplicial elemination ...
Voir plus Voir moins

Vous aimerez aussi

4`emeCours
Cours MPRI 2010–2011
4e`meCours Cours MPRI 2010–2011
Michel Habib habib@liafa.jussieu.fr http://www.liafa.jussieu.fr/~habib
Chevaleret, october 2010
4`emeCoursCoursMPRI20102011
Schedule
Some NP-hard problems
Partition reﬁnement
Interval graph recognition
Back to graph searching
4e`meCoursCoursMPRI20102011 Some NP-hard problems
Answer to one exercice
The following decision problem is NP-complete D. Corneil, E. Kohler, J-M. Lanlignel, Discrete Applied Math. 2010
Data: a graphG= (V,E) and a given vertexxV ResultDoes there exist a LexBFS of: Gending inx?
Easy reduction from 3-SAT.
4`emeCoursCoursMPRI20102011 Some NP-hard problems
Back to chordal graphs
Chordal graph sumary 1.Apply a graph search MNS (LexBFS or MCS) on G, in the meantime construct a treeTbased on the strictly increasing sequences of labels. O(n+m). This step isgreedy, i.e. with no backtrack. 2.Check if the reverse ordering is a simplicial elimination scheme. In case of successTis a maximal clique tree. Furthermore, using this simplicial elimination scheme many optimisation problems onGcan be solved (minimum coloring, maximum clique . . .). O(n+m) 3.In case of failure, exhibit a certiﬁcate : i.e. a cycle of length 4, without a chord. O(n)
4e`meCoursCoursMPRI20102011 Some NP-hard problems
Back to chordal graphs II
Maximal cliques and minimal spearators 1.One can extract in linear time the set of all maximal cliques Just using a simplicial elemination scheme.
2.of all minimal separators can be extracted from aThe set maximal clique tree.
4`emeCoursCoursMPRI20102011 Some NP-hard problems
Theorem Every minimal separator belongs to every maximal clique tree.
Lemma Every minimal separator is the intersection of at least 2 maximal cliques ofG.
4e`meCoursCoursMPRI20102011 Some NP-hard problems
Proof of the lemma
D´ nstratio emo n. We know thatSis a clique. Let us considerG1a connected component ofGS. Letx1, . . . ,xkbe the vertices ofG1having a maximal neighbourhood inS. Ifk= 1 thenx1must be universal toS, sinceSis a minimal separator. Else, consider a shortest pathµinG1fromx1toxk. Necessarilyx1 (resp.xk) has a private neighbourz(resp.t) inS. Then the cycle [x1, µ,xk,t,z] has no chord, a contradiction. Thereforex1Sis a clique, and is contained in some maximal cliqueCinG1. We ﬁnish the proof by taking another connected component ofGS.
4e`meCoursCoursMPRI20102011 Some NP-hard problems
Proof of the theorem
De´monstration. ThereforeS=C0C00. These two maximal cliques belong to any maximal clique treeTofG. Let us consider the unique pathµin TjoigningC0toC00. All the internal maximal cliques inµmust containS. Suppose that all the edges ofµare labelled with minimal separators strictly containingS, then we can construct a path inGfromC0Sto C00SavoidingS, a contradiction. So at least one edge ofµis labelled withS.
4`emeCoursCoursMPRI20102011 Some NP-hard problems
Since chordal graphs are well-known, it could be of interest to embed a graph into a chordal graph. Unfortunately the following problems are NP-hard :
1.Treewidth(G) =MinH triangulation of G{ω(H)1} 2.MinFillin(G) =MinH=(V,F) Gtriangulation of{|F|} 3.Pathwidth(G) =Min GH intervalcompletion of{ω(H)1} 4.lpteoinervalcomMinInt(G) = MinH=(V,F)intervalcompletion of G{|F|} 5.Theorem Arnborg, Corneil, Proskurowski, 1987 : These 4 problems are NP-hard.
`4emeoSCoemrusPNCh-oaurrdsMproPbRleI2sm1000211
Chordal sandwich problem is NP-complete
Data:G1= (V,E1)G2= (V,E2) two graphs, withE1E2 Result: Does there exist a chordal graphG= (V,E) withE1EE2? Such a graphGis called a sandwich graph, notion introduced by M. Golumbic, for the study of physical mapping of DNA in Biology.
Modelisation Sandwich problem allow to cope with uncertainity : E1is the set offorcededges (good data) E2E1is the set ofpossibleedges (some kind of uncertainity or fuzziness) X2E2is the set offorbiddenedges.
4`emeCoursCoursMPRI20102011 Some NP-hard problems
Perfect Phylogeny and chordal graphs
The data is an incidence matrix from a set of speciesS1, . . . ,Snto a set of attributesF1, . . . ,Fm. Attributes can have diﬀerent values (integers or colors). These species are modern species and we aim at reconstructing a plausible historical evolution treeT, ﬁnding ancestral species. InTvertices are species, and its leaves correspond toS1, . . . ,Sn and every value of an attribute must deﬁne a connected subtree.