finding minimal subgraph in an undirected acyclic simple graph

0
votes

I have an undirected acyclic simple graph with N nodes and N-1 edges (all nodes are connected to each others).

Removing the edge E_i splits the graph into exactly two sub-graphs having M_i and N-M_i nodes respectively.

I'm looking for an algorithm that searches the edges E_i to find the most equal partition of nodes: I want to find min(max(M_i, N-M_i)).

2
algorithmgraph-theory
If I understand correctly, you have a path and you want to find the midpoint of the path. Two nodes are the endpoints and must have degree 1. All other nodes have degree 2. Find these two nodes. Walk both of them towards each other one step at a time until you meet in the middle (or cross). - MFisherKDX
@MFisherKDX Something to consider: a graph of 4 nodes, where the center node has degree 3, and the other 3 nodes have degree 1. In other words, the graph isn't necessarily a path graph. - user3386109
yeah ... so are right. ignore my comment above. - MFisherKDX
What does it mean to "verify" a scalar integer? - Prune
Please remove the tag graph and add the tag graph-theory to help get the interest of the right people. - Jeff Learman

2 Answers

2
votes

What is an undirected acyclic connected graph? That's right, a tree.

  1. Root the tree at an arbitrary vertex and calculate the size of each vertex's subtree.
  2. Let m(i) be the size of the i-th vertex's subtree.
  3. Let's assume you have fixed edge (u, v), with depth(u) < depth(v). Then, simply calculate max(m(v), N - m(v)).
  4. The minimum of all these values is your answer.
1
votes

I'll assume that the graph is represented by an edge list; from this we can create the corresponding list of nodes with their associated edges.

Rationale:

  • Consider each node to be its own cluster, weight 1.
  • Successively "merge" each leaf node into its parent, increasing the parent's weight.
  • At each iteration, build the lightest cluster available.
  • Continue until there are only two clusters remaining; the edge connecting them is the one to remove.

Initialize:

  1. Put all leaf nodes (order 1) into a list.
  2. Sort the list by increasing weight.
  3. Take the leaf node at the top of the list; merge it into its parent (add the weights).
  4. If the resulting node is now a leaf, insert the leaf at the appropriate point in the list.

Repeat steps 3 & 4 until there are only two nodes remaining; these form the desired partition.