4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Just to confirm, weights can be negative? $\endgroup$ – D.W. Mar 23 '18 at 19:42
  • $\begingroup$ They don't have to be. a solution where all weights are positive is fine with me $\endgroup$ – Spaanse Mar 24 '18 at 9:16
  • 2
    $\begingroup$ I think your problem is NP-hard by reduction from Bipartite Expansion (see e.g. here). 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. ? $\endgroup$ – Neal Young Mar 24 '18 at 22:27
  • $\begingroup$ @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?. $\endgroup$ – Spaanse Mar 25 '18 at 7:51

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.