1
$\begingroup$

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?
Improve this question
$\endgroup$
4
  • 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, 2021 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, 2021 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$
    – Chandra Chekuri
    Nov 5, 2021 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, 2021 at 14:00

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.