Graph Decompositions and Optimization Problems

Vassilis Giakoumakis
Professor
Department of Computer Science
University of Amiens, Amiens, France

Abstract. 

Let G = (V; E) be a graph and let P be a problem on G that we wish to
solve.

Assume that we know a "good" solution of P for a special family of graphs H. Assume,
further, that we can decompose G into subgraphs H1 , ..., Hn which are of type H.
This approach implies that we are able to:

1. Find a decomposition of G into H1 , ..., Hn.
Many graph partitioning problems (partition into forests, cliques, isomorphic sub
graphs etc) are NP-complete problems.

2. Solve the restriction of problem P to each subgraph Hi.

3. Use the partial solutions on each Hi to solve the original instance of P.

In this talk we first present a classical graph decomposition, the modular decompo-
sition, a module M of a graph G being a set of vertices of G such that every vertex
outside M is either adjacent to all vertices in M or to none of them. Next, we present a
well-known family of graphs, the cographs which are totally decomposable by the mod-
ular decomposition and we show how the decomposition of cographs leads to optimal
solutions for a number of optimization problems.

In a number of papers B. Jamison and S. Olariu showed that many results obtained
for cographs can be extended to larger classes of graphs.
Using modular decomposition, we then propose a method that generalizes and unifies
many of the previous results. More precisely, we show that for about ten families of
graphs, our method leads to optimal recognition and optimization algorithms.

Finally, we discuss a decomposition for bipartite graphs and we conclude this talk by
new perspectives and open problems.

Biographical sketch

Vassilis Giakoumakis
Professor
Department of Computer Science
University of Amiens, Amiens, France

Education Background:
Ph.D., Applied Mathematics, University Paris V-Sorbonne (1985)

Research Interests Graph Theory, Algorithms, Combinatorial
Optimization, Discrete Mathematics, Automata Theory, Compilation,
Wireless Networks.

Major Appointments
Associate Professor, Dept. of Computer Science, 
  University of Amiens (1989-1997)
Professor, Dept. of Computer Science, 
  University of Amiens, (1997- present)

Further Affiliations
LaRIA: Laboratoire d'Informatique d'Amiens
LIAFA: Laboratoire d'Informatique, Algorithmique: Fondaments et
  Applications, University of Paris VII-Jussieu

CAMS-Paris: Centre d'Analyse et des Mathematiques Sociales, Perfect
  Graphs research group lead by Claude Berge