# Efficient algorithm to find subgraph

I have a really nasty problem (for me) at hand and I was wishing some of you may know an efficient algorithm to solve it. Thanks to all of you in advance.

## My problem

I have a set of elements (that I would describe as a graph) that may be of three categories:

• Provider nodes
• Consumer nodes
• Interconnections between nodes

Each node can have one or more interconnections tied to it.

My goal is to correlate each consumer to a set of providers to whom is connected, both directly through an interconnection or indirectly through multiple hops from one consumer to the other. Indirect interconnections can't go through a provider, only a consumer.

Our current approach is to analyze this graph starting with providers, hopping through interconnections recursively until a all unvisited consumers are hit. We then take this "island" of consumers bordered by a set of producers and assign these producers to each consumer we visited.

The approach gave us the right results but at a very high cost, in terms of time spent analyzing the graph.

Do you have any suggestion for an algorithm that can come in handy to solve this problem? I would also consider alternative data structures to hold our input (right now they are a set of tuples in a relational database describing the correlation between nodes and interconnections).

• there is quite a bit of info but it still seems not fully specified. is this a directed graph? if not then you seem to be interested in shortest paths, some kind of optimization problem? – vzn Jul 9 '14 at 15:06
• @vzn the "graph" is not directed in the sense that it just consists of information of correlation between nodes, without specifying a direction. – stefanobaghino Jul 9 '14 at 15:16
• This seems interesting, but with a quick read, I don't think I follow completely. So each vertex in the undirected graph is either a provider or a consumer? Can there be extreme cases where say each vertex is a provider, or each vertex is consumer? Do you know anything about the structure of the graphs that might be helpful? Is it maybe a tree, or anything else? – Juho Jul 9 '14 at 15:55
• @Juho Extreme cases are not contemplated, since they would be unrealistic. All verteces are either providers or consumers. Regarding the structure, it's an undirected graph. – stefanobaghino Jul 9 '14 at 16:03
• @stefanobaghino Sorry if I'm being dense. But in other words, you don't need to find an actual path, but only to decide one exists with the property I defined above? I'm not sure what you mean with "to determine the connectivity between consumers and producers ..." – Juho Jul 9 '14 at 16:10

OK, it sounds like your problem is the following:

You have an undirected graph. Each vertex is either a consumer or a producer. Say that a consumer $c$ is connected to a producer $p$ if there is a path from $c$ to $p$ where all intermediate nodes are consumer nodes. You want to output a list of pairs $(c,p)$ where $c$ is connected to $p$.

This problem can be solved in a straightforward, clean, and efficient manner, using an algorithm for connected components. Here is the algorithm:

1. Remove all of the producer nodes, keeping only the consumer nodes and the edges from a consumer node to a consumer node.

2. Compute connected components on this smaller graph. Let the connected components be $C_1,\dots,C_k$.

3. Now, back in the original graph, shrink all of the consumer nodes in the same connected component into a single node. Thus, we get an edge from connected component $C_i$ to producer $p$ if there is any consumer $c$ in $C_i$ that has an edge to $p$.

4. This resulting graph now describes the connectivity relationship. In particular, for each consumer $c$ and each producer $p$, $c$ is connected to $p$ if and only $C_i$ has an edge to $p$, where $C_i$ is the connected component containing $c$.

For instance, to output the list of all pairs $(c,p)$ that are connected, you can do the following:

• For each connected component $C_i$, for each provider $p$ that has an edge from $C_i$ to $p$, for each consumer $c$ in $C_i$, output the pair $(c,p)$.

This algorithm runs in linear time. The running time to compute the connectivity graph (produced in steps 1-3) is $O(m+n)$, where $n$ is the number of nodes and $m$ is the number of edges (interconnections) in the original graph. The running time in step 4 could be as large as $\Theta(n^2)$, since there might be as many as $\Theta(n^2)$ such pairs. However, here's what we can say. If the correct output has length $\ell$ (i.e., there are $\ell$ pairs $(p,c)$ that are connected), then step 4 will have running time $O(\ell)$.

Therefore, the total running time is $O(m+n+\ell)$, i.e., linear in the sum of the size of the input and the size of the output. This is as fast as you could possibly hope for.

If you don't need to output the set of all pairs $(c,p)$ explicitly, but you just want a compact representation of this connectivity information, you can use the graph computed in steps 1-3 as that compact representation. Then the running time is $O(m+n)$.

• +1 Right, the problem is just connectivity. I didn't know what I was thinking when I wrote down my answer. – Apiwat Chantawibul Jul 9 '14 at 22:56
• Thank you very much! I've already shared your answer with my coworkers, this can be what we were looking for! – stefanobaghino Jul 10 '14 at 7:36

I can't tell if my answer will be applicable because the question is not precisely defined. But let me make some guesses here:

Input graphs with 2 types of vertex.

1. Provider node (P)
2. Consumer node (C)

The edges are constrained by:

1. (P) can connect to (C)
2. (C) can connect to (C)
3. (P) can not connect to (P) (or we just don't care if they're connected)

We say that a producer $p \in P$ can reach $c_* \in C$ denoted with $p \rightarrow c_*$ if:

there is a path starting from $p$ then going through customers only $c_1,c_2,\ldots,c_* \in C$ ending at $c_*$.

You might be interested in the questions:

1. Given a $p \in P$, find $C_p = \{c \mid c \in C \text{ and } p \rightarrow c\}$. (The set of consumers reachable from $p$)
2. Given a $c \in C$, find $P_c = \{p \mid p \in P \text{ and } p \rightarrow c\}$. (The set of providers that can provide for $c$)

EDIT: see D.W.'s answer for calculation.

• You got it! Thank you so much for formally defining my problem!!! – stefanobaghino Jul 9 '14 at 16:15
• You did a wonderful job at formally defining the problem, thank you very much for you effort! – stefanobaghino Jul 10 '14 at 7:39

(am going to take a stab at this with the partial information at this point & possibly modify it on further clarification by questioner.) the Djikstra shortest path algorithm (which basically adds the shortest weighted new edges in the "frontier set") can be run in parallel across multiple starting nodes (but havent seen a ref to this). it sounds like that would give you close to what you want. the starting nodes in your case are the providers. as the edge/vertex set expands, this will eventually "touch" all consumers, and the shortest path to any provider from any consumer can be calculated.

• First off, thanks for your answer. Your help is really appreciated. But I'm not interested in shortest paths, my concern is to find all sets of consumers that are subtended to all sets of providers, forming a subgraph that is bordered by these providers. – stefanobaghino Jul 9 '14 at 15:20
• then you should try to formulate that condition clearly/ formally/ mathematically in the question as a key criteria. what do you mean by "sets of consumers that are subtended to all sets of providers, forming a subgraph that is bordered by these providers"...? that does not seem to express a logical/mathematical criteria although one could be hidden in it... maybe you are actually just interested in a graph connectivity question? ie not all providers are connected to all consumers etc? my answer sketched out above is based on full connectivity of all providers/consumers... – vzn Jul 9 '14 at 15:27
• I'm not sure I can express myself formally in this regard. What I want to know if for each consumer to which providers is connected, directly or indirectly. In the latter case, it's only possible to indirectly connect two nodes if the path between them is made of consumers only. – stefanobaghino Jul 9 '14 at 15:32
• There is full connectivity between nodes but a node cannot be connected to another node through a provider. – stefanobaghino Jul 9 '14 at 15:34
• the problem does not have an algorithmic solution unless it can be clearly described. am roughly following/ understanding some of your ideas. maybe you could cook up some examples or diagrams. sometimes nearly half the problem is clearly describing it. you apparently have two classes of vertices and the paths must somehow be based on the vertex classes. if you show up in Computer Science Chat can further prompt you thru clearly describing/formulating the problem. plz see also how to formulate computational problem rigorously – vzn Jul 9 '14 at 15:38