Bipartite realization algorithm

The Bipartite realization algorithm is an algorithm in graph theory solving the bipartite realization problem, i.e. the question of whether there exists for two finite lists of nonnegative integers a simple bipartite graph such that its degree sequence corresponds exactly to these lists. For a positive answer, the pair of lists is called bigraphic. The algorithm constructs a special solution if one exists, or proves that one cannot find a positive answer. The construction is based on a recursive algorithm. It has never been published in a scientific paper but works similarly to the Havel-Hakimi Algorithm for the graph realization problem or the Kleitman-Wang algorithms for the digraph realization problem.

The algorithm

The algorithm is based on the following theorem.

Let $(a_{1}, \dots, a_{n})$ and $(b_{1}, \dots, b_{n})$ be two finite lists of nonnegative integers such that $a_{1} \geq \dots \geq a_{n}$ and let $b_{i} > 0$ . The pair of lists $(a_{1}, \dots, a_{n})$ , $(b_{1}, \dots, b_{n})$ is bigraphic if and only if the pair of lists $(a_{1} - 1, \dots, a_{b_{i}} - 1, a_{b_{i} + 1}, \dots, a_{n})$ , $(b_{1}, \dots, b_{i - 1}, 0, b_{i + 1}, \dots, b_{n})$ is bigraphic.

If the given pair of lists is bigraphic, then the theorem will be applied at most $n$ times on the current pair of lists. This process ends when both lists only contain zeros. In each step of the algorithm, one constructs the edges of a bipartite graph with vertices $v_{1}, \dots, v_{n}$ and $w_{1}, \dots, w_{n}$ in the two partite sets, i.e. if it is possible to reduce the lists, then we add edges ${w_{i}, v_{1}}, {w_{i}, v_{2}}, \dots, {w_{i}, v_{b_{i}}}$ . When one of the current lists contains negative entries in any step of the algorithm, the theorem proves that the lists from the beginning are not bigraphic.

Proof

⇐: If the pair $(a_{1} - 1, \dots, a_{b_{i}} - 1, a_{b_{i} + 1}, \dots, a_{n})$ , $(b_{1}, \dots, b_{i - 1}, 0, b_{i + 1}, \dots, b_{n})$ is bigraphic, then there exists a labeled bipartite graph $G (U, V, E)$ with this degree sequence. Especially vertex $v_{i}$ has degree zero. We connect vertex $v_{i}$ with vertices $u_{1}, \dots, u_{b_{i}}$ by edges and get a bipartite graph with degree sequence $(a_{1}, \dots, a_{n})$ , $(b_{1}, \dots, b_{n})$ .

⇒: We consider a bipartite graph $G (U, V, E)$ with degree sequence $(a_{1}, \dots, a_{n})$ , $(b_{1}, \dots, b_{n})$ such that a maximum number of vertices $u_{1}, \dots, u_{b_{i}}$ is adjacent to vertex $v_{i}$ . Assume one of these vertices, say $u_{j}$ , is not adjacent to vertex $v_{i}$ . Then there is a vertex $u_{k}$ with $k > b_{i} \geq j$ such that ${u_{j}, v_{i}}$ is no edge and ${u_{k}, v_{i}}$ is one. Since $a_{j} \geq a_{k}$ there is a further vertex $v_{l}$ such that ${u_{j}, v_{l}}$ is an edge and ${u_{k}, v_{l}}$ is none. We delete in $G$ the edges ${u_{k}, v_{i}}, {u_{j}, v_{l}}$ and add the edges ${u_{j}, v_{i}}, {u_{k}, v_{l}}$ obtaining a bipartite graph $G^{'}$ with the same degree sequence. The number of adjacent vertices of vertex $v_{i}$ in $u_{1}, \dots, u_{b_{i}}$ is larger than in $G$ , in contradiction to our assumption. We conclude that in $G$ vertex $v_{i}$ is adjacent to all vertices $u_{1}, \dots, u_{b_{i}}$ . We delete in $G$ all incident edges of $v_{i}$ and get a bipartite graph with degree sequence $(a_{1} - 1, \dots, a_{b_{i}} - 1, a_{b_{i} + 1}, \dots, a_{n})$ , $(b_{1}, \dots, b_{i - 1}, 0, b_{i + 1}, \dots, b_{n})$ .

Bipartite realization algorithm

The algorithm

Proof

See also

📰 Article(s) of the same category(ies)[edit]