Selecting k sub-posets I ran into the following algorithmic problem while experimenting with classification algorithms. Elements are classified into a polyhierarchy, what I understand to be a poset with a single root ("largest" element), please correct me if I am mistaken. I have to solve the following problem, which looks a lot like the set cover problem.
Let $L$ be a directed, acyclic, unweighted graph of $n \in \mathbb{N}$ vertices $V = \{v_1, v_2, \dots, v_n\}$ with edges $E = \{(v_i, v_j) | v_i, v_j \in V\}$. $L$ has a poset structure. There is one designated "root" vertex and a direction "down" the graph, following the direction of the edges. Basically a tree where all non-root vertices may have multiple parents.
Let $G = \{g_1, g_2, \dots, g_m\} \subseteq V$ be a subset of $V$ containing vertices to be covered. For each vertex $v \in V$, let $\sigma(v)$ be the verticies of the sub-graph rooted at $v$.
For a given $k \in \mathbb{N}$, $k \leq m \leq n$, select $S = \{s_1, s_2, \dots, s_l\} \subseteq V$,  $l \geq k$ such that:


*

*$G \subseteq \bigcup_{i=1}^{l} \sigma(s_i)$ ($S$ covers $G$).

*$\forall s_i, s_j \in S, i \neq j: \sigma(s_i) \nsubseteq \sigma(s_j)$ (no redundant vertices in $S$).

*$\nexists S' \subseteq V$ that satisfies 1 with $k \leq |S'| < l$ (minimal).


Note that 2 is not implied by 3 because of the lower bound $k$. If we have to to drop 3 in order to get an efficient algorithm, we still want to keep 2.
This problem will in general not have a solution for $l=k$, which is why we need the additional variable $l$: Say you choose $k=2$ and $V$ with $|V|=4$ has the form of a root node with 3 children. Let $G$ be these 3 children. This is solvable for $l=3$ but not for $l=k=2$.
Finding an optimal solution (satisfying 3) may be hard. This looks a lot like the set cover problem (which is NP-hard), but really is a special case of it, given the special structure of the subsets.
Devising an approximation algorithm that satisfies 1 & 2 is quite easy, just start at the vertices of $G$ and "walk up" or start at the root and "walk down". Say you start at the root, iteratively expand vertexes and then remove unnecessary vertices until you have at least $k$ sub-graphs. The approximation bound depends on the number of children of a vertex, which is OK for my application.
However I would be very interested in proofing that this problem is NP-hard. So far my tries with set cover and knapsack failed. Does anyone have a hint which NP-hard problem would lend itself to a reduction? Or maybe the problem isn't NP-hard after all, given the special structure of the subsets?
This is my first post on MathOverflow, so I hope I chose the right tags, please feel free to improve my tagging.
 A: You seem to rely on a notion of a vertex preceding another (you use the terms "lattice" and "polyhierarchy", and refer to the direction "down").  So the edge relation $E$ appears to be transitive, forming a strict partial order.
To show why the $k$ parameter is important, you suggest an example where the target set $G$ presumably contains the three children of the root $\mu$.  In this case, $k=1$ would clearly allow $S = \lbrace \mu \rbrace$.  On the other hand, setting $k=2$ would force each of the children to be in $S$, to avoid condition 2.
This gives the key to the reduction of SET COVER to the decision version of your problem.  Given is a set of subsets of a finite universe, and an integer $l$.  The problem is to determine whether one can find at most $l$ subsets which cover the entire universe.  For each subset create a vertex, and let $E$ be the subset relation between subsets, expressed in terms of the vertices.  If the universe itself is one of the subsets, then let $k=1$ (note that in this case the problem is quite trivial, the solution $S$ will simply contain this one element).  Otherwise let $k=2$ and add a new root vertex denoting the universe, with edges to every other vertex.  Finally, let $G$ be the set of all minimal vertices (corresponding to all minimal subsets).
This instance of your problem has a solution (a set of at most $l \ge k$ vertices, covering all minimal vertices) if, and only if, the set cover instance has a solution.
I hope I have managed to capture your problem correctly.
