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:

- Delete 0 or more edges such that the graph becomes a
`VALID graph`

. - And the sum of distances from all nodes to source node is minimum.
- And the number of
`SPECIAL nodes`

is minimum possible.

Note:

- Graph is undirected.
- It is always possible to connect all nodes.
- 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

link?

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?

evil666man akashdeep amit_swami yashChandnani teja349 cerberus97 gvaibhav21 jtnydv25 iitbhu_0 codelegend akulsareen 768092 Jeel_Vaishnav rekt_n00b hitman623 Ashishgup born2rule murugappan_s PrashantM GT_18 gohan123 acraider jaker_y Enolla kristevalex Vovuh AHDPIYKO kr_abhinav nyan101 AJAYHAYAGREEVE deepsea 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.

is it necessary to minimize the number of edge removals?

No.

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

Thanks for the solution.

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

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.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?

I forgot that 10 constraint.

My entire solution fails there.

So, any alternate ideas?

Who are all those people?

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

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

Minimisation of sum has higher priority than Special nodes.

Auto comment: topic has been updated by dragoneel (previous revision, new revision, compare).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.

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.

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.

Thanks for your guidance.