Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

dragoneel's blog

By dragoneel, history, 4 weeks 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  

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

link?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I created this problem without thinking about the solution, I didn't find anything similar anywhere. If something strikes you, can you provide an idea?

»
4 weeks ago, # |
Rev. 3   Vote: I like it -102 Vote: I do not like it
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    is it necessary to minimize the number of edge removals?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No.

      • »
        »
        »
        »
        4 weeks 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

        • »
          »
          »
          »
          »
          4 weeks 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?

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I forgot that 10 constraint.

            My entire solution fails there.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Who are all those people?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      These are the people whose solution I have referred to in the past for the problems I was unable to solve.

  • »
    »
    4 weeks 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?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Minimisation of sum has higher priority than Special nodes.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by dragoneel (previous revision, new revision, compare).

»
4 weeks 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.

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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.