Subgraph Isomorphism Problem for Graph Classes

Graph Classes and Subgraph Isomorphism
Toshiki Saitoh
ERATO, Minato Discrete Structure Manipulation System Project, JST
Joint work with
Yota Otachi, Shuji Kijima, and Takeaki Uno
アルゴリズム研究会
2010年11月19日
Subgraph Isomorphism Problem
 Input: Two graphs G=(VG, EG) and H=(VH, EH)
 |VH|≦|VG| and |EH|≦|EG|
 Question: Is H a subgraph isomorphic of G?
 Is there an injective map f from VH to VG
 {f(u), f(v)}∈EG holds for any {u, v}∈EH
Example
Graph G
Yes
Graph H1
No
Graph H2
Subgraph Isomorphism Problem
 Input: Two graphs G=(VG, EG) and H=(VH, EH)
 |VH|≦|VG| and |EH|≦|EG|
 Question: Is H a subgraph isomorphic of G?
 Is there an injective map f from VH to VG
 {f(u), f(v)}∈EG holds for any {u, v}∈EH
Application
•LSI design
•Pattern recognition
•Bioinfomatics
•Computer vision, etc.
Known Result
 NP-complete in general


Contains maximum clique, Hamiltonian path,
Isomorphism problem etc.
Graph classes
o Outerplanar graphs
o Cographs
 Polynomial time algorithms
 k-connected partial k-trees
 Tree
 H is forest ⇒ NP-hard
 2-connected series-parallel graphs
Graph Classes
G, H: Connected
G, H∈Graphclass C
Perfect
HHD-free
Comparability
Chordal
Bipartite
Distance-hereditary
Cograph
NP-hard
Ptolemaic
Permutation
Interval
Bipartite permutation
Proper interval
Trivially perfect
Co-chain
Threshold
NP-hard
Chain
Tree
Proper Interval Graphs (PIGs)
 Have proper interval representations
 Each interval corresponds to a vertex
 Two intervals intersect ⇔
corresponding two vertices
are adjacent
 No interval properly contains another
Proper interval graph and its proper interval representation
Characterization of PIGs
 Every PIG has at most 2 Dyck paths.
 Two PIGs G and H are isomorphic
⇔ the Dyck path of G is equal to the Dyck path of H.
 A maximum clique of a PIG G corresponds to
a highest point of a
Dyck path.
 If a PIG G is connected, G contains Hamilton path.
We thought that
the subgraph isomorphism problem of PIGs is easy.
But,
NP-complete!
Problem
Connected
 Input: Two proper interval graphs
G=(VG, EG) and H=(VH, EH)
= |VGG| and |EH| < |EG|
|V|VHH| |≦|V
 Question: Is H a subgraph isomorphic of G?
NP-complete
Reduction from 3-partition problem
3-Partition
 Input: Set A of 3m elements, a bound B∈Z+, and a size aj∈Z+ for each j∈A
 Each aj satisfies that B/4 < aj < B/2
 Σj∈A aj = mB
 Question: Can A be partitioned into m disjoint sets A(1), ... , A(m),
for 1≦i≦m, Σj∈A(i) aj = B
Proof (G and H are disconnected)
Cliques of size B
G
…
m
…
…
…
…
…
Proof (G and H are disconnected)
Cliques of size B
G
…
m
Cliques
H
…
a1
a2
a3
a3m
Proof (G and H are disconnected)
Cliques of size BM
G
…
…
m
(M=m10)
H
…
…
a 1M
a2M
a3M
a3mM
m>2
Proof (G and H are disconnected)
Cliques of size BM+6m2
G
…
…
…
…
…
…
…
3m2
(M=m10)
H
…
a 1M
a2M
a3M
a3mM
m>2
Proof (G is connected)
Cliques of size BM+6m2
G
…
…
…
…
…
…
…
…
(M=m10)
…
3m2
Cliques of size 6m2
H
…
a 1M
a2M
a3M
a3mM
m>2
Proof (G is connected)
Cliques of size BM+6m2
G
…
…
…
…
…
…
…
…
…
3m2
Cliques of size 6m2
(M=m10)
…
…
…
…
…
…
…
…
…
…
…
…
m>2
Proof (G is connected)
Cliques of size BM+6m2
G
…
…
…
…
…
…
…
…
(M=m10)
…
3m2
Cliques of size 6m2
H
…
a 1M
a2M
a3M
a3mM
m>2
Proof (G and H are connected)
Cliques of size BM+6m2
G
H
Paths of length m
…
a 1M
…
a2M
…
Cliques of size 6m2
…
(M=m10)
…
…
…
…
…
…
…
3m2
…
a3M
a3mM
m>2
Proof (G and H are connected)
…
…
…
…
…
…
…
(M=m10)
H
Paths of length m
…
a 1M
…
a2M
…
a3M
a3mM
m>2
Proof (G and H are connected)
Cliques of size BM+6m2
G
H
Paths of length m
…
a 1M
…
a2M
…
Cliques of size 6m2
…
(M=m10)
…
…
…
…
…
…
…
3m2
…
a3M
a3mM
m>2
Proof (|VG|=|VH|)
Cliques of size BM+6m2
G
H
Paths of length m
…
Cliques of size 6m2
…
(M=m10)
…
…
…
…
…
…
…
3m2
6m3-m2-3m+2
…
…
a 1M
…
a2M
…
a3M
a3mM
Graph Classes
G, H: connected
G, H∈Graphclass C
Perfect
HHD-free
Comparability
Chordal
Bipartite
Distance-hereditary
Cograph
NP-hard
Ptolemaic
Permutation
Interval
Bipartite permutation
Proper interval
Trivially perfect
Co-chain
Threshold
NP-hard
Chain
Tree
Threshold Graphs
N(v): neighbor set of v
N[v]:closed neighbor set of v
 A graph G=(V, E) is a threshold
 There are a real number S and a real vertex weight w(v)
such that (u,v) ∈E ⇔ w(u)+w(v)≧S
Lemma [Hammer, et al. 78]
G=(V, E): graph, (d(v1), d(v2), …, d(vn)): degree sequence of G.
G is a threshold
⇔ N[v1]⊇N[v2]⊇… ⊇N[vi]⊇N(vi+1)⊇… ⊇ N(vn)
v1
v7
v2
v6
v3
v5
Graph G
v4
Degree sequence: 6 6 4 3 3 2 2
v1, v2, v3, v4, v5, v6, v7
N[v1]⊇N[v2]⊇N[v3]⊇N(v4)⊇N(v5)⊇N(v6)⊇N(v7)
Polynomial Time Algorithm
Finds degree sequences of G and H
1.


2.
3.
4.
G : ( d(v1), d(v2), …, d(vn) )
H : ( d(u1), d(u2), …, d(un’) )
for i=1 to n’ do
if d(vi) < d(ui) then return No!
return Yes!
Graph G
Yes
No
Graph H1
Graph H2
G :6643322
H1: 6 5 3 3 2 2 1
G :6643322
H2: 5 5 5 3 3 3
Our Results
G, H: connected
G, H∈Graphclass C
Perfect
HHD-free
Comparability
Chordal
Bipartite
Distance-hereditary
Cograph
NP-hard
Ptolemaic
Permutation
Interval
Bipartite permutation
Proper interval
Trivially perfect
NP-hard
Chain
Tree
Co-chain
Threshold

Download Report