0% found this document useful (0 votes)

4 views48 pages

Graph Kernel Computation Algorithms

The document discusses the computation of kernels in directed graphs, particularly focusing on chordal clique-acyclic graphs. It defines a kernel as a stable and absorbing subset of vertices and outlines an algorithm for computing kernels in these graphs, leveraging the structural properties of clique trees. The goal is to determine polynomial-time algorithms for kernel computation in specific graph families where kernel existence is guaranteed but computational complexity remains uncertain.

Uploaded by

Chhin Visal

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

4 views48 pages

Graph Kernel Computation Algorithms

Uploaded by

Chhin Visal

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

Computing kernels of graphs

Adèle Pass-Lanneau
Internship supervised by Frédéric Meunier

Ecole polytechnique - CERMICS

July 11, 2016

Computing kernels of graphs

Plan

1 Introduction

2 Algorithm for chordal graphs

3 Generalization
Computing kernels of graphs
Introduction

Plan

1 Introduction

2 Algorithm for chordal graphs

3 Generalization
Computing kernels of graphs
Introduction

Graph theory basics

1 2 Vertices, edges

3 4 5

6
Computing kernels of graphs
Introduction

Graph theory basics

1 2 Vertices, edges
Orientation, arcs
3 4 5

6
Computing kernels of graphs
Introduction

Graph theory basics

1 2 Vertices, edges
Orientation, arcs
3 4 5 Neighbors/Adjacent vertices
Successor
Sink: vertex without successor
6
Circuit
Computing kernels of graphs
Introduction

Kernel

Denition
Let D = (V , A) be a directed graph. A subset of vertices K is a kernel of
D when:

K is stable: it contains no pair of adjacent vertices

K is absorbing: every vertex v ∈ / K has a successor in K ,

i.e.,∀v ∈
/ K , there is a vertex k ∈ K such that (v , k ) ∈ A.
Computing kernels of graphs
Introduction

Kernel

Denition
Let D = (V , A) be a directed graph. A subset of vertices K is a kernel of
D when:

K is stable: it contains no pair of adjacent vertices

K is absorbing: every vertex v ∈ / K has a successor in K ,

i.e.,∀v ∈
/ K , there is a vertex k ∈ K such that (v , k ) ∈ A.

1 {1, 6} is not an absorbing subset of D :

2 vertex 2 has no successor in {1, 6}

3 4 5

6
Computing kernels of graphs
Introduction

Kernel

Denition
Let D = (V , A) be a directed graph. A subset of vertices K is a kernel of
D when:

K is stable: it contains no pair of adjacent vertices

K is absorbing: every vertex v ∈ / K has a successor in K ,

i.e.,∀v ∈
/ K , there is a vertex k ∈ K such that (v , k ) ∈ A.

1 {1, 6} is not an absorbing subset of D :

2 vertex 2 has no successor in {1, 6}
{1, 2, 6} is absorbing but not stable
3 4 5 because of the arc (1, 2)

6
Computing kernels of graphs
Introduction

Kernel

Denition
Let D = (V , A) be a directed graph. A subset of vertices K is a kernel of
D when:

K is stable: it contains no pair of adjacent vertices

K is absorbing: every vertex v ∈ / K has a successor in K ,

i.e.,∀v ∈
/ K , there is a vertex k ∈ K such that (v , k ) ∈ A.

1 {1, 6} is not an absorbing subset of D :

2 vertex 2 has no successor in {1, 6}
{1, 2, 6} is absorbing but not stable
3 4 5 because of the arc (1, 2)
{2, 6} is absorbing and stable: it is a
kernel of D
6
Computing kernels of graphs
Introduction

Kernel

Denition
Let D = (V , A) be a directed graph. A subset of vertices K is a kernel of
D when:

K is stable: it contains no pair of adjacent vertices

K is absorbing: every vertex v ∈ / K has a successor in K ,

i.e.,∀v ∈
/ K , there is a vertex k ∈ K such that (v , k ) ∈ A.

1 {1, 6} is not an absorbing subset of D :

2 vertex 2 has no successor in {1, 6}
{1, 2, 6} is absorbing but not stable
3 4 5 because of the arc (1, 2)
{2, 6} is absorbing and stable: it is a
kernel of D
6
{3, 6} is another kernel of D
Computing kernels of graphs
Introduction

Existence of a kernel

Graphs can have several kernels (even exponentially many)

Others have no kernel at all, for example odd circuits

Existence theorems are proven for some families of graphs

Graphs without circuits, perfect graphs (Boros-Gurvich), graphs without
odd circuit (Richardson), line-graphs (Maray)...
Computing kernels of graphs
Introduction

Why kernels ?

Related to winning strategies in game theory

Initially introduced by Von Neumann and Morgenstern in their Theory of
Games and Economic Behavior in 1944

Consider a graph without circuit,

with a token placed on a starting
vertex s .
Two-player game: at his turn,
each player moves the token from
the current vertex to a successor
of his.
The player who can't move
anymore is the loser.
Computing kernels of graphs
Introduction

Why kernels ?

A game corresponds to a path

v0 = s → v1 → ... → vn with vn a sink.
Player 1 chooses v2p+1 ∀p .

Let K be a kernel of the digraph. Then:

All sinks are in K .
∀v2p ∈/ K , Player 1 has a strategy to
impose v2p+1 ∈ K .
If s ∈
/ K , Player 1 knows how to win !
Computing kernels of graphs
Introduction

Example of a Nim game

A Nim game:
stack of 10 sticks
two players playing in turns
each of them removes 1, 2 or 3 sticks
the loser is the player who removes the last stick
Computing kernels of graphs
Introduction

Example of a Nim game

A Nim game:
stack of 10 sticks
two players playing in turns
each of them removes 1, 2 or 3 sticks
the loser is the player who removes the last stick
Equivalent to moving a token in the appropriate state graph.