# Time complexity of a precedence constrained selection problem

I wonder if you have an idea over the time complexity of the following problem, or a problem similar to this one (generally a selection problem)

[Assuming operations on integers take O(1) time]

We are given a set $N$ of $n$ items, that are subject to general precedence constraints (a partial order $E$ on $N$). The problem could then be represented by an acyclic directed graph $G(N,E)$ where the nodes represent items and edges represent precedence constraints. Each item has a selection cost $c_i$ that may be positive, zero, or negative. The objective is to find a subset $S \subseteq N$ of items that is precedence feasible, i.e., $\forall i \in S:\{j \in N|(j,i) \in E\}\subset S$, and minimizes the total selection cost $F(S)=\sum_{i \in S}c_i$.

I tried to find a reduction from CLIQUE or 3-Dimensional Matching, but I couldn't.

• This sounds very similar to minimum feedback arc set. Oct 25 '16 at 18:45
• Can you elaborate on the connection? (The graph $G$ here is acyclic, whereas minimum feedback arc set deals with graphs containing cycles, so I'm not seeing the relationship.)
– D.W.
Oct 26 '16 at 9:22
• @YuvalFilmus , the problem you are referring to, is to choose the minimum number of edges which, when removed from a directed cyclic graph, leave a directed acyclic graph. In this context, the chosen edges are neither precedence related nor costly/profitable. Hence, I don't see the connection immediately. Can you explain a bit? Oct 26 '16 at 12:36
• Perhaps there is no connection. Oct 26 '16 at 12:52

The algorithm is described in the Wikipedia page linked above. Briefly, it involves setting the capacity of each edge to infinity, which has the effect that any minimum cut avoids all original graph edges in the forward direction (since any cut that included such an edge would have infinite flow), and adding a new edge to each vertex from one of two new vertices, $s$ (for positive-weight vertices) or $t$ (for negative-weight vertices). The capacity of any $s$-$t$ cut magically works out to be a constant minus the total weight of vertices on one side of the cut, so minimising this (which can be done by a max-flow algorithm) maximises said total weight!
The problem should be easily solvable, even in linear time: Just consider a topological sorting $v_1,\ldots,v_n$ of the nodes of the induced graph and let $C(v_i)$ denote the minimal costs if you choose to select item $v_i$. Clearly, it holds that $C(v_1) = c_1$. For some $i > 1$, if you choose to select item $v_i$, you must select all the preceding items, so you get $c_i$ plus the (already computed) values $C(v_j)$ for each edge $(j,i)$. In the end, you only have to look for a node $v_i$ with the minimum value $C(v_i)$ among all nodes (or choose none if all of them have positive costs).
• I'm afraid it's not that easy! Unfortunately, your proposed method does not work for general precedence graphs (maybe for series parallel, I'm not sure). Let me give you a counter example: Consider the set $N = \{ 1, 2, 3 \}$, their corresponding selection costs $c = \{ +3, -2, -2 \}$, and the set of precedence relations $E = \{ (1,2), (1,3) \}$. The cumulative costs would be: $C(1)=+3$, $C(2)=+1$ and $C(3)=+1$. Now, based on your method, no item should be selected since the cumulative costs are all positive ($F=0$), while the optimal solution is too choose all the items ($F^{*}=-1$). Oct 26 '16 at 14:13