Bipartite realization algorithm

The Bipartite realization algorithm is an algorithm in graph theory solving the bipartite realization problem, i.e. the question if 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 constructions is based on a recursive algorithm. It was never been published in a scientific paper but works similar as 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.

Is the given pair of lists 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},\cdots ,v_{n}$ and $w_{1},\cdots ,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}\},\cdots ,\{w_{i},v_{b_{1}}\}$. 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

⇐:When 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})$.

See also

• Gale–Ryser theorem

This article "Bipartite realization algorithm" is from Wikipedia. The list of its authors can be seen in its historical. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

📰 Article(s) of the same category(ies)

• The Algorithms
• Ankit's Primality Test: A New deterministic Primality Test Algorithm
• Automated Bidding in a Repeated Bidding Game
• Biologically inspired algorithms
• Trajectoid
• Parametric innovation
• Lamé’s Theorem

---