Fix a partially ordered set $(P, \le)$ with $N$ elements and real weights $w(p)$ for each $p \in P$. A subset $S \subset P$ is called closed if for any $x, y$ with $y \in S$ and $x \le y$ we also have $x \in S$.

MAXIMUM $k$-CLOSURE asks us to find a closed subset $S \subset P$ with $|S| = k$ and $\sum_{s \in S} w(s)$ maximal. (If we remove the $|S| = k$ requirement, this is just MAXIMUM CLOSURE, which Picard (1976) reduced to MAX-FLOW.)

We can also formulate this problem more generally on a weighted DAG. Here a closed set is one with no incoming edges; any instance of the poset version of this problem can be converted to an instance of the DAG version by passing to the Hasse diagram of the poset.

In Goldschmidt-Hochbaum (1997), "$k$-edge subgraph problems", the following claim appears (p. 165):

The closely related problem of finding a maximum weight closed set of k-nodes in a DAG is NP-complete (using a reduction from CLIQUE via the selection problem).

I have been unable to reproduce this reduction. I would like to know answers to either of the following questions:

  1. How does this reduction proceed?
  2. What, exactly, is the selection problem that Goldschmidt-Hochbaum are referring to?
  • 2
    $\begingroup$ Wait, so what role does MAXIMUM $k$-CLOSURE play in your question? It seems that all you are asking is how to reduce CLIQUE to the problem of "finding a max-weight closed set of $k$-nodes in a DAG"... (And what is the definition of that problem, anyway? Is it supposed to be the same as MAXIMUM $k$-CLOSURE?) $\endgroup$
    – Neal Young
    Nov 5 at 1:54
  • $\begingroup$ @NealYoung On a DAG one can define a closed set to be a set with no incoming edges. Then MAXIMUM $k$-CLOSURE for a poset is equivalent to solving the DAG problem on the Hasse diagram of that poset (with the obvious vertex weights). I've edited the question to make this clearer. $\endgroup$
    – dvitek
    Nov 5 at 10:40
  • 1
    $\begingroup$ This is well known. Given graph $G=(V,E)$, create a DAG $H$ where there is one node for each vertex of $G$ and one node for each edge of $G$. If $v_e$ is the node correspond to edge $ab \in E$ then make $v_e$ be preceded by $v_a,v_b$. That's it. Set $w(v_e) = 1$ for all nodes corresponding to edges and $w(v_a) = 0$ for all nodes corresponding to vertices. Set $p(v_e) = 0$ and $p(v_a) = 1$. Choosing $k$ vertices in $G$ to maximize number of edges in the induced graph is same as finding max-weight closure with bound $k$ on $p(S)$. $\endgroup$ Nov 5 at 13:08
  • $\begingroup$ @ChandraChekuri Ah, so in particular $k$-CLIQUE becomes equivalent to deciding whether or not there is a closed subset with $k+\binom{k}{2}$ nodes with weight $\binom{k}{2}$. Many thanks for the explanation; if you want to post this as an answer I'd be happy to accept it. $\endgroup$
    – dvitek
    Nov 5 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.