4ème Cours Cours MPRI 2010–2011

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 ...