# A reduction from the maximum $k$-closure problem to the clique problem

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?
• 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?) Nov 5 at 1:54
• @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. Nov 5 at 10:40
• 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)$. Nov 5 at 13:08
• @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. Nov 5 at 14:00