Data structure and optimal algorithm for modeling reachable outputs given a set of inputs

Question

Given the following:

• A set of input types $I$ = {a, b, d, ...}
• A set of functions $F$ (With associated costs, and possibly identical signatures) = {($c_1$, a -> d), ($c_2$, (a,b) -> e), ($c_3$, e -> (d,f)), ...}
• A set of desired output types $O$ = {f, g, h, ...}

I would like to build a system that can return the lowest cost set of functions in $F$ which need to be called to generate $O$ from $I$, if such a set exists (Let's call this subset $R$ ).

By "generate" I mean that for each $o \in O$ there is a function in the returned subset $R$ that includes $o$ among its outputs; and for each function in $R$, all of its inputs are either in $I$ or are outputs of other earlier functions.

If $F$ consisted of only single-variable functions this would be easy, as I could just use a graph with types as vertices and functions as edges, then find the shortest path from available input type vertices to desired output type vertices. With multi-input/multi-output functions I can still do this, but I have to make multiple re-traversals through the graph if I find that I do not yet have a function in the selected collection that can generate one or more of the inputs required for a particular function.

The best idea I've come up with to deal with the multi-input/multi-output function scenario is to still use a graph (a DAG specifically), but have each vertex represent a full collection of currently available types, with each edge representing a function, and many duplicate edges representing the same function being called using the required inputs from many different overlapping collections in the graph.

I'm looking for confirmation on whether or not this is a good approach, and any recommendations on alternative data structures or algorithms to solve this problem effectively.

Answer 1

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

In particular, suppose we have a instance of the set cover problem, i.e., sets $S_1,\dots,S_m$, and the goal is to identify the smallest collection of sets whose union is $U$. We can create an instance of your problem, with $I=\emptyset$ and $O=U$, with one function $f_i$ for each set $S_i$, such that the output set of $f_i$ is $S_i$ and its input set is $\emptyset$, and every function has the same cost. Then the lowest-cost collection of functions that cover $O$ yields the smallest collection of sets whose union is $U$.

Therefore, you should not expect any efficient algorithm for your problem that always works.

Instead, you might consider using an off-the-shelf ILP solver. For instance, introduce a zero-or-one variable $x_f$ for each function $f \in F$; the intended meaning of $x_f=1$ is that $f$ should be included in the set of functions. Then, add linear inequalities to capture that this set is valid:

• For each function $g \in G$ and each type $t \notin I$ that is an input to $g$, add a linear inequality

  $$\sum x_f \ge x_g,$$

  where the sum ranges over all functions $f$ that contain $t$ as one of their output types.

• For each $o \in O$, add a linear inequality

  $$\sum x_f \ge 1,$$

  where the sum ranges over all functions $f$ that contain $o$ as one of their output types.

Finally, the objective function is

$$\Phi = \sum_{f \in F} c_f x_f,$$

where $c_f$ is the cost of function $f$. This is an instance of integer linear programming (ILP), so you can use an off-the-shelf ILP solver to try to find the best solution to it.