4
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 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. ♦
    Commented Apr 22, 2016 at 1:42

1 Answer 1

Reset to default
2
$\begingroup$

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 the following technical report by Cong:

Computing Maximum Weighted K-Families and K-Cofamilies in Partially Ordered Sets. J. Cong. UCLA CS Dept Technical Report CSD-930014, May 1993.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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