Let $G=(V,E)$ be a vertex weighted DAG (Directed Acyclic Graph), with positive real valued weights.Let also $k\leq \left\vert V\right\vert$, is there any way to find a maximum weighted antichain over $G$ (a set of vertexes $A\subseteq V$ where there is no edges between elements of $A$) , with cardinality less or equal than $k$?The unconstrained problem (i.e. where the size of the anti-chain is not bounded) can be solved by reducing it to a minumum flow problem (as can be seen in this Technical Report by Cong).Is this problem NP-hard?
Maximum weighted antichain over a DAG with cardinality constraint
graphs;weighted graphs;dag