freto's blog

Graph problem-Need help
By freto, history, 6 years ago, In English

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

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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.

→ Reply