patternMinor
Maximize function over a set with a transitive and antisymmetric relation
Viewed 0 times
antisymmetricwithfunctiontransitivemaximizeandrelationoverset
Problem
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?
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?
Solution
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.
Computing Maximum Weighted K-Families and K-Cofamilies in Partially Ordered Sets. J. Cong. UCLA CS Dept Technical Report CSD-930014, May 1993.
Context
StackExchange Computer Science Q#56288, answer score: 2
Revisions (0)
No revisions yet.