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

Question

Hello,

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

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).

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?

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.