# Maximize function over a set with a transitive and antisymmetric relation

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?

• 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. – 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.