Search code examples
algorithmdynamic-programminggraph-theory

Select K edges with minimum weight in linear graph

We are given a linear graph with N vertices. The task is to select K edges with no overlapping vertices than have minimum weight.

As an example, in the graph below, where N = 5 and K = 2,

enter image description here

the answer is

enter image description here

Because it has the minimum possible possible weight (2 + 2 = 4). Note thath we couldn't select edge with weight 1 because in that case, the next possible edge to select would be 6 which leads to a greater weight sum (1 + 6 = 7).

My solution so far: I have solved the problem in O(NK) time and O(N) memory using dynamic programming. I store an array DP_k of size N, where DP_k[n] is minimum weight of k edges selected from the first n edges. Then I build the array DP_k+1 by iterating from 0 to N and the formula DP_k+1[n] = min(weight[n] + DP_k[n - 2], DP_k+1[n - 1]). I do this for k = 1 to k = K and return DP_K[N] as the answer which leads to O(NK) time.

But I need to reduce the time complexity. I would really appreciate any hints on how I can do this.

Solution

  • I found an O(k log(n)) answer here from Codeforces.

    (I) For every 1 ≤ i ≤ n, insert i with cost ai into a priority_queue whose top element has the minimum cost. And keep a linked-list 1, 2, 3, ..., n.

    (II) Repeat the following steps k times:

    (II.a) Pick the top element x from the priority_queue.

    (II.b) Add the cost of x into the answer.

    (II.c) Change the cost of x into costprex + costnxtx - costx, where prex and nxtx are the previous and next element of x in the linked-list.

    (II.d) Delete prex and nxtx from the linked-list and the priority_queue.

    (II.e) Insert x with new cost into the priority_queue.