dragoneel's blog

Graph problem to minimise total distance from all nodes to a source node under constraints.
By dragoneel, history, 5 years ago, In English

I was solving some graph problems with dp and bitmasking when a problem crossed my mind. But I'm unable to solve it optimally. I tried brute force considering all possible combinations. Can we form an optimal solution?

The problem goes like this:

SPECIAL node : Can connect upto 10 nodes.

GOOD node: Is only connected to exactly 1 SPECIAL node and no other node.

VALID edge: Has atleast one SPECIAL node.

VALID graph: A connected graph such that every edge is a VALID edge and each node is either a GOOD node or a SPECIAL node.

Given a connected graph with N nodes (including a source node), your task is to:

  1. Delete 0 or more edges such that the graph becomes a VALID graph.
  2. And the sum of distances from all nodes to source node is minimum.
  3. And the number of SPECIAL nodes is minimum possible.

Note:

  1. Graph is undirected.
  2. It is always possible to connect all nodes.
  3. Minimisation of sum has higher priority than minimisation of SPECIAL nodes.

Constraints:

1<N<=30
1<=E<=435
1<=src<=30

Input: N -> total number of nodes

E edges with values: u v w (there is an edge between u and v with length w)

src -> index of source node

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
5 years ago, # |
← Rev. 3   Vote: I like it -102 Vote: I do not like it

pranjal.ssh akashdeep amit_swami yashChandnani teja349 cerberus97 gvaibhav21 jtnydv25 IndianICPC-Joke. codelegend akulsareen shpsi Jeel_Vaishnav animeshf hitman623 Ashishgup born2rule murugappan_s PrashantM GT_18 gohan123 acraider Arigato Enolla kristevalex vovuh Jajceslav kr_abhinav nyan101 newbie_forever_at_cp walht yaksha alexwice aditya1701 jefrai architkarandikar mbrc siddharthnohria Mindyou Roooooo SiriusRen lrvideckis chinmay0906 aakashag1996 dreamplay Enigma27 saurabhrathi12 shubhamgarg18 kaushal02 nikolayterek Zxyelf lgkm39 dima_z Any help is appreciated.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    is it necessary to minimize the number of edge removals?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        run a dijkstras from source node, so we will know the min distance of each node from source.

        Which implies that we know the minimum sum of all distances from source.

        Now the problem breaks into maximizing the number of leaf nodes and thereby creating a tree.

        I have a greedy solution, idk whether it works.

        The idea is that start from farthest node/nodes(if multiple nodes exist with same distance) , increment count for all candidate parents.

        Take the candidate parent with max count and reduce the count of parents of children of currently chosen parent.

        Don't take parents when their count<=0 (they are leafs now)

        UPD : Solution doesn't work because it doesn't take the 10 constraint into consideration

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks for the solution.

          I have 2 doubts, if I have understood it correctly:

          1. If we already calculate the minimum sum of all distances before converting the graph into a VALID graph, then it might be possible that the shortest path from the src to a node which we considered earlier, might not exist after deletion of edges.

          2. Since the candidate parent we are choosing has max count, how can we determine which edges to remove to reduce its degree to 10 (a special node) since deletion of different set of edges from this node will result in different configurations of solution.

          Any ideas on how we can deal with them?

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I forgot that 10 constraint.

            My entire solution fails there.

            → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Who are all those people?

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    which of the two minimizations are more important, sum or number of special nodes?

    → Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Well any instance that will be a solution will be having a connected Core of Special Nodes and rest are like leaves to this Node. I think this is probably NP-Hard Because it is Similar to the K-CUT(each component has a special node) problem with the Cost function being more complex than of K-cut.

By the way how did you get the number 435 and 30?

One Solution that i can think of is : 1. Use Prim to get the MST from the source. Now as long as the tree is same, the distance cost will remain same. 2. take all the Internal Nodes to be Special Nodes.(if you wanna minimise the number of edges deleted too, put back the edges that were internal.) 3. If some Node has more than 10 nodes as neighbour, take the highest degree neighbour into special Set.

Note: this is an approx solution(can't prove any heuristics though) as MST is non unique.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For feasibility, I decided N=30 ,and E=435 is for a fully connected graph.

    I don't understand the part of the solution when number of neighbours>10 for current node, e.g when we have current node as a SPECIAL node with 20 leaves as its children, how should we pick SPECIAL nodes such that the degree of current node becomes <=10 meanwhile making minimum no of SPECIAL nodes.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Ok. I think i took <=10 nodes as <=10 Good Nodes. Then this is Surely NP complete as Finding a Degree Constraint Spanning Tree is NP-Complete.

      See this

      Solution to this NP problem is the Solution to the Problem, With Taking all the internal Nodes(deg>1) as Special Node.

      → Reply