月度归档:2019年10月

Partitioning Edges of an Undirected Graph into Forests

Given an undirected graph $G(V, E)$, we need to partition the edge set $E$ into several forests, i.e., edge sets which are acyclic. Specifically, we are interested in the minimum number of forests into which the set of edges can be partitioned, which is defined as the arboricity of the graph. It turns out that computing the arboricity of an undirected graph, or giving a specific edge partition into a minimum number of forests, are both solvable in polynomial time.

1. The Algorithm

We present a polynomial algorithm that solves this problem. The algorithm adds the edges one by one and maintains a set of forests in an incremental fashion. Note that adding an edge increases the minimum number of forests by at most 1. The framework of the algorithm is as follows.

  1. Initialize the set of forests $\mathcal{F}$ to $\varnothing$;
  2. For each edge $e \in E(G)$, if it is possible to add $e$ by not increasing the minimum number of forests, then add it; otherwise, let $\mathcal{F} \leftarrow \mathcal{F} + \{e\}$.

The hard part is to determine if it is possible to add an edge without increasing the number of forests. Note that simply trying to add the edge into every forest is incorrect because it is possible to move some edges between the forests to make room for the new edge to fit in some forest.

The algorithm is to build an auxiliary directed graph and find an augmenting path. The vertex set of the auxiliary graph is $\mathcal{F} \cup E’ \cup \{e\}$, where $E’$ is the set of edges that are already added. There is an edge $e_1 (\in E) \rightarrow f (\in \mathcal{F})$ if $f \cup \{e\}$ is acyclic, and there is an edge $e_1 (\in E’) \rightarrow e_2 (\in E’)$ if replacing $e_2$ with $e_1$ in the forest of $e_2$ yields a valid forest. If there exists a directed path from $e$ to any $f$, then performing all operations represented by these edges simultaneously yields a set of forests of the same size; otherwise, we must increment the number of forests.

2. Remark

This problem is a special case of the matroid partition problem, which asks the minimum number of independent sets to which a matroid can be partitioned. The general problem is also polynomially solvable; an algorithm similar to the one presented above works.

3. References

  1. Arboricity. Wikipedia, https://en.wikipedia.org/wiki/Arboricity.
  2. Edmonds, Jack (1965), “Minimum partition of a matroid into independent subsets”, Journal of Research of the National Bureau of Standards, 69B: 67–72.