govind53's blog

Graph with minimum bandwidth and at most k connected components
By govind53, history, 6 months ago, In English

There is a network graph given, in which we need to remove few edges to form at the most k connected components. Resulting graph should have minimum possible bandwidth (by bandwidth we mean maximum number of data packets which can pass through the graph). We need to identify the minimum bandwidth possible. Can someone please suggest possible approach to solve this problem?

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

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

You need to state the problem in more detail.

What do you mean by bandwidth? Pass through from where to where? Is it the same as maximum flow? Are the edges directed? Are source and sink given? If not, it's not clear at all how anything can pass through if there is more than one connected component.

Are there any bounds on the number of nodes in the network or $$$k$$$? What is the time limit? (Even if this is a problem from real life, not from a contest, you should have some realistic estimates.)

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

    If I take what is in my mind the most obvious interpretation, then this problem will be pointless and weird:

    Given an undirected graph and two vertices $$$s$$$ and $$$t$$$. You may remove any number of edges. After the removal, the graph must not have more than $$$k$$$ connected components. Minimize the maximum flow between $$$s$$$ and $$$t$$$.

    I look at all the neighbors $$$u$$$ of $$$s$$$. If there is a path $$$u \leadsto t$$$ that doesn't visit $$$s$$$, I remove the edge $$$su$$$, otherwise I don't. In total, this increases the number of connected components by one, and now there is no path from $$$s$$$ to $$$t$$$ so the maximum flow is 0.

    If $$$k$$$ is equal to the initial number of connected components (i.e. I can't create a new one), I just don't delete one of the edges I would've deleted. Now the maximum flow is 1 and the number of connected components doesn't change.

    This doesn't feel like the intended problem, so I think something is still missing.

    → Reply