4ème Cours Cours MPRI 2010–2011

Michel Habib [e-mail] ` `%%%`#`&12_`__~~~ Alse

Description

4eme Cours Cours MPRI 2010{20114eme CoursCours MPRI 2010{2011Michel [e-mail]://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 ...

Informations

• Publié par: Irne
• Nombre de lectures: 14
• Langue: English

Extrait

4`emeCours

Cours MPRI 2010–2011

4e`meCours Cours MPRI 2010–2011

Michel Habib [e-mail] http://www.liafa.jussieu.fr/ ~ habib

Chevaleret, october 2010

4`emeCoursCoursMPRI2010–2011

Schedule

Some NP-hard problems

Partition refinement

Interval graph recognition

Back to graph searching

4e`meCoursCoursMPRI2010–2011 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 vertexx∈V ResultDoes there exist a LexBFS of: Gending inx?

Easy reduction from 3-SAT.

4`emeCoursCoursMPRI2010–2011 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 certificate : i.e. a cycle of length ≥4, without a chord. O(n)

4e`meCoursCoursMPRI2010–2011 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`emeCoursCoursMPRI2010–2011 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`meCoursCoursMPRI2010–2011 Some NP-hard problems

Proof of the lemma

D´ nstratio emo n. We know thatSis a clique. Let us considerG 1 a connected component ofG−S. Letx 1 , . . . ,x k be the vertices ofG 1 having a maximal neighbourhood inS. Ifk= 1 thenx 1 must be universal toS, sinceSis a minimal separator. Else, consider a shortest pathµinG 1 fromx 1 tox k . Necessarilyx 1 (resp.x k ) has a private neighbourz(resp.t) inS. Then the cycle [x 1 , µ,x k ,t,z] has no chord, a contradiction. Thereforex 1 ∪Sis a clique, and is contained in some maximal cliqueCinG 1 . We finish the proof by taking another connected component ofG−S.

4e`meCoursCoursMPRI2010–2011 Some NP-hard problems

Proof of the theorem

De´monstration. ThereforeS=C 0 ∩C 00 . These two maximal cliques belong to any maximal clique treeTofG. Let us consider the unique pathµin TjoigningC 0 toC 00 . 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 inGfromC 0 −Sto C 00 −SavoidingS, a contradiction. So at least one edge ofµis labelled withS.

4`emeCoursCoursMPRI2010–2011 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) =Min H triangulation of G {ω(H)−1} 2.MinFillin(G) =Min H=(V,F) Gtriangulation of {|F|} 3.Pathwidth(G) =Min  GH intervalcompletion of {ω(H)−1} 4.lpteoinervalcomMinInt(G) = Min H=(V,F)intervalcompletion of G {|F|} 5.Theorem Arnborg, Corneil, Proskurowski, 1987 : These 4 problems are NP-hard.

`4eme oS Co em rus PN C h- o a u r r d sM pro P b R le I2 sm 10–00211

Chordal sandwich problem is NP-complete

Data:G 1 = (V,E 1 )G 2 = (V,E 2 ) two graphs, withE 1 ⊆E 2 Result: Does there exist a chordal graphG= (V,E) withE 1 ⊆ E⊆E 2 ? 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 : E 1 is the set offorcededges (good data) E 2 −E 1 is the set ofpossibleedges (some kind of uncertainity or fuzziness) X 2 −E 2 is the set offorbiddenedges.

4`emeCoursCoursMPRI2010–2011 Some NP-hard problems

Perfect Phylogeny and chordal graphs

The data is an incidence matrix from a set of speciesS 1 , . . . ,S n to a set of attributesF 1 , . . . ,F m . Attributes can have different values (integers or colors). These species are modern species and we aim at reconstructing a plausible historical evolution treeT, finding ancestral species. InTvertices are species, and its leaves correspond toS 1 , . . . ,S n and every value of an attribute must define a connected subtree.