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. I have to solve the following problem, which looks a lot like the set cover problem.

I uploaded my Latex-ed problem description here.

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.

Does anyone know if this problem has a proper name, or maybe the tree-version of the problem? I would be interested to find out if this problem is NP-hard, maybe someone has ideas for a good NP-hard problem to reduce or has a polynomial algorithm to solve the problem. If you have both collect your million dollar price. ;)

Answer 1

The DAG version is hard by (drum roll) a reduction from set cover. Set k = 2 and do the obvious: condition (2) prevents us from taking the root. (Note that (3) doesn't actually imply (2) because of the lower bound k.)

The tree version is a special case of the series-parallel poset version, which can be solved exactly in polynomial time. Here's a recursive formula that gives a polynomial p(x) where the coefficient of xⁿ is the number of covers of cardinality n.

Single vertex to be covered: p(x) = x.

Other vertex: p(x) = 1 + x.

Parallel composition, where q and r are the polynomials for the two posets: q(x) r(x).

Series composition, where q is the polynomial for the top poset and r, for the bottom: If the top poset contains no vertices to be covered, then p(x) = (q(x) - 1) + r(x); otherwise, p(x) = q(x).