2 Forgot to edit title.

# Selecting k sub-latticessub-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 latticeposet 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 lattice poset structure, meaning there . 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-lattice 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 $|S'| k \leq |S'| < l$ (minimal).

Note that 2 is redundant as it is not implied by 3 . However, if 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; this . 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-latticessub-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.

1

# Selecting k sub-lattices

I ran into the following algorithmic problem while experimenting with classification algorithms. Elements are classified into a polyhierarchy, what I understand to be a lattice, 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 lattice structure, meaning 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-lattice 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 $|S'| < l$ (minimal).

Note that 2 is redundant as it is implied by 3. However, 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; 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-lattices. 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.