4
$\begingroup$

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.

Thank you in advance :)

$\endgroup$
  • $\begingroup$ This sounds very similar to minimum feedback arc set. $\endgroup$ – Yuval Filmus Oct 25 '16 at 18:45
  • $\begingroup$ 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.) $\endgroup$ – D.W. Oct 26 '16 at 9:22
  • $\begingroup$ @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? $\endgroup$ – Salim Oct 26 '16 at 12:36
  • $\begingroup$ Perhaps there is no connection. $\endgroup$ – Yuval Filmus Oct 26 '16 at 12:52
2
$\begingroup$

If you flip the signs on your costs and reverse edge directions, this is the Closure Problem, also known as the Open-Pit Mining Problem, and it's actually solvable in polynomial time using a rather non-obvious transformation into maximum flow.

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!

$\endgroup$
0
$\begingroup$

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

If the graph is not connected, you can do the same separately for each connected component.

$\endgroup$
  • 1
    $\begingroup$ 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$). $\endgroup$ – Salim Oct 26 '16 at 14:13

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.