cours3-2012

8/12/2019 cours3-2012

1/35

3eme Cours : Chordal Graphs MPRI 20122013

3eme Cours : Chordal GraphsMPRI 20122013

Michel [email protected]

http://www.liafa.univ-Paris-Diderot.fr/~habib

Chevaleret, octobre 2012
http://www.liafa.univ-paris-diderot.fr/~habibhttp://www.liafa.univ-paris-diderot.fr/~habibhttp://www.liafa.univ-paris-diderot.fr/~habibhttp://www.liafa.univ-paris-diderot.fr/~habib

8/12/2019 cours3-2012

2/35


Schedule

Partition refinement II

Chordal graphs

Representation of chordal graphs

8/12/2019 cours3-2012

3/35



Tree isomorphism using Partition refinement

Compute the generalized degree partitions of the two graphs Gand H

Folklore Property

iF G and Hare isomorphic then their partitions are identical.

Particular case of trees

For trees the converse is also true.

8/12/2019 cours3-2012

4/35



To compute this partition we can use a variation of the partition

refinement.DegreeRefine(P, S) :compute the partition of S in parts having same degree with P

8/12/2019 cours3-2012

5/35



This technique is very powerfull not only for graph algorithms.

First used by Corneil for Isomorphism Algorithms 1970Hopcroft Automaton 1971Crochemore string sorting 1981. . .

8/12/2019 cours3-2012

6/35



Applications

QUICKSORT : Hoare, 1962.

Minimal deterministic automaton : Hopcroft O(nlogn) 1971. Relational coarset partition : Paige, Tarjan 1987

Doubly Lexicographic ordering : Paige Tarjan 1987 O(LlogL).using a 2-dimensional refinement technique.

Interval graph recognition, modular decomposition, manyproblems on graphs (LexBFS . . .). 1990

8/12/2019 cours3-2012

7/35



Vertex splitting

Also called vertex partitionningWhen the neighborhood N(x) is used as a pivot set.

8/12/2019 cours3-2012

8/35



J.E. Hopcroft, A nlogn algorithm for minimizing states in afinite automaton, Theory of Machine and Computations,(1971) 189-196.

A. Cardon and M. Crochemore, Partitioning a Graph inO(|A|log2|V|), Theor. Comput. Sci., 19 (1982) 85-98.

M. Habib, R. M. McConnell, C. Paul and L. Viennot, Lex-BFSand partition refinement, with applications to transitiveorientation, interval graph recognition and consecutive ones

testing, Theor. Comput. Sci. 234 :59-84, 2000.

R. Paige and R. E. Tarjan, Three Partition RefinementAlgorithms, SIAM J. Computing 16 : 973-989, 1987.

eme

8/12/2019 cours3-2012

9/35


Chordal graphs

Definition

A graph is a chordal graph if every cycle of length 4 has a chord.Also called triangulated graphs, (cordaux in french)

1. First historical application : perfect phylogeny.

2. Many NP-complete problems for general graphs arepolynomial for chordal graphs.

3. Second application : graph theory. Treewidth (resp.

pathwidth) are very important graph parameters that measuredistance from a chordal graph (resp. interval graph).

eme C Ch d l G h MPRI

8/12/2019 cours3-2012

10/35


Chordal graphs

Two Basic facts

1. Chordal graphs are hereditary2. Interval graphs are chordal

3eme C Ch d l G h MPRI 2012 2013

8/12/2019 cours3-2012

11/35


Chordal graphs

Chordal graph

5

1 4 38

6 7 2

A vertex is simplicial if its neighbourhood is a clique.

Simplicial elimination scheme

= [x1. . . xi. . . xn] is a simplicial elimination scheme ifxi is

simplicial in the subgraph Gi=G[{xi. . . xn}]

ca b

3eme Co rs Chordal Graphs MPRI 2012 2013

8/12/2019 cours3-2012

12/35


Chordal graphs

A characterization theorem for chordal graphs

Theorem

Dirac 1961, Fulkerson, Gross 1965, Gavril 1974, Rose, Tarjan,Lueker 1976.For a connected graph G the following items are equivalent :

(0) G is chordal (every cycle of length 4 has a chord).

(i) G has a simplicial elimination scheme

(ii) Every minimal separator is a clique

3eme Cours : Chordal Graphs MPRI 2012 2013

8/12/2019 cours3-2012

13/35

3 Cours : Chordal Graphs MPRI 20122013

Chordal graphs

Minimal Separators

A subset of vertices S is aminimal separator ifGif there exist a, bG such that a and bare not connected inG S.and Sis minimal for inclusion with this property .


8/12/2019 cours3-2012

14/35

3 Cours : Chordal Graphs MPRI 2012 2013

Chordal graphs

An example

3 minimal separators {b} forf and a, {c}fora and eand {b, c}fora and d.


8/12/2019 cours3-2012

15/35

3 Cours : Chordal Graphs MPRI 2012 2013

Chordal graphs

IfG= (V, E) is connected then for every a, bV such thatab /E

then there exists at least one minimal separator.But there could be anexponential number of minimal separators.Consider 2 stars a, x1, . . . , xn (centered in a) and b, y1, . . . , yn(centered in b) and then add all the edges xiyi for 1 in.There exist 2n minimal separators for the vertices a and b.


8/12/2019 cours3-2012

16/35

3 u p 0 0 3

Chordal graphs

Proof of the theorem


8/12/2019 cours3-2012

17/35

p

Chordal graphs

Lexicographic Breadth First Search (LexBFS)

Data: a graph G = (V, E) and a start vertex s

Result: an ordering ofV

Assign the label to all vertices

label(s) {n}for in to 1 do

Pick an unumbered vertex vwith lexicographically largest label(i) vforeach

unnumbered vertex w adjacent to v do

label(w) label(w).{i}end

end


8/12/2019 cours3-2012

18/35

Chordal graphs

1

76

5

4

3

2


8/12/2019 cours3-2012

19/35

Chordal graphs

The reference for a graph algorithm theorem

LexBFS Characterization [Rose, Tarjan et Lueker 1976]

A graph is chordal Giff every LexBFS ordering ofGprovides a

simplicial elimination scheme.

1 8

7

6

5

4

3

2


8/12/2019 cours3-2012

20/35

Chordal graphs

How can we prove such a theorem ?

1. A direct proof, finding the invariants ?

2. Find some structure of chordal graphs

3. Understand how LexBFS explores a chordal graph

4. We will consider the 3 viewpoints.


8/12/2019 cours3-2012

21/35

Chordal graphs

Chordal graphs recognition so far

Chordal graph recognition

1. Apply a LexBFS on G O(n+m)2. Check if the reverse ordering is a simplicial elimination scheme

O(n+m)

3. In case of failure, exhibit a certificate : i.e. a cycle of length

4, without a chord. O(n)


8/12/2019 cours3-2012

22/35


About Representations

Interval graphs are chordal graphs How can we represent chordal graphs ?

As an intersection of some family ?

This family must generalize intervals on a line


8/12/2019 cours3-2012

23/35


Which kind of representation to look for for special classes

of graphs ?

Easy to manipulate (optimal encoding, easy algorithms foroptimisation problems)

Geometric in a wide meaning (ex : permutation graphs =intersection of segments between two lines)

Examples : disks in the plane, circular genomes . . .


R i f h d l h

8/12/2019 cours3-2012

24/35


First remark

Proposition

Every undirected graph can be obtained as the intersection of asubset family

Proof

G= (V, E)Let us denote by Ex={eE|e x=} the set of edges adjacentto x.

xyE iffEx Ey=We could also have taken the set Cxof all maximal cliques whichcontains x.Cx Cy = iff one maximal clique containing both x and y


R t ti f h d l h

8/12/2019 cours3-2012

25/35


Starting from a graph in some application, find its characteristic :

1. 2-intervals on a line (biology), intersection of disks (orhexagons) in the plane (radio frequency), filament graphs,

trapezoid graphs . . .2. A whole book on this subject :

J. Spinrad, Efficient Graph Representations, Fields InstituteMonographs, 2003.

3. A website on graph classes :http ://www.graphclasses.org/



8/12/2019 cours3-2012

26/35


For chordal graphs the solution isSubtrees in a tree

Using results of Dirac 1961, Fulkerson, Gross 1965, Buneman1974, Gavril 1974 and Rose, Tarjan and Lueker 1976 :

For a connected graph, the following statements are equivalent

and characterize chordal graphs :(i) G has a simplicial elimination scheme

(ii) Every minimal separator is a clique

(iii) Gadmits a maximal clique tree.

(iv) G is the intersection graph of subtrees in a tree.

(v) Any MNS (LexBFS, LexDFS, MCS) provides asimplicial elimination scheme.



8/12/2019 cours3-2012

27/35


Helly Property

Definition

A subset family{Ti}iI satisfies Helly property ifJI et i,jJ Ti Tj= impliesiyJTi=

Exercise

Subtrees in a tree satisfy Helly property.



8/12/2019 cours3-2012

28/35


Demonstration.Suppose not. Consider a family of subtrees that pairwise intersect.For each vertex xof the tree T, it exists at least one subtree of thefamily totally contained in one connected component ofT x.

Else xwould belong to the intersection of the family, contradictingthe hypothesis.Direct exactly one edge ofT from x to this part.We obtain a directed graph G, which has exactly n vertices and ndirected edges. Since T is a tree, it contains no cycle, therefore it

must exist a pair of symmetric edges in G, which contradicts thepairwise intersection.



8/12/2019 cours3-2012

29/35


VIN :Maximal Clique trees

A maximal clique tree (clique tree for short) is a tree T that

satisfies the following three conditions : Vertices ofTare associated with the maximal cliques ofG

Edges ofTcorrespond to minimal separators.

For any vertex xG, the cliques containingxyield a subtree

ofT.



8/12/2019 cours3-2012

30/35

ep ese tat o o c o da g ap s

Two subtrees intersect iff they have at least one vertex in common.By no way, these representations can be uniquely defined !



8/12/2019 cours3-2012

31/35

p g p

An example



8/12/2019 cours3-2012

32/35

Back to the theorem

For a connected graph, the following statements are equivalentand characterize chordal graphs :

(i) G has a simplicial elimination scheme(ii) Every minimal separator is a clique

(iii) Gadmits a maximal clique tree.

(iv) G is the intersection graph of subtrees in a tree.

(v) Any MNS (LexBFS, LexDFS, MCS) provides asimplicial elimination scheme.



8/12/2019 cours3-2012

33/35

Proof of the chordal characterization theorem

Clearly (iii) implies (iv)

For the converse, each vertex of the tree corresponds to aclique in G.But the tree has to be pruned of all its unnecessary nodes,

until in each node some subtree starts or ends. Then nodescorrespond to maximal cliques.

We need now to relate these new conditions to chordal graphs.(iii) implies (i) since a maximal clique tree yields a simplicial

elemination scheme.(iv) implies chordal since a cycle without a chord generates acycle in the tree.(iv) implies (ii) since each edge of the tree corresponds to aminimal separator which is a clique



8/12/2019 cours3-2012

34/35

from (i) to (iv)

Demonstration.

By induction on the number of vertices. Let xbe a simplicialvertex ofG.

By induction G xcan be represented with a family of subtreeson a tree T.N(x) is a clique and using Helly property, the subtreescorresponding to N(x) have a vertex in common .To represent Gwe just add a pending vertex adjacent to .xbeing represented by a path restricted to the vertex , and weadd to all the subtrees corresponding to vertices in N(x) the edge.



8/12/2019 cours3-2012

35/35

Playing with the representation

Easy Exercises :

1. Find a minimum Coloring (resp. a clique of maximum size) of

a chordal graph in O(n+m).Consequences :chordal graphs are perfect.At most n maximal cliques.

2. Find a minimum Coloring (resp. a clique of maximum size) of

an interval graph in O(n)using the interval representation.

Documents

cours3-2012