0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – D.W. Mar 3 at 23:41
  • $\begingroup$ @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. $\endgroup$ – kauray Mar 4 at 6:32
  • $\begingroup$ 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. $\endgroup$ – D.W. Mar 5 at 7:15
  • $\begingroup$ @D.W. yea if a node is in the set, its predecessors must be in the set too $\endgroup$ – kauray Mar 5 at 15:14
  • $\begingroup$ 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. $\endgroup$ – D.W. Mar 5 at 17:39
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How does the problem statement say that if a vertex is in set $S$ then its predecessors are also in the set? $\endgroup$ – kauray Mar 7 at 5:03
  • $\begingroup$ @kauray, that's what you wrote in your comment: cstheory.stackexchange.com/questions/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. $\endgroup$ – D.W. Mar 7 at 5:05
  • $\begingroup$ Oh sorry this is what captures the problem statement. I had misinterpreted a part of your statement. Thanks a lot! $\endgroup$ – kauray Mar 7 at 6:00

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.