We are given a graph with n nodes.
For every pair of nodes i,j (i!=j) there is an edge from i to j and an edge from j to i. Note that both these edges may have different cost.
There is also a node S (source node). For every node i (i!=S) there is an edge from S to i. (No edge from i to S).
A wheel tree is a tree which has several linear chains connected to S. (meaning that every node except S has atmost one child.)
We are given an array D[i]. We have to construct a wheel tree from the given graph such that distance of ith node from S is <= D[i]. Distance is obviously the sum of edges.
Each chain connected to S is called a "spoke".
We have to remove some edges from the initial graph such that the distance conditions are satisfied ALSO we need to MINIMIZE the number of spokes.
I think this might be a flow problem. But am not able to solve it.
Any ideas?
EDIT:
contraints: N is <=40.
Any algorithm ( apart from brute :P )??
Auto comment: topic has been updated by freto (previous revision, new revision, compare).
The first observation is that there is unlikely to be a polynomial-time algorithm to this, because otherwise we could use the solution to this to find (and determine the existence of) a Hamiltonian circuit of an arbitrary graph in polynomial time. I think this rules out most flow-based solutions as well.
This and the 40 constraint leads me to believe the intended complexity is something like
. I think the solution is dp on bitmasks, but I can't piece it together yet.