Let $\mathcal{R}$ be a transitive and antisymmetric relation defined over a finite set $X$.

For any set $S\subseteq X$ define $\Gamma(S)=\left\{y\in S \mid \not \exists x\in S . (x,y)\in\mathcal{R}\right\}$. (Thus, $y \in \Gamma(S)$ if it belongs to $S$ and no other element in $S$ "dominates" it.)

Suppose that each element is assigned a weight. This is represented by the function $w:X\to \mathbb{R}^+$.

The problem is to find a subset $S \subseteq X$ to maximize $\sum_{z \in \Gamma(S)}w(z)$.

Is this problem polynomial-time solvable?

  • 2
    $\begingroup$ Equivalent formulation: Given a dag with non-negative weights on the vertices, find a subset $S$ of the vertices whose total sum is as large as possible, subject to the constraint that no vertex in $S$ is reachable from any other. Or: given a partial order on $X$ and a non-negative weight for each element of $X$, find an antichain whose total weight is as large as possible. $\endgroup$ – D.W. Apr 22 '16 at 1:42

You can compute the maximum weight of an antichain, or more generally the maximum weight of a union of $k$ antichains, by reducing to the maximum flow problem. See for example a technical report by Cong.

| cite | improve this answer | |

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.