<p>Fix a partially ordered set <span class="math-container">$(P, \le)$</span> with <span class="math-container">$N$</span> elements and real weights <span class="math-container">$w(p)$</span> for each <span class="math-container">$p \in P$</span>.  A subset <span class="math-container">$S \subset P$</span> is called <em>closed</em> if for any <span class="math-container">$x, y$</span> with <span class="math-container">$y \in S$</span> and <span class="math-container">$x \le y$</span> we also have <span class="math-container">$x \in S$</span>.</p>
<p><strong>MAXIMUM <span class="math-container">$k$</span>-CLOSURE</strong> asks us to find a closed subset <span class="math-container">$S \subset P$</span> with <span class="math-container">$|S| = k$</span> and <span class="math-container">$\sum_{s \in S} w(s)$</span> maximal.  (If we remove the <span class="math-container">$|S| = k$</span> requirement, this is just <strong>MAXIMUM CLOSURE</strong>, which Picard (1976) reduced to <strong>MAX-FLOW</strong>.)</p>
<p>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.</p>
<p>In Goldschmidt-Hochbaum (1997), &quot;<span class="math-container">$k$</span>-edge subgraph problems&quot;, the following claim appears (p. 165):</p>
<blockquote>
<p>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).</p>
</blockquote>
<p>I have been unable to reproduce this reduction.  I would like to know answers to either of the following questions:</p>
<ol>
<li>How does this reduction proceed?</li>
<li>What, exactly, is the selection problem that Goldschmidt-Hochbaum are referring to?</li>
</ol>

CC BY-SA 4.0
2021-11-05T01:54:15.950Z
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?)
Neal Young
CC BY-SA 4.0
2021-11-05T10:40:00.853Z
@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.
dvitek
CC BY-SA 4.0
2021-11-05T13:08:22.550Z
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)$.
Chandra Chekuri
CC BY-SA 4.0
2021-11-05T14:00:45.570Z
@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.
dvitek
<cc.complexity-theory><graph-algorithms><np-hardness><reductions><directed-acyclic-graph>
A reduction from the maximum $k$-closure problem to the clique problem
dvitek
# A reduction from the maximum $k$-closure problem to the clique problem

(Asked by: username_0 on 2021-11-05)

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?

**Tags:** cc.complexity-theory, graph-algorithms, np-hardness, reductions, directed-acyclic-graph

> **Comments:**
> **username_1**: 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?)  
> **username_0**: @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.  
> **username_2**: 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)$.  
> **username_0**: @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.  

---

## 0 answers

