Selecting k sub-posets - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T15:42:48Z http://mathoverflow.net/feeds/question/32290 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/32290/selecting-k-sub-posets Selecting k sub-posets dareios 2010-07-17T15:30:21Z 2010-07-27T18:02:27Z <p>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 <a href="http://en.wikipedia.org/wiki/Set_cover_problem" rel="nofollow">set cover problem</a>.</p> <p>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.</p> <p>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$.</p> <p>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:</p> <ol> <li>$G \subseteq \bigcup_{i=1}^{l} \sigma(s_i)$ ($S$ covers $G$).</li> <li>$\forall s_i, s_j \in S, i \neq j: \sigma(s_i) \nsubseteq \sigma(s_j)$ (no redundant vertices in $S$).</li> <li>$\nexists S' \subseteq V$ that satisfies 1 with $k \leq |S'| &lt; l$ (minimal).</li> </ol> <p>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.</p> <p>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$.</p> <p>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.</p> <p>Devising an approximation algorithm that satisfies 1 &amp; 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.</p> <p>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?</p> <p>This is my first post on MathOverflow, so I hope I chose the right tags, please feel free to improve my tagging.</p> http://mathoverflow.net/questions/32290/selecting-k-sub-posets/32300#32300 Answer by András Salamon for Selecting k sub-posets András Salamon 2010-07-17T18:11:46Z 2010-07-27T18:02:27Z <p>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.</p> <p>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.</p> <p>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).</p> <p>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.</p> <p>I hope I have managed to capture your problem correctly.</p>