2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Your "lattice" looks more like a poset with one maximal element; a lattice has stricter properties than what you describe, in particular, any two elements have a unique least upper bound. Also, it looks like a solution would be to take the immediate children of the root, and see which of those form a cover. If you look at this subproblem, you may be able to reduce set-cover to it. However, if you do indeed have a lattice structure, you could start by computing the least upper bound of G to simplify things. Gerhard "Ask Me About System Design" Paseman, 2010.07.17 $\endgroup$ Jul 17, 2010 at 16:48
  • $\begingroup$ You are exactly right, after looking at the definitions I think what I have is a poset with one maximal element, not even a semi-lattice. I will correct the problem statement. $\endgroup$
    – dareios
    Jul 18, 2010 at 8:40

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I do not think that his edge relation is transitive, but that its transitive closure does induce a partial order. His conditions are weak enough that the structure may not even be a semilattice; it is possible that two children a and b each have two direct parents x and y, which means a and b do not have a least upper bound. However, I think your reduction holds. Gerhard "Ask Me About System Design" Paseman, 2010.07.17 $\endgroup$ Jul 17, 2010 at 18:58
  • $\begingroup$ Gerhard Paseman is right, the upper bound is not unique in general. The idea for the reduction still seems to work just fine. Thank you so much for helping me formulate my problem correctly and even solve it! $\endgroup$
    – dareios
    Jul 18, 2010 at 8:43
  • $\begingroup$ I have removed my incorrect assertion that a finite poset with a unique maximal element must be a semilattice. Thanks for pointing out the glitch. $\endgroup$ Jul 18, 2010 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.