Selecting k sub-posets

Question

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:

1. $G \subseteq \bigcup_{i=1}^{l} \sigma(s_i)$ ($S$ covers $G$).
2. $\forall s_i, s_j \in S, i \neq j: \sigma(s_i) \nsubseteq \sigma(s_j)$ (no redundant vertices in $S$).
3. $\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.

Answer 1

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.