<p><strong>The problem</strong></p>

<p>Given </p>

<ul>
<li>a (connected) DAG $G(V,E)$ where each node is assigned an (non-negative) integer
weight</li>
<li>an integer k where $0\leq k\leq|V|$</li>
</ul>

<p>Find a induced subgraph $H$ of $G$ consisting of $k$ vertices such that</p>

<ul>
<li>if a vertex is in $H$, all of its predecessors are also in $H$ (=closure?)</li>
<li>The sum of the weights for all vertices in $H$ is minimized</li>
</ul>

<p><strong>Possible algoritms</strong></p>

<p>a trivial algorithm to solve this problem is to loop over all subsets of the vertices with size $k$ and check if the first condition holds. If so check if the sum of weigths is smaller than the current best one found. This algorithm would be $O(V×V!)$. For large graphs this would be extremely slow.</p>

<p>Is there a more efficiënt algorithm?</p>

<p>I have considered an greedy algorithm which builds up by starting with an empty set and adds the smallest weight vertex where the first condition would still hold. This algorithm does not always give the correct result. </p>

<p><strong>Edit:</strong> An example</p>

<pre><code>weights: vertex 1:weight 6, 2:4, 3:3, 4:4, 5:1, 6:3, 7:6, 8:7, 9:1, 10:4
connections: 1-&gt;3, 2-&gt;3, 2-&gt;4, 3-&gt;5, 3-&gt;7, 4-&gt;6, 4-&gt;8, 5-&gt;7, 6-&gt;8, 7-&gt;9, 8-&gt;9, 8-&gt;10
</code></pre>

<p>for $k=4$ a greedy algorithm will return {1,2,4,6} with total weight 17, whilst {1,2,3,5} has total weight 14.</p>

CC BY-SA 3.0
2018-03-23T19:42:48.387Z
Just to confirm, weights can be negative?
D.W.
CC BY-SA 3.0
2018-03-24T09:16:14.717Z
They don't have to be. a solution where all weights are positive is fine with me
Jelmer Firet
CC BY-SA 3.0
2018-03-24T22:27:29.483Z
I think your problem is NP-hard by reduction from Bipartite Expansion (see e.g. [here](https://pdfs.semanticscholar.org/6c29/2af8b5eb9b3dc3b8ad216833063941b5c9be.pdf)).  Given an n-vertex bipartite graph G'=(U,W,E') and integers b and c, the problem is to find a b-subset of U with at most c neighbors in W.  To reduce to your problem, create DAG G with two levels by duplicating each vertex in U n^2 times and directing all edges from W to U.  Give each vertex in U weight zero and each vertex in W weight 1, then ask for a sol'n to your problem with k = b n^2 vertices and total weight at most c. ?
Neal Young
CC BY-SA 3.0
2018-03-25T07:51:01.980Z
@NealYoung I think you're right. I would phrase it as followed:
Because bipartite expansion is NP-hard, the problem to find a b-subset of U with **exactly** c neighbors in W is also NP-hard. (otherwise just loop over all c to get a polynomial solution to bipartite expansion). Given a DAG with 2 levels: U,W where all edges go from U to W. All weights of U are 1, those of W are 0. the problem of finding a k-closure is equivalent to finding the minimum c such that there exists an (k-c)-subset of W with c neighbors in U. that problem was NP-hard so the k-closure must be too?.
Jelmer Firet
<np-hardness><directed-acyclic-graph>
min weight k-closure on DAG
Jelmer Firet
# min weight k-closure on DAG

(Asked by: username_0 on 2018-03-23)

The problem
Given 

a (connected) DAG $G(V,E)$ where each node is assigned an (non-negative) integer
weight
an integer k where $0\leq k\leq|V|$

Find a induced subgraph $H$ of $G$ consisting of $k$ vertices such that

if a vertex is in $H$, all of its predecessors are also in $H$ (=closure?)
The sum of the weights for all vertices in $H$ is minimized

Possible algoritms
a trivial algorithm to solve this problem is to loop over all subsets of the vertices with size $k$ and check if the first condition holds. If so check if the sum of weigths is smaller than the current best one found. This algorithm would be $O(V×V!)$. For large graphs this would be extremely slow.
Is there a more efficiënt algorithm?
I have considered an greedy algorithm which builds up by starting with an empty set and adds the smallest weight vertex where the first condition would still hold. This algorithm does not always give the correct result. 
Edit: An example
weights: vertex 1:weight 6, 2:4, 3:3, 4:4, 5:1, 6:3, 7:6, 8:7, 9:1, 10:4
connections: 1->3, 2->3, 2->4, 3->5, 3->7, 4->6, 4->8, 5->7, 6->8, 7->9, 8->9, 8->10

for $k=4$ a greedy algorithm will return {1,2,4,6} with total weight 17, whilst {1,2,3,5} has total weight 14.

**Tags:** np-hardness, directed-acyclic-graph
> **Comments:**
> **username_1**: Just to confirm, weights can be negative?  
> **username_0**: They don't have to be. a solution where all weights are positive is fine with me  
> **username_2**: I think your problem is NP-hard by reduction from Bipartite Expansion (see e.g. [here](https://pdfs.semanticscholar.org/6c29/2af8b5eb9b3dc3b8ad216833063941b5c9be.pdf)).  Given an n-vertex bipartite graph G'=(U,W,E') and integers b and c, the problem is to find a b-subset of U with at most c neighbors in W.  To reduce to your problem, create DAG G with two levels by duplicating each vertex in U n^2 times and directing all edges from W to U.  Give each vertex in U weight zero and each vertex in W weight 1, then ask for a sol'n to your problem with k = b n^2 vertices and total weight at most c. ?  
> **username_0**: @NealYoung I think you're right. I would phrase it as followed: Because bipartite expansion is NP-hard, the problem to find a b-subset of U with **exactly** c neighbors in W is also NP-hard. (otherwise just loop over all c to get a polynomial solution to bipartite expansion). Given a DAG with 2 levels: U,W where all edges go from U to W. All weights of U are 1, those of W are 0. the problem of finding a k-closure is equivalent to finding the minimum c such that there exists an (k-c)-subset of W with c neighbors in U. that problem was NP-hard so the k-closure must be too?.  

---

## 0 answers

