Easy way to determine whether a given graph is subgraph of some other graph?

Question

I'm looking for an algorithm to check whether a given graph is subgraph of another given graph.

I have few conditions to make this NP complete problem bit more feasible..

• The graphs have approx <20 vertices.
• The graphs are DAG.
• All vertices are non-uniquely labeled, and the corresponding vertices in the main graph and the subgraph should have same label. I don't know if I'm using the correct terminologies (because I haven't taken a graph theory course...). It will be something like:

The line graph A--B is subgraph of A--B--A but A--A is not a subgraph of A--B--A.

Any suggestions are fine. This is not a homework question btw. :D

Rapid

What is this line graph that you mention? Are you saying that the smaller graph is always a simple path? – Precedence

@Jeeyoung: Just fyi, this is called the subgraph isomorphism problem. With labels, I believe it is called the labelled subgraph isomorphism problem. – Hecatomb

Answer 1

If the labels are unique, for a graph of size N, there are O(N^2) edges, assuming there are no self loops or multiple edges between each pair of vertices. Let's use E for the number of edges.

If you hash the set edges in the parent graph, you can go through the subgraph's edges, checking if each one is in the hash table (and in the correct amount, if desired). You're doing this once for each edge, therefore, O(E).

Let's call the graph G (with N vertices) and the possible subgraph G_1 (with M vertices), and you want to find G_1 is in G.

Since the labels are not unique, you can, with Dynamic Programming, build the subproblems as such instead - instead of having O(2^N) subproblems, one for each subgraph, you have O(M 2^N) subproblems - one for each vertex in G_1 (with M vertices) with each of the possible subgraphs.

G_1 is in G = isSubgraph( 0, empty bitmask)

and the states are set up as such:

isSubgraph( index, bitmask ) =
   for all vertex in G
       if G[vertex] is not used (check bitmask)
          and G[vertex]'s label is equal to G_1[index]'s label
          and isSubgraph( index + 1, (add vertex to bitmask) )
               return true
   return false

with the base case being index = M, and you can check for the edges equality, given the bitmask (and an implicit label-mapping). Alternatively, you can also do the checking within the if statement - just check that given current index, the current subgraph G_1[0..index] is equal to G[bitmask] (with the same implicit label mapping) before recursing.

For N = 20, this should be fast enough.

(add your memo, or you can rewrite this using bottoms up DP).

Karajan

I don't think this method will work, because of the third constraint i've put in - vertices are non-uniquely labeled. for example, when you have cycle of nodes {A, A, A, B}, and a line graph A--A--B, how I know how the A's get mapped together? – Rapid

@Larry: isSubgraph needs to check edges as vertices are added to bitmask, before the recursive call. – Osset

Thanks, I actually had it as the base case, but left my mind when I typed it out. – Karajan

Answer 2

OK, I have to ask the obvious question. 1. You have twenty vertices. Walk each graph in depth first, alphabetical order among siblings to get strings. 2. One graph is a subgraph of another iff one string is in another.

So, what else is hiding in the problem specification to make this infeasible?

Aryn

Answer 3

You can view this as an alignment problem. Basically you want to come up with an injective mapping a that maps every vertex in V_1 to a vertex in V_2. An alignment map a can be scored as follows:

s(a) = \sum_{(v,w) \in E_1} \sigma(v, w, a(v), a(w)),

where \sigma(v, w, a(v), a(w)) = 1, if (a(v), a(w)) \in E_2 otherwise it is 0.

I think that this can be formulated in the form of an integer linear program.

Gaullist