algorithm to check whether a given graph is subgraph of another graph

Question

i assume that we have 2 labeled graphs G and T and the algorithm determine if G a subgraph of T and the corresponding vertices in the main graphT and the subgraph G should have same label

Just a note on the side, the [Subgraph isomorphism problem](http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem) is NP-complete. — miku, Mar 11 '11 at 23:42

score 2 · Answer 1 · answered Mar 11 '11 at 23:42

2

That problem is called "subgraph isomorphism" and it is NP-complete (and so likely to be hard). Do you need a general solution for this, or just for a particular graph G? The second case is much easier. There is some general information about algorithms here. There is a version of one of the algorithms (actually, for a more general problem) in the Boost Graph Library (see documentation here).

answered Mar 11 '11 at 23:42

Jeremiah Willcock

30,161
7
76
78

+1 for being first and citing a 1993 thread on the matter :) – phooji Mar 11 '11 at 23:45
@phooji: A lot of the results haven't changed, most likely; I know Nauty is still used, at least, though I've heard of it from the full graph isomorphism problem. The algorithm I mention from my edit is from 1982. – Jeremiah Willcock Mar 11 '11 at 23:47
@Jeremiah Willcock: 1993... 1982... what's next? 1971? ;) – phooji Mar 11 '11 at 23:51
i need a general algorithm for graph isomorphism problem – fayza Mar 12 '11 at 00:02
@fayza: Graph isomorphism or subgraph isomorphism? – Jeremiah Willcock Mar 12 '11 at 00:11

score 1 · Answer 2 · answered Mar 11 '11 at 23:43

1

A general answer for a general question: the problem you want to solve is known as 'subgraph isomorphism.' Have a look here for further references: http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem .

answered Mar 11 '11 at 23:43

phooji

10,086
2
38
45

algorithm to check whether a given graph is subgraph of another graph

2 Answers2

Linked