<p>Your problem is the following:</p>

<p>Given a dag <span class="math-container">$G$</span>, with labels <span class="math-container">$\ell:V\to L$</span> on the vertices, and a set <span class="math-container">$O \subseteq L$</span>, find the smallest subset <span class="math-container">$S \subseteq V$</span> of vertices such that for each <span class="math-container">$o \in O$</span>, there is a vertex in <span class="math-container">$S$</span> labelled <span class="math-container">$o$</span>.</p>

<p>This problem is NP-hard, by reduction from set cover.</p>

<p>(The reduction: given sets <span class="math-container">$T_1,\dots,T_n$</span> and universe <span class="math-container">$U$</span>, define a dag with one source vertex for each <span class="math-container">$T_i$</span>, one sink vertex per element of <span class="math-container">$U$</span>, labelled with that element, and an edge <span class="math-container">$T_i \to t$</span> for each <span class="math-container">$t \in T_i$</span>; and set <span class="math-container">$O=U$</span>.  Then the smallest subset of vertices that meets the requirements is also the minimum set cover.)</p>

<p>Since it is NP-hard, you'll need to use any of the standard methods for dealing with NP-hardness: heuristics, an approximation algorithm, an exponential-time algorithm, etc.  I suggest reducing this to integer linear programming.  Add a zero-or-one boolean variable <span class="math-container">$x_v$</span> for each vertex <span class="math-container">$v$</span>; for each edge <span class="math-container">$v \to w$</span>, add the inequality <span class="math-container">$x_v \ge x_w$</span>; for each label <span class="math-container">$o \in O$</span> in the output set, add the inequality <span class="math-container">$\sum_{\ell(v)=o} x_v \ge 1$</span>, where the sum ranges over all vertices with label <span class="math-container">$o$</span>; and then minimize the objective function <span class="math-container">$\sum_{v \in V} x_v$</span>.  Then, apply an off-the-shelf ILP solver.  Of course this may be exponential time in the worst case, but I suspect it's about as you're likely to get in practice, within any reasonable amount of programming effort.</p>

<p>The data structure to use is a graph.  The problem remains NP-hard no matter what data structure you use, so choice of an appropriate data structure isn't going to make the problem any easier.</p>

CC BY-SA 4.0
2019-03-07T05:03:09.427Z
How does the problem statement say that if a vertex is in set $S$ then its predecessors are also in the set?
kauray
CC BY-SA 4.0
2019-03-07T05:05:13.600Z
@kauray, that's what you wrote in your comment: https://cstheory.stackexchange.com/questions/42468/data-strcuture-to-represent-dependencies-amongst-modules/42483?noredirect=1#comment98668_42468.  You tell me -- if that's not the problem statement, then edit your question to make it clearer.  I'm finding it very hard to extract what the problem statement is.  If we have to ask multiple rounds of questions to try to understand what you're asking, that makes it harder to give you a useful answer.
D.W.
CC BY-SA 4.0
2019-03-07T06:00:25.787Z
Oh sorry this is what captures the problem statement. I had misinterpreted a part of your statement. Thanks a lot!
kauray
CC BY-SA 4.0
2019-03-06T17:53:58.420Z
2019-03-06T17:53:58.420Z
D.W.
<p>Consider several software modules <span class="math-container">$m_1, m_2, ... m_n$</span>. Each module has some inputs and outputs and the inputs to some of the modules are dependent on the outputs of some other modes. For example, in the figure, module <span class="math-container">$m_3$</span> and <span class="math-container">$m_4$</span> are dependent on the output of module <span class="math-container">$m_1$</span>. If we are given a set if inputs <span class="math-container">$I$</span> and a set of outputs <span class="math-container">$O$</span>, the objective is to find a set of modules which produce this output.</p>

<p><a href="https://i.sstatic.net/aFs4S.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/aFs4S.png" alt="enter image description here"></a>
For example, if the output set <span class="math-container">$O$</span> is <span class="math-container">$\{o_1, o_2\}$</span> then all of the modules would have to be used. However if the output set <span class="math-container">$O$</span> is <span class="math-container">$\{o_2\}$</span> then only <span class="math-container">$\{m_2, m5, m_7\}$</span> needs to be used. </p>

<p>A graph is a natural model for such an objective. Are there any alternative data structures to represent this description?</p>

<p>Consider a modification to the earlier example as shown in the figure below, where all the outputs produced are <span class="math-container">$o_1$</span> and the output set required is also <span class="math-container">$O = \{o_1\}$</span>. In this scenario we have two possible set of modules which satisfy our goal of <span class="math-container">$O$</span> :  <span class="math-container">$\{m_2, m_5, m_7\}$</span> and <span class="math-container">$\{m_1, m_3, m_4, m_6\}$</span>. We wish to select the set which minimizes the number of modules used, hence the set <span class="math-container">$\{m_2, m_5, m_7\}$</span> would be our desired set <span class="math-container">$O$</span>. Would a graph still be the most natural representation of such a scenario or some other data structure would be better off?</p>

<p><a href="https://i.sstatic.net/1g6Di.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/1g6Di.png" alt="enter image description here"></a></p>

CC BY-SA 4.0
2019-03-03T23:41:44.393Z
I don't understand what is the input to the algorithm.  Are we given the graph of modules?  And you want to find a subset of nodes such that some condition holds?  If so, what is that condition? You haven't defined what outputs a set of modules produces.  For instance, what is the output produced by the set $\{m_1,m_7\}$?  Do you require the set to have some property (e.g., if a node is in the set, all its predecessors are as well)?
D.W.
CC BY-SA 4.0
2019-03-04T06:32:10.223Z
@D.W. The input to the algorithm is the set of modules, where each module has some input and output. In addition, the inputs are sets $I$ and $O$. The outputs of a module say $m_1$ serves as input to modules $m_3$ and $m_4$, this represents the fact that $m_1$ must be executed before and to drive $m_3$ and $m_4$. We are not given this graph but I represent this scenario using a graph. Thus we are required to find a subset of the nodes that take $I$ as input and produce $O$ as output. $I$ are inputs to the modules which are not dependent on the output of any other module.
kauray
CC BY-SA 4.0
2019-03-05T07:15:47.470Z
Why isn't this just a matter of programming?  For each module you're given its inputs, so look at which modules have inputs from $I$.  Do you really mean an arbitrary subset of nodes, or do you require that it be closed in some way (e.g., if a node is in the set, then all its predecessors must be in the set too)?  The problem doesn't seem well-formulated yet; and before it can be solved, first you must figure out how to formulate it clearly.
D.W.
CC BY-SA 4.0
2019-03-05T15:14:00.323Z
@D.W. yea if a node is in the set, its predecessors must be in the set too
kauray
CC BY-SA 4.0
2019-03-05T17:39:33.243Z
Is the problem as follows?  Given a directed acyclic graph $G$, and some source vertices $I$ and sink vertices $O$, find a subset $S \subseteq V$ of vertices such that $I \cup O \subseteq S$ and if $v \in S$ then all predecessors of $v$ are in $S$ as well?  Is that the problem statement?  Do you want any set $S$, or the smallest such $S$?  Do you want to know the theoretical complexity of this problem, or are you looking for a practical algorithm?  It's important that the problem statement be stated clearly in the question.  I'm not finding any of that clearly stated in the post.
D.W.
CC BY-SA 4.0
2019-03-06T15:26:39.273Z
@D.W. Given a DAG $G$, find a subset $S \subseteq V$ such that if $v \in S$ then all predecessors of $v$ are in $S$ as well such that $S$ is minimum. $O$ which is a $\subset V$ must be present in $S$, that is, $O \in S$. There maybe multiple nodes having the same label for $O$. Like in the example above, $m_6$ and $m_7$ are labeled with both $o_1$. In this example, if $O  = \{o_1\}$ only one would suffice in the output set $S$, I do not know how to state this part formally. All the vertices of $I$ may or may not be present in the set $S$ though.
kauray
CC BY-SA 4.0
2019-03-06T15:35:20.390Z
@D.W. By All the vertices of $I$ may or may not be present in the set $S$ though, I mean, looking at the last example above, the set $S$ would be $m_2, m_5, m_7$ since this set is minimum for the $O = \{o_1\}$. Again, I do not understand how to specify this formally. Do these two comments provide a much more clearer formal description of the questions you asked based on your formulation? I am looking for hints for a practical algorithm and whether there maybe a better data structure suited for this problem?
kauray
<graph-algorithms><ds.data-structures>
Data Strcuture to represent dependencies amongst modules
kauray
# Data Strcuture to represent dependencies amongst modules

(Asked by: username_0 on 2019-03-03)

Consider several software modules $m\_1, m\_2, ... m\_n$. Each module has some inputs and outputs and the inputs to some of the modules are dependent on the outputs of some other modes. For example, in the figure, module $m\_3$ and $m\_4$ are dependent on the output of module $m\_1$. If we are given a set if inputs $I$ and a set of outputs $O$, the objective is to find a set of modules which produce this output.

[![enter image description here](https://i.sstatic.net/aFs4S.png)](https://i.sstatic.net/aFs4S.png)
For example, if the output set $O$ is $\{o\_1, o\_2\}$ then all of the modules would have to be used. However if the output set $O$ is $\{o\_2\}$ then only $\{m\_2, m5, m\_7\}$ needs to be used.

A graph is a natural model for such an objective. Are there any alternative data structures to represent this description?

Consider a modification to the earlier example as shown in the figure below, where all the outputs produced are $o\_1$ and the output set required is also $O = \{o\_1\}$. In this scenario we have two possible set of modules which satisfy our goal of $O$ : $\{m\_2, m\_5, m\_7\}$ and $\{m\_1, m\_3, m\_4, m\_6\}$. We wish to select the set which minimizes the number of modules used, hence the set $\{m\_2, m\_5, m\_7\}$ would be our desired set $O$. Would a graph still be the most natural representation of such a scenario or some other data structure would be better off?

[![enter image description here](https://i.sstatic.net/1g6Di.png)](https://i.sstatic.net/1g6Di.png)

**Tags:** graph-algorithms, ds.data-structures
> **Comments:**
> **username_1**: I don't understand what is the input to the algorithm.  Are we given the graph of modules?  And you want to find a subset of nodes such that some condition holds?  If so, what is that condition? You haven't defined what outputs a set of modules produces.  For instance, what is the output produced by the set $\{m_1,m_7\}$?  Do you require the set to have some property (e.g., if a node is in the set, all its predecessors are as well)?  
> **username_0**: @D.W. The input to the algorithm is the set of modules, where each module has some input and output. In addition, the inputs are sets $I$ and $O$. The outputs of a module say $m_1$ serves as input to modules $m_3$ and $m_4$, this represents the fact that $m_1$ must be executed before and to drive $m_3$ and $m_4$. We are not given this graph but I represent this scenario using a graph. Thus we are required to find a subset of the nodes that take $I$ as input and produce $O$ as output. $I$ are inputs to the modules which are not dependent on the output of any other module.  
> **username_1**: Why isn't this just a matter of programming?  For each module you're given its inputs, so look at which modules have inputs from $I$.  Do you really mean an arbitrary subset of nodes, or do you require that it be closed in some way (e.g., if a node is in the set, then all its predecessors must be in the set too)?  The problem doesn't seem well-formulated yet; and before it can be solved, first you must figure out how to formulate it clearly.  
> **username_0**: @D.W. yea if a node is in the set, its predecessors must be in the set too  
> **username_1**: Is the problem as follows?  Given a directed acyclic graph $G$, and some source vertices $I$ and sink vertices $O$, find a subset $S \subseteq V$ of vertices such that $I \cup O \subseteq S$ and if $v \in S$ then all predecessors of $v$ are in $S$ as well?  Is that the problem statement?  Do you want any set $S$, or the smallest such $S$?  Do you want to know the theoretical complexity of this problem, or are you looking for a practical algorithm?  It's important that the problem statement be stated clearly in the question.  I'm not finding any of that clearly stated in the post.  
> **username_0**: @D.W. Given a DAG $G$, find a subset $S \subseteq V$ such that if $v \in S$ then all predecessors of $v$ are in $S$ as well such that $S$ is minimum. $O$ which is a $\subset V$ must be present in $S$, that is, $O \in S$. There maybe multiple nodes having the same label for $O$. Like in the example above, $m_6$ and $m_7$ are labeled with both $o_1$. In this example, if $O  = \{o_1\}$ only one would suffice in the output set $S$, I do not know how to state this part formally. All the vertices of $I$ may or may not be present in the set $S$ though.  
> **username_0**: @D.W. By All the vertices of $I$ may or may not be present in the set $S$ though, I mean, looking at the last example above, the set $S$ would be $m_2, m_5, m_7$ since this set is minimum for the $O = \{o_1\}$. Again, I do not understand how to specify this formally. Do these two comments provide a much more clearer formal description of the questions you asked based on your formulation? I am looking for hints for a practical algorithm and whether there maybe a better data structure suited for this problem?  

---

## 1 answers

### Answer by username_1 on 2019-03-06. Score: 2 | Accepted answer

Your problem is the following:

Given a dag $G$, with labels $\ell:V\to L$ on the vertices, and a set $O \subseteq L$, find the smallest subset $S \subseteq V$ of vertices such that for each $o \in O$, there is a vertex in $S$ labelled $o$.

This problem is NP-hard, by reduction from set cover.

(The reduction: given sets $T\_1,\dots,T\_n$ and universe $U$, define a dag with one source vertex for each $T\_i$, one sink vertex per element of $U$, labelled with that element, and an edge $T\_i \to t$ for each $t \in T\_i$; and set $O=U$. Then the smallest subset of vertices that meets the requirements is also the minimum set cover.)

Since it is NP-hard, you'll need to use any of the standard methods for dealing with NP-hardness: heuristics, an approximation algorithm, an exponential-time algorithm, etc. I suggest reducing this to integer linear programming. Add a zero-or-one boolean variable $x\_v$ for each vertex $v$; for each edge $v \to w$, add the inequality $x\_v \ge x\_w$; for each label $o \in O$ in the output set, add the inequality $\sum\_{\ell(v)=o} x\_v \ge 1$, where the sum ranges over all vertices with label $o$; and then minimize the objective function $\sum\_{v \in V} x\_v$. Then, apply an off-the-shelf ILP solver. Of course this may be exponential time in the worst case, but I suspect it's about as you're likely to get in practice, within any reasonable amount of programming effort.

The data structure to use is a graph. The problem remains NP-hard no matter what data structure you use, so choice of an appropriate data structure isn't going to make the problem any easier.

> **Comments:**
> **username_0**: How does the problem statement say that if a vertex is in set $S$ then its predecessors are also in the set?  
> **username_1**: @kauray, that's what you wrote in your comment: https://cstheory.stackexchange.com/questions/42468/data-strcuture-to-represent-dependencies-amongst-modules/42483?noredirect=1#comment98668_42468.  You tell me -- if that's not the problem statement, then edit your question to make it clearer.  I'm finding it very hard to extract what the problem statement is.  If we have to ask multiple rounds of questions to try to understand what you're asking, that makes it harder to give you a useful answer.  
> **username_0**: Oh sorry this is what captures the problem statement. I had misinterpreted a part of your statement. Thanks a lot!  

---

