1
$\begingroup$

I'm running into an interesting directed acyclic graph (DAG) problem and was wondering if this is a known problem and if it has an efficient algorithm for it. I will use 'graph' and 'DAG' interchangeably

Problem statement:

Find all subgraphs of a DAG that can be defined by two nodes 'Input' and 'Output'. All vertices must be reachable from 'Input' and all these vertices must be able to reach 'Output' in order to be a valid subgraph. Only 'Input' may have incoming edges from outside the subgraph and only 'Output' may have edges to vertices not in the subgraph. The 'Input' and 'Output' vertices may be the same vertex. Let's call this kind of subgraph a 'contractible subgraph'

I'm only interested in the contractible subgraphs which are not included in another contractible subgraph. As an example we can see in the following graph the following contractible subgraphs which satisfy the property.

The contractible subgraphs: {9, 10}, {11}, {12}, {13}, {0, 1, 2, 3, 4, 5, 6, 7, 8}.

The 'Input' and 'Output' vertices respectively:{9, 10}, {11, 11}, {12, 12}, {13, 13}, {8, 0}

enter image description here

Solution approach:

One can conceptually think of the subgraph being able to be collapsed into a single new vertex where its outgoing edges are the ones of the 'Output' vertex and its incoming edges are the ones of the 'Input' vertex.

I was thinking of some divide and conquer algorithm where you can merge two vertices if the 'Input' vertex has one outgoing edge and the 'Output' node has a single incoming edge coming from the 'Input' vertex. This rule alone is however not enough.

A naïve solution: Two vertices form a contractible subgraph iff:

(descendants(Output) - descendants(Input)) U {Input} == (ancestors(Input) - ancestors(Output)) U {Output}

Any ideas, some more observations? Is this a known problem?

Edit:

  • Specified that the 'Input' and 'Output' vertices may be the same vertex
  • Specified that the graph is a DAG
  • Removed incorrect Big-O notation for naïve solution
$\endgroup$
  • $\begingroup$ The definition is somewhat ambiguous with respect to subgraphs that consist of one vertex. As I understand, every subgraph that consists of one vertex is such a graph. Can you edit the post to clarify that input and output can be the same node? Include an example of such subgraph with more than 2 vertices whose input and output are the same node. I also recommend, for the sake of easier references in the question and coming comments and answers, that we give it a name, such as "contractible subgraph". $\endgroup$ – Apass.Jack Mar 28 at 18:14
  • $\begingroup$ "check each combination of two nodes, resulting in $O(V^2)$". No, it results in about $O(V^4)$ or $O(V^3)$. $\endgroup$ – Apass.Jack Mar 28 at 18:17
  • $\begingroup$ Isn't $\{2, 1\}$ a "contractible subgraph"? $\endgroup$ – Apass.Jack Mar 28 at 18:23
  • $\begingroup$ @Apass.Jack Yes {2, 1} is a contractible subgraph, but I'm only interested in the contractible subgraphs which are not subgraph of another contractible subgraph. Also note that each vertex is itself a contractible subgraph. $\endgroup$ – Mattias De Charleroy Mar 29 at 8:11
  • $\begingroup$ @Apass.Jack Hi Jack, I forgot to mention that the input graph is a DAG, so the input and output node can only be the same if the size of the contractible subgraph is 1. $\endgroup$ – Mattias De Charleroy Mar 29 at 8:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.