Fact-checked by Grok 2 weeks ago

Bipartite graph

In graph theory, a bipartite graph is an undirected graph whose vertices can be partitioned into two disjoint sets such that no two graph vertices in the same set are adjacent, meaning every edge connects a vertex in one set to a vertex in the other.^[1] This partition, often denoted as sets U and V, ensures that the graph has no edges within U or within V, making it a fundamental structure for modeling binary relations.^[2] Bipartite graphs exhibit several key properties that distinguish them from general graphs, including the absence of odd-length cycles, as any cycle must alternate between the two sets and thus have even length. Equivalently, a graph is bipartite if and only if it is 2-colorable, where vertices can be colored with two colors such that no adjacent vertices share the same color, reflecting the partition into independent sets.^[3] These properties imply that bipartite graphs have chromatic number at most 2 and are useful for algorithmic efficiency in problems like graph coloring and cycle detection.^[4] Beyond their structural characteristics, bipartite graphs find wide applications in optimization and modeling real-world scenarios involving two distinct categories. For instance, they model assignment problems such as matching jobs to workers or students to courses, where one set represents candidates and the other resources.^[5] Key theorems like Hall's marriage theorem provide conditions for the existence of perfect matchings in bipartite graphs, enabling solutions to stable matching problems like the stable marriage and hospital-residents dilemma.^[6] Additionally, bipartite graphs underpin network flow algorithms for minimum vertex cover and maximum matching, with applications in scheduling, resource allocation, and computer science.^[7]

Fundamentals

Definition

A bipartite graph is an undirected graph G = (V, E) whose vertex set V can be partitioned into two disjoint independent sets U and W such that U \cap W = \emptyset, U \cup W = V, and every edge in E connects a vertex in U to a vertex in W.^[8] This partition ensures that no edges exist within U or within W, resulting in a two-part structure where interactions occur exclusively between the sets.^[9] The complete bipartite graph K_{m,n} denotes the bipartite graph with partition sets of sizes m = |U| and n = |W|, where every vertex in U is adjacent to every vertex in W, yielding m \times n edges.^[10] This notation highlights the balanced or imbalanced nature of the partitions and serves as a foundational example for studying bipartite structures. The term "bipartite" for such graphs was introduced by Dénes Kőnig in his 1931 paper "Graphok és matrixok," in the context of graph colorings and matrix theory.^[11]

Characterization

A bipartite graph is equivalently characterized as a graph that admits a proper 2-coloring of its vertices, meaning the vertices can be colored using exactly two colors such that no two adjacent vertices share the same color.^[12] This equivalence holds because the two color classes naturally form the independent sets in the bipartition.^[13] To verify 2-colorability and thus bipartiteness, a proof sketch involves applying a graph traversal algorithm such as breadth-first search (BFS) or depth-first search (DFS) from each connected component. Begin by assigning one color to a starting vertex and alternating colors for its neighbors; a conflict arises if an adjacent vertex is assigned the same color, indicating non-bipartiteness. If no conflicts occur across all components, the graph is 2-colorable.^[14] Another fundamental characterization states that a graph is bipartite if and only if it contains no odd-length cycles. In a bipartite graph, every cycle must alternate between the two partitions, resulting in even length; conversely, the presence of an odd cycle implies non-bipartiteness, as it would force at least one edge to connect two vertices in the same partition during any attempted 2-coloring, leading to a monochromatic edge by contradiction.^[13] This parity condition provides a cycle-based test for bipartiteness distinct from but equivalent to the coloring approach.^[12] From an extremal perspective, the Zarankiewicz problem characterizes the maximum number of edges in an m-by-n bipartite graph without a complete bipartite subgraph K_{s,t}, offering bounds on dense bipartite structures free of forbidden subgraphs.^[15]

Examples

Illustrative Graphs

A fundamental class of bipartite graphs is the complete bipartite graphs K_{m,n}, consisting of two disjoint vertex sets U and V with |U| = m and |V| = n, where every vertex in U connects to every vertex in V, but no edges exist within U or V.^[16] A specific instance is the star graph K_{1,n}, featuring a single central vertex adjacent to n isolated leaves, illustrating a tree structure with all edges crossing the partitions. Even-length cycles, denoted C_{2k} for integer k \geq 2, form another basic example; their vertices alternate between two partitions as one traverses the cycle, ensuring no intra-partition edges.^[17] Paths of arbitrary length are also bipartite, as they lack cycles and can be colored alternately along the chain.^[1] More generally, all trees—acyclic connected graphs—are bipartite, with partitions determined by levels from any root or by parity of distances.^[18] To contrast, non-bipartite graphs include odd-length cycles C_{2k+1}, such as the triangle C_3, which cannot be partitioned without intra-set edges due to the odd cycle.^[19] Complete graphs K_n for n \geq 3 similarly fail bipartiteness, as they contain triangles and other odd cycles among their fully connected vertices. The complete bipartite graph K_{3,3} exemplifies edge distribution: visualize two parallel rows of three vertices each (partitions U = \{u_1, u_2, u_3\} and V = \{v_1, v_2, v_3\}), with nine edges forming a dense grid where each u_i links to all v_j, but none within rows, highlighting the exhaustive cross-connections.^[16] Another illustrative construction is the bipartite double cover of a graph G, formed by duplicating each vertex v into v_1 and v_2, then replacing each original edge uv with edges u_1 v_2 and u_2 v_1; the resulting graph is always bipartite, with partitions separating the subscript-1 and subscript-2 copies, and edges solely between them.^[20] The enumeration of bipartite graphs underscores their restriction compared to general graphs: while the total number of simple labeled graphs on n vertices is $2^{\binom{n}{2}}, the count of unlabeled bipartite graphs is smaller, yielding 1, 2, 3, 7, 13, 35, and 88 for n = [1](/page/1) to $7, reflecting the limit to edges between partitions.^[1] For labeled cases, the total arises from summing over partition sizes, giving \sum_{k=0}^{n} \binom{n}{k} 2^{k(n-k)}.

Real-World Models

Bipartite graphs serve as effective models for incidence structures in geometry, where one partition represents points and the other represents lines, with edges indicating incidence relations between them. For instance, in projective geometry, the point-line incidence graph captures the relationships in finite geometries, enabling the study of combinatorial properties such as the number of incidences and extremal bounds. This modeling approach facilitates analysis in discrete geometry, where the bipartite structure highlights the absence of edges within point or line sets, reflecting the inherent separation of these geometric elements.^[21] In recommendation systems, bipartite graphs model user-item interactions by partitioning users into one set and items (such as products or media) into another, with edges representing interactions like ratings or purchases. This structure underpins collaborative filtering techniques, where the graph encodes sparse interaction data to infer preferences and generate suggestions. Seminal work in this area leverages the bipartite framework to address scalability in large-scale systems, such as those used by e-commerce platforms.^[22] Social networks often employ bipartite graphs to represent collaborations, particularly in the Hollywood actor-movie graph, where one partition consists of actors and the other of movies, with edges connecting actors to films they have appeared in. This model reveals power-law degree distributions, with actors having varying numbers of credits and movies featuring multiple casts, leading to clustering coefficients around 0.785 and average path lengths of about 3.6 in datasets from the Internet Movie Database. Such representations highlight community structures and influence propagation in creative industries without assuming direct connections within actor or movie sets.^[23] In biological networks, bipartite graphs model interactions between different molecule types, such as compounds and proteins, where one partition holds compounds (e.g., drugs) and the other proteins (e.g., targets), with edges denoting binding or functional associations. This approach is common in drug discovery and systems biology, allowing the integration of heterogeneous data like compound-protein interaction networks to predict novel associations. For example, in compound-protein prediction tasks, the bipartite structure supports graph neural network models that learn embeddings from these interactions across diverse biological entities.^[24] Transportation and logistics systems utilize bipartite graphs to model supply-demand matching, with one partition representing supply nodes (e.g., warehouses or sources) and the other demand nodes (e.g., customers or destinations), where edges incorporate costs or capacities for potential shipments. This formulation transforms the transportation problem into a network flow optimization setup, enabling efficient allocation in scenarios like freight routing or market choice decisions. In such models, the bipartite nature ensures that flows occur only between supply and demand, reflecting real-world constraints in logistics planning.^[25]

Properties

Structural Properties

A bipartite graph G = (V, E) with bipartition (U, V), where U and V partition the vertex set and all edges connect vertices between U and V, has the property that both U and V are independent sets—no edges exist within either set.^[26] This structural feature ensures the absence of edges connecting vertices in the same partition, distinguishing bipartite graphs from those with intra-partition connections.^[26] As a consequence of lacking odd-length cycles, bipartite graphs are inherently triangle-free, since a triangle constitutes a cycle of length three.^[27] This triangle-free nature extends to the prohibition of any odd cycles, reinforcing the independence of the partitions and limiting possible subgraph structures.^[27] Regarding planarity, not all bipartite graphs are planar; for instance, the complete bipartite graph K_{3,3} cannot be embedded in the plane without edge crossings.^[28] Kuratowski's theorem characterizes planar graphs as those without K_5 or K_{3,3} as minors, and since K_{3,3} is bipartite, any bipartite graph containing a K_{3,3} minor is non-planar.^[29] The complement of a bipartite graph exhibits a distinct clique structure: with partitions U and V, the complement forms complete cliques on U and on V, augmented by edges between U and V precisely where the original graph lacked them.^[30] This results in a cobipartite graph, where the vertex set partitions into two cliques, highlighting the duality between bipartite and clique-based structures.^[30] Spectral properties of bipartite graphs arise from the block structure of their adjacency matrix, which, when vertices are ordered by partitions, takes the form

\begin{pmatrix} 0 & B \\ B^T & 0 \end{pmatrix},

where B is the biadjacency matrix.^[31] A hallmark feature is the symmetry of the spectrum about zero: the eigenvalues are symmetric, meaning if \lambda is an eigenvalue with multiplicity m, then -\lambda is also an eigenvalue with multiplicity m.^[31] This property reflects the balanced, two-part nature of the graph without delving into explicit computations.^[31]

König's Theorem

König's theorem, proved by Dénes König in 1931, states that in any bipartite graph, the cardinality of a maximum matching equals the cardinality of a minimum vertex cover.^[32] This duality highlights a fundamental optimization property unique to bipartite graphs, where the minimum number of vertices needed to cover all edges matches the maximum number of pairwise disjoint edges. A common proof outline begins with a maximum matching M and constructs a vertex cover C of the same size by including all unsaturated vertices in one partite set and the endpoints in the other set reached via alternating paths starting from unsaturated vertices.^[33] These alternating paths, which alternate between edges in M and not in M, cannot form augmenting cycles due to the bipartiteness, ensuring no larger matching exists and that C covers all edges. One direction of the proof—that the vertex cover size is at most the matching size—relies on Hall's marriage theorem, which ensures matchings exist when neighborhood sizes satisfy certain expansion conditions, allowing the inductive construction of covers.^[33] In contrast, non-bipartite graphs satisfy only the inequality that the maximum matching size is at most the minimum vertex cover size, as captured by the Gallai identities, which relate these quantities to the independence number and edge cover size without equality in general.^[34] The theorem's implications enable efficient computation of minimum vertex covers in bipartite graphs by reducing the problem to finding a maximum matching, solvable in polynomial time.^[33] It also connects to total coloring, where the edge-coloring version of König's theorem (stating that the chromatic index equals the maximum degree Δ) allows vertices to be colored with an additional color beyond the Δ edge colors, yielding a total chromatic number of Δ + 1 for bipartite graphs.^[35] An important extension addresses edge covers: in any graph without isolated vertices, the size of a minimum edge cover equals the number of vertices minus the size of a maximum matching, a relation that in bipartite graphs follows directly from König's theorem via the Gallai identities.^[34]

Degree Sequences

In bipartite graphs, the degree sequence is partitioned into two non-increasing sequences of non-negative integers, one for each part of the vertex partition, say d = (d_1 \geq d_2 \geq \cdots \geq d_m) for the first part and e = (e_1 \geq e_2 \geq \cdots \geq e_n) for the second part. A pair of sequences (d, e) is said to be bipartite graphical (or bigraphic) if there exists a simple bipartite graph realizing these degrees. The Gale-Ryser theorem provides the necessary and sufficient conditions for this realization.^[36] The theorem states that (d, e) is bigraphic if and only if \sum_{i=1}^m d_i = \sum_{j=1}^n e_j and the conjugate partition e^* of e majorizes d. Here, the conjugate e^* is defined such that e^*_k is the number of parts in e that are at least k, for k = 1, 2, \dots, \max e_j. Majorization means that \sum_{i=1}^k d_i \leq \sum_{i=1}^k e^*_i for all k = 1, \dots, m, with equality when k = m. This condition ensures the existence of a (0,1)-matrix with row sums d and column sums e, which corresponds directly to the adjacency matrix of the bipartite graph. The theorem was established independently by Gale and by Ryser. For example, consider a k-regular bipartite graph with equal part sizes m = n. The degree sequences are both (k, k, \dots, k) ( m times each), and the total edges match as k m = k n. The conjugate of the column sequence is (m, m, \dots, m) ( k times, padded with zeros), which majorizes the row sequence since both are uniform and sums equal, confirming realizability (e.g., the complete bipartite graph K_{m,m} achieves this for k = m). In contrast, for general (non-bipartite) graphs, the Erdős–Gállai theorem characterizes a single degree sequence d_1 \geq \cdots \geq d_N via \sum_{i=1}^k d_i \leq k(k-1) + \sum_{i=k+1}^N \min(d_i, k) for k = 1, \dots, N, with equality in the total sum; this accounts for potential odd cycles absent in bipartite realizations.^[36] The Gale-Ryser theorem extends to applications in generating random bipartite graphs via the configuration model, where stubs (half-edges) are paired randomly according to the prescribed degrees d and e. For the resulting multigraph to admit a simple graph realization, the sequences must satisfy the theorem's conditions; otherwise, multiple edges or loops may occur, and conditioning on simplicity yields a uniform random simple bipartite graph with those degrees. This model is widely used to study properties like connectivity and matching sizes under fixed degree distributions.

Connections to Other Structures

Bipartite graphs are intimately connected to hypergraphs through the concept of incidence graphs. The incidence graph of a hypergraph H = (V, E) is a bipartite graph with partite sets V (the vertices of H) and E (the hyperedges of H), where an edge exists between a vertex v \in V and a hyperedge e \in E if and only if v \in e. This construction preserves the incidence structure of the hypergraph while embedding it into a bipartite framework. Conversely, every bipartite graph can be interpreted as the incidence graph of a hypergraph, where one partite set represents vertices and the other represents hyperedges; in cases with multiple edges, this corresponds to a multihypergraph.^[37] In the context of directed graphs, bipartite graphs admit straightforward acyclic orientations. Specifically, by directing all edges from one partite set to the other, any bipartite graph becomes a directed acyclic graph (DAG) with no directed cycles, leveraging the absence of odd cycles in the undirected structure. This orientation yields a bipartite DAG, where the two partite sets serve as natural layers. Furthermore, complete bipartite graphs can be oriented to form bipartite tournaments, which are directed graphs without symmetric edges and with specific regularity properties in balanced cases.^[38]^[39] Bipartite multigraphs extend the simple bipartite graph model by permitting multiple edges between vertices in different partite sets, while weighted bipartite graphs incorporate real-valued weights on edges without altering the underlying bipartition. These variants maintain core bipartite properties, such as the absence of odd cycles, and facilitate modeling scenarios involving capacities or multiplicities. For infinite bipartite graphs, foundational results like König's duality theorem extend to the infinite setting, ensuring the existence of matchings that cover infinite sets under certain conditions. A related highlight is König's lemma, which applies to infinite trees—a special class of bipartite graphs without cycles—stating that every infinite, finitely branching tree contains an infinite path. This underscores the structural parallels between finite and infinite bipartite graphs in combinatorial contexts.

Algorithms

Testing Bipartiteness

Testing bipartiteness of a graph can be accomplished efficiently using graph traversal algorithms that attempt to 2-color the vertices, leveraging the equivalence between bipartiteness and 2-colorability.^[14] The breadth-first search (BFS)-based algorithm begins by selecting an arbitrary uncolored vertex as the source and assigning it color 0. It then explores the graph layer by layer, assigning color 1 to all neighbors of color-0 vertices and color 0 to their neighbors, ensuring adjacent vertices receive opposite colors. During traversal, if an edge connects two vertices of the same color, an odd-length cycle is detected, indicating the graph is not bipartite. This process runs in O(|V| + |E|) time, visiting each vertex and edge exactly once.^[40]^[41] To handle disconnected graphs, the algorithm iterates over all vertices, initiating a BFS from any uncolored vertex to process each connected component separately. If no color conflicts arise across all components, the graph is bipartite, and the coloring provides the two partitions.^[40] A depth-first search (DFS) variant operates recursively or via a stack, starting from a source vertex colored 0 and coloring each subsequent vertex opposite to its parent. Upon encountering a back edge or adjacent edge to a visited vertex, it verifies that the colors differ; a match signals a non-bipartite graph. Like BFS, this achieves O(|V| + |E|) time complexity and extends naturally to disconnected graphs by traversing unvisited components.^[42]^[43] Union-find structures can be adapted for this task by maintaining disjoint sets for color classes within components, unioning vertices with their opposites across edges and detecting conflicts via path compression and rank heuristics, though traversal methods remain more conventional for static graphs. The correctness of these approaches follows from the 2-colorability characterization: successful coloring without conflicts confirms bipartiteness and yields the partition sets.^[14]

Odd Cycle Transversal

An odd cycle transversal (OCT) of an undirected graph G = (V, E) is a subset S \subseteq V such that the graph G - S induced by V \setminus S contains no odd-length cycles and is thus bipartite. The minimum odd cycle transversal problem asks for the smallest such S, and it is a canonical graph editing problem aimed at achieving bipartiteness through vertex deletions.^[44] The decision version of minimum OCT, parameterized by the solution size k = |S|, is NP-complete in general graphs.^[45] However, the problem is fixed-parameter tractable (FPT), admitting algorithms running in time f(k) \cdot n^{O(1)} for some computable function f, where n = |V|. The seminal FPT algorithm, introduced by Reed, Smith, and Vetta in 2004, employs iterative compression to solve disjoint instances of OCT and achieves a runtime of O(2^k n^3).^[44] Subsequent improvements have refined this to single-exponential time, such as O(2.3146^k) using techniques like measure-and-conquer analysis.^[46] If the input graph G is already bipartite, the minimum OCT is trivially the empty set, as no odd cycles exist to hit; this case reduces to standard bipartiteness testing via BFS or DFS in linear time. For non-bipartite graphs, algorithms for OCT often adapt methods from the feedback vertex set (FVS) problem, which hits all cycles, by focusing exclusively on odd cycles through branching or dynamic programming on conflict graphs derived from potential bipartitions.^[47] The minimum OCT problem admits an integer linear programming (ILP) formulation as follows: introduce a binary variable x_v \in \{0,1\} for each vertex v \in V indicating whether v is selected in the transversal; minimize \sum_{v \in V} x_v subject to \sum_{v \in C} x_v \geq 1 for every odd cycle C in G. This ILP has exponentially many constraints due to the potential number of odd cycles, rendering it impractical for direct solving without enumeration; however, in parameterized settings, it can be addressed via separation oracles that efficiently find violated constraints using flow-based methods or randomized techniques.^[46] Reductions to ILP solvers are common in FPT algorithms, often via relaxations solved to optimality with rounding or branch-and-bound tailored to the parameter k. Regarding 2-SAT reductions, OCT is FPT-equivalent to Almost 2-SAT (where at most k clauses are violated in a 2-CNF formula), allowing bidirectional parameterized reductions that transform instances while preserving the parameter size.^[48] In the context of parameterized complexity, kernelization techniques for OCT reduce the input instance to one whose size is bounded by a polynomial in k, enabling faster resolution. A notable approach uses linear matroids to encode odd cycle hitting constraints, yielding a kernel with O(k^2) vertices through a series of min-cut computations interpreted matroidally. More recent developments include randomized polynomial kernels of size O(k^2 \log k) via iterative compression simulations, and deterministic ones for restricted graph classes like planar graphs. These kernels facilitate preprocessing in FPT solvers and highlight OCT's role in advancing kernelization theory.^[45]^[49]

Matching Algorithms

In bipartite graphs, finding a maximum matching—a largest set of edges with no shared vertices—is a fundamental problem with applications in resource allocation and scheduling. A key theoretical foundation is Hall's marriage theorem, which provides a necessary and sufficient condition for the existence of a perfect matching (one that covers all vertices in both partitions). For a bipartite graph G = (U \cup V, E) with |U| = |V|, there exists a perfect matching if and only if for every subset S \subseteq U, the neighborhood N(S) \subseteq V satisfies |N(S)| \geq |S|; this condition symmetrically holds when swapping U and V.^[50] The theorem, proved using combinatorial arguments on systems of distinct representatives, ensures no "bottleneck" subsets obstruct a complete matching.^[50] Algorithms for computing maximum matchings in bipartite graphs typically rely on finding and augmenting along paths that increase the matching size, starting from an empty matching and repeating until no such path exists. The Hungarian algorithm, developed by Harold W. Kuhn in 1955, solves the assignment problem (a weighted variant) but adapts to unweighted maximum cardinality matching by treating all edges equally. It proceeds by iteratively identifying augmenting paths using a step-by-step process: maintain dual variables (potentials) for vertices to ensure reduced costs are non-negative, then use breadth-first search (BFS) or depth-first search (DFS) in the equality subgraph to find shortest augmenting paths, updating the matching and adjusting potentials after each augmentation. This yields a time complexity of O(|V|^3) for graphs with |V| vertices, making it efficient for dense graphs up to moderate sizes.^[51]^[51] For improved efficiency on sparse graphs, the Hopcroft-Karp algorithm, introduced by John E. Hopcroft and Richard M. Karp in 1973, achieves O(|E| \sqrt{|V|}) time by augmenting multiple vertex-disjoint shortest augmenting paths simultaneously in each phase. It builds a layered graph via BFS from all free vertices in one partition, assigning levels based on distance; then, using DFS, it finds blocking flows—maximal sets of shortest augmenting paths—within these layers, ensuring no path crosses layers improperly. Phases continue until no augmenting paths remain, with at most \sqrt{|V|} phases needed due to the increasing length of shortest paths. This method outperforms the Hungarian algorithm on large, sparse instances, such as those in network flow modeling.^[52]^[52] While Edmonds' blossom algorithm handles maximum matchings in general (non-bipartite) graphs by shrinking odd cycles ("blossoms") encountered during augmenting path searches, bipartite graphs simplify this process: the absence of odd cycles eliminates blossoms, reducing the algorithm to a pure augmenting path search akin to Hopcroft-Karp but without contraction overhead, confirming the equivalence of maximum matching size to minimum vertex cover size via König's theorem.^[53]

Applications

Combinatorial Optimization

Bipartite graphs play a central role in the assignment problem, which seeks to assign a set of agents to a set of tasks in a way that minimizes the total cost, assuming one-to-one assignments. This is formulated as finding a minimum-cost perfect matching in a complete bipartite graph, where one partition represents agents, the other tasks, and edge weights denote assignment costs.^[54] The problem is solved efficiently using the Hungarian algorithm, which iteratively adjusts dual variables to find an optimal solution in polynomial time.^[51] Alternatively, the assignment problem can be reduced to a minimum-cost flow problem by constructing a flow network with unit capacities from a source to agents, from tasks to a sink, and costs on agent-task edges, solvable via successive shortest path algorithms.^[55] The transportation problem extends this framework to scenarios with multiple units shipped from supply nodes to demand nodes, minimizing total shipping costs while respecting supply and demand constraints. Modeled as a bipartite graph with supplies and demands as partitions, edges represent shipping routes with associated costs and capacities.^[56] The problem is balanced when total supply equals total demand, allowing a feasible flow that saturates all constraints; in unbalanced cases, where supply exceeds or falls short of demand, a dummy demand or supply node is introduced with zero-cost edges to restore balance.^[57] König's theorem, stating that in any bipartite graph the size of the maximum matching equals the size of the minimum vertex cover, underpins optimization in scheduling and resource allocation. For instance, in job scheduling, the maximum matching determines the largest set of non-conflicting assignments, while the minimum vertex cover identifies the smallest set of machines or time slots needed to cover all jobs, enabling efficient resource provisioning. This duality facilitates polynomial-time solutions for these tasks via matching algorithms. Due to the bipartite structure, combinatorial optimization problems like assignment and transportation are solvable in polynomial time, with algorithms such as Hopcroft-Karp achieving O(E √V) for maximum matching, in contrast to the general traveling salesman problem, which is NP-hard even on non-bipartite graphs. Bipartite graphs are widely used in network and social analysis to model relationships between two distinct types of entities, such as actors and events in affiliation networks. In these structures, one partition represents actors (e.g., individuals), while the other represents events (e.g., committees or groups), with edges indicating participation. This modeling approach facilitates the analysis of social structures where direct connections within the same entity type are absent. Affiliation networks capture phenomena like co-membership in organizations, enabling researchers to uncover patterns of social interaction through bipartite representations.^[58] Community detection in affiliation networks often involves projecting the bipartite graph onto one of the partitions to form a unipartite graph, where nodes from the same set are connected if they share common neighbors in the other set. This projection reveals communities based on shared affiliations, such as groups of individuals attending similar events. The Community-Affiliation Graph Model (CAGM) provides a probabilistic framework for overlapping community detection by treating the bipartite structure as node-community affiliations, allowing inference of latent groups from observed connections. Such methods have been applied to real-world datasets, like collaboration networks, to identify densely connected subgroups.^[59] In recommendation systems, bipartite graphs model interactions between users and items, such as movies or products, where edges represent ratings or purchases. This user-item structure underpins collaborative filtering, which predicts preferences by identifying patterns in the graph, such as similar users liking similar items. Matrix factorization techniques decompose the biadjacency matrix of the bipartite graph into lower-dimensional latent factors for users and items, enabling efficient recommendation generation by approximating missing edges. This approach gained prominence in the Netflix Prize competition, where it improved prediction accuracy on sparse user-item interactions. Bipartite representations help mitigate data sparsity in large-scale systems by focusing on indirect similarities via shared connections.^[60] Communication networks can be modeled as bipartite graphs with partitions for senders and receivers, capturing directed interactions like emails or messages without intra-partition edges. This setup allows analysis of information flow between distinct roles, such as individuals and topics in discussion forums. Centrality measures, including betweenness, are adapted for bipartite structures to quantify control over paths between partitions, normalized by the relative sizes of the sets to account for the graph's asymmetry. For instance, high betweenness in a sender node indicates its role as a bridge in disseminating information across receivers. These adaptations enable identification of key communicators in social media or organizational networks.^[61]^[62] Specific metrics for bipartite graphs enhance analysis in these domains, including bipartite modularity, which extends the standard modularity to quantify community strength while respecting the two-partition constraint. Defined via a modularity matrix that penalizes intra-partition connections, it supports community detection algorithms tailored to bipartite data, outperforming projections in preserving structural information. Bipartite clustering coefficients measure local density through the proportion of 4-cycles, reflecting how often pairs of nodes in one partition share multiple neighbors in the other, unlike triangles in unipartite graphs. Tools like NetworkX implement these metrics, providing functions for computing clustering and modularity on bipartite graphs to facilitate empirical social network studies.^[63]^[64]^[65]

References

[1]
Bipartite Graph -- from Wolfram MathWorld
A bipartite graph, also called a bigraph, is a set of graph vertices decomposed into two disjoint sets such that no two graph vertices within the same set ...
[2]
Bipartite Graph - an overview | ScienceDirect Topics
A bipartite graph G is a graph whose vertex set V can be partitioned into two nonempty subsets A and B (ie, A ∪ B=V and A ∩ B=Ø)
[3]
[PDF] Lecture 15 1 Overview 2 Graph Coloring
Mar 6, 2019 · Then G is 2-colorable if and only if G is bipartite. Proof. Let G be ... A graph is bipartite if and only if it does not contain an odd cycle.
[4]
5.4 Bipartite Graphs
All closed walks in a bipartite graph must have even length, since the vertices along the walk must alternate between the two parts.<|control11|><|separator|>
[5]
[PDF] Applications of Network Flow
Bipartite graphs model situations in which objects are matched with or assigned to other objects: e.g., marriages, residents/hospitals, jobs/machines.
[6]
BipartiteGraphs
Bipartite graphs are often used to model assignment problems, where the vertices of the left-hand side X represent things that need to be assigned.
[7]
[PDF] Lecture 14 - Stanford CS Theory
Feb 22, 2011 · As another application, we are going to show how to solve optimally the minimum vertex cover problem in bipartite graphs using a minimum cut ...
[8]
[PDF] 6.042J Chapter 5: Graph theory - MIT OpenCourseWare
Definition 5.2. 2. A bipartite graph is a graph together with a partition of its vertices into two sets, L and R, such that every edge is incident to a vertex ...
[9]
[PDF] 1 Bipartite maximum matching - Cornell: Computer Science
1.1 Definitions. Definition 1. A bipartite graph is a graph whose vertex set is partitioned into two disjoint sets L, R such that each edge has one endpoint in ...
[10]
[PDF] Introduction to Decision Sciences [.1in] Lecture 12 - Andrew B. Nobel
Formal: A graph is a pair G = (V,E) where ... Definition: Km,n = complete bipartite graph with vertex set partition. V = V1 ∪ V2 with |V1| = m and |V2| = n. Page ...
[11]
[PDF] Graphs and matrices - arXiv
Sep 5, 2020 · This paper, originally written in Hungarian by Dénes Kőnig in 1931, proves that in a bipartite graph, the minimum vertex cover and the max-.Missing: origin | Show results with:origin
[12]
[PDF] Diestel: Graph Theory - PRIP
There are two areas of graph theory which I find both fascinat- ing and important, especially from the perspective of pure mathematics adopted here, but which ...
[13]
[PDF] Math 7410 Graph Theory
Characterization of Bipartite Graphs. Theorem 3.3. A graph is bipartite if and only if it has no cycles of odd length. Proof. Necessity is clear: every cycle ...
[14]
[PDF] Graph Theory II 1 Coloring Graphs - DSpace@MIT
Mar 3, 2005 · Suppose that G is bipartite. This means we can color every vertex in. G either black or white so that adjacent vertices get different colors.
[15]
[2410.03702] A survey of Zarankiewicz problems in geometry - arXiv
Sep 24, 2024 · In this paper, we survey Zarankiewicz's problem, with a focus on graphs that arise from geometry. Incidence geometry, in particular, can be viewed as a ...
[16]
Complete Bipartite Graph -- from Wolfram MathWorld
A complete bipartite graph is a bipartite graph where every pair of vertices in the two sets are adjacent. It is denoted as K_(p,q).
[17]
Cycle Graph -- from Wolfram MathWorld
A cycle graph is a graph with n nodes containing a single cycle through all nodes. It is also known as an n-cycle.
[18]
Tree -- from Wolfram MathWorld
edges is a tree. All trees are bipartite graphs (Skiena 1990, p. 213). Trees with no particular node singled out are sometimes called free trees (or unrooted ...
[19]
Graph Cycle -- from Wolfram MathWorld
An acyclic graph is bipartite, and a cyclic graph is bipartite iff all its cycles are of even length (Skiena 1990, p. 213).
[20]
Bipartite Double Graph -- from Wolfram MathWorld
In a non-bipartite connected graph, exactly one double cover is bipartite. ... C_(2k+1) circledot K_1, sunlet graph C_(4k+2) circledot K_1. tesseract graph ...
[21]
[PDF] MIT OCW: Graph Theory and Additive Combinatorics - Yufei Zhao
1, let us first sketch the geometric intuition. Given a set of points P and a set of lines L, the point-line incidence graph is the bipartite graph with two ...
[22]
[PDF] Bipartite Graphs and Recommendation Systems
Oct 30, 2021 · Abstract—Bipartite graphs are used to model many real- world relationships with applications in several domains,.Missing: seminal | Show results with:seminal
[23]
[PDF] Bipartite Graphs as Models of Complex Networks - GRAAL
Actors. In this social network, two actors are connected if they have played together in a movie. This graph is widely studied for many reasons: it is very ...Missing: hollywood | Show results with:hollywood
[24]
An inductive graph neural network model for compound–protein ...
Mar 12, 2022 · The network can describe the interactions between various biological entities, such as compounds and proteins. Bipartite graphs are a frequently ...
[25]
[PDF] On the Transportation Problem With Market Choice
Apr 3, 2013 · More formally, we are given a set of supply and demand nodes that form a bipartite graph G(V1 ∪ V2,E). The nodes in set V1 represent the supply ...
[26]
[PDF] Extremal Results for the Number of Matchings and Independent Sets
A graph is bipartite if its vertices can be partitioned into two sets U and V such that every edge connects a vertex in U to a vertex in V . The neighborhood of ...
[27]
[PDF] exploiting the structure of bipartite graphs for algebraic and spectral ...
The volume of a graph G = (V,E) is its number of edges. For a bipartite graph. G = (V1,V2,E), no change in the definition is needed; the volume is simply |E ...Missing: coined | Show results with:coined
[28]
Why The Complete Bipartite Graph K3,3 Is Not Planar - Rod Hilton
Oct 29, 2011 · This is then a good thing to be shared to the other people that bipartite graph k33 is not actually planar. AS_Butler • 10 years ago. But ...Missing: coined | Show results with:coined
[29]
[1312.0210] Bipartite Minors - arXiv
Dec 1, 2013 · ... planar ... not contain K_{3,3} as a bipartite minor. Similarly, we provide a forbidden minor characterization for outerplanar graphs and forests.
[30]
[PDF] A Structure Theorem for Claw-Free Perfect Graphs - Math (Princeton)
A graph is cobipartite if it admits a cobipartition, that is, it is the complement of a bipartite graph. A graph is called peculiar by Chvátal and Sbihi [4] if ...
[31]
[PDF] Spectra of graphs - CWI
More in particular, spectral graph theory studies the relation between graph properties and the spectrum of the adjacency matrix or Laplace matrix. And the ...
[32]
A translation of "Graphok és matrixok" by Dénes Kőnig (1931) - arXiv
Sep 5, 2020 · This paper, originally written in Hungarian by Dénes Kőnig in 1931, proves that in a bipartite graph, the minimum vertex cover and the maximum matching have ...
[33]
[PDF] 1. Lecture notes on bipartite matching
Feb 8, 2011 · Theorem 1.1 (König 1931) For any bipartite graph, the maximum size of a matching is equal to the minimum size of a vertex cover. We shall ...
[34]
[PDF] Lecture 1: Matchings on bipartite graphs 1 Basic Concepts
Let us start with the so-called Gallai identities. Theorem 2.2 (Gallai Identities, 1959 [7]). For any graph G, let n = V (G), then (i) α(G) + τ(G) = n. (ii) ν( ...
[35]
[PDF] graph coloring - OSU Math Department
if neither G nor. ¯. G contains an odd cycle of length 5 as an induced cycle. References. [1] Bollobás, Modern Graph Theory. [2] Diestel, Graph Theory.
[36]
[PDF] On Realizing a Single Degree Sequence by a Bipartite Graph
The Gale-Ryser theorem characterizes bigraphic degree partitions. 2 All sequence that we consider are assumed to be in a non-increasing order. SWAT 2022 ...
[37]
[1905.03758] Super-pancyclic hypergraphs and bipartite graphs
May 9, 2019 · We mostly use the language of bipartite graphs, because every bipartite graph is the incidence graph of a multihypergraph. In particular, we ...
[38]
The distribution of the length of the longest path in random acyclic ...
Aug 22, 2024 · Randomly sampling an acyclic orientation on the complete bipartite graph K_{n,k} with parts of size n and k, we investigate the length of the ...
[39]
Hamilton decompositions of regular bipartite tournaments - arXiv
Sep 7, 2022 · A regular bipartite tournament is an orientation of a complete balanced bipartite graph K_{2n,2n} where every vertex has its in- and outdegree ...
[40]
15.2. Graph Algorithms — Programming for Mathematical Applications
To test if a graph is bipartite: We can augment either BFS or DFS when we first discover a new vertex, color it opposited its parents, and for each other ...
[41]
[PDF] Problem Set 5 - csail
Nov 2, 2010 · The time complexity is essentially that of BFS, O(|V | + |E|). Many variations of this algorithm are possible for this problem. For example, one ...
[42]
[PDF] 3.4 Testing Bipartiteness - Washington
Many graph problems become: easier if the underlying graph is bipartite (matching) tractable if the underlying graph is bipartite (independent set). Before ...Missing: citation | Show results with:citation
[43]
[PDF] CSCE 629-601 Analysis of Algorithms Solutions to Assignment #2
The algorithm is a simple modification of DFS without changing complexity. Thus, the algorithm BIPARTITE runs in time O(n + m). (4) Find a cycle in a graph G.
[44]
Finding odd cycle transversals - ScienceDirect.com
Finding odd cycle transversals. Author links open overlay panel. Bruce Reed a ... Reed. Mangoes and blueberries. Combinatorica, 19 (2) (1999), pp. 267-296.
[45]
[PDF] Kernelization by matroids: Odd Cycle Transversal 1 Introduction
May 10, 2013 · We present an FPT algorithm, interpret it as a series of f(k) min-cut queries and finally use matroid tools to encode the graph in kO(1) bits so ...Missing: hard | Show results with:hard
[46]
[PDF] Faster Parameterized Algorithms using Linear Programming
The most notable improvement among these is the new bound for Odd Cycle Transversal - this is the first algorithm which improves upon the dependence on k of the ...<|control11|><|separator|>
[47]
[PDF] FPT Algorithms for st-Separator and Odd Cycle Transversal - DROPS
Again, the problem here is that determining whether a vertex passes through an induced odd cycle is NP-hard (see Lemma 4), therefore we cannot use it as a ...
[48]
[PPT] Linear Programming and Parameterized Algorithms
A ck-OPTLPnO(1)algorithm for Vertex Cover automaticallygivesck-OPTLPnO(1)algorithm for Almost 2-SAT and Odd Cycle Transversal. Canget a 2.32k-OPTLPnO(1) ...
[49]
A Randomized Polynomial Kernel for Odd Cycle Transversal
Dec 18, 2013 · For OCT, the matroid is built to allow us to simulate the computation of the iterative compression step of the algorithm of Reed, Smith, and ...
[50]
On Representatives of Subsets - London Mathematical Society (LMS)
On Representatives of Subsets. P. Hall, P. Hall. King's College Cambridge. Search for more papers by this author. First published: January 1935.
[51]
[PDF] The Hungarian method for the assignment problem
The purpose of this paper is to develop a computational method that uses this duality in a particu- larly effective manner. One interesting aspect of the ...
[52]
[PDF] Hopcroft-Karp-bipartite-matching.pdf - CSE IITM
Abstract. The present paper shows how to construct a maximum matching in a bipartite graph with n vertices and m edges in a number of computation steps ...
[53]
[PDF] paths, trees, and flowers - jack edmonds
A matching in G is a subset of its edges such that no two meet the same vertex. We describe an efficient algorithm for finding in a given graph a match-.Missing: original | Show results with:original
[54]
The Hungarian method for the assignment problem - Kuhn - 1955
The “assignment problem” is the quest for an assignment of persons to jobs so that the sum of the n scores so obtained is as large as possible.
[55]
[1610.04012] Min cost flow on unit capacity networks and convex ...
Oct 13, 2016 · Min cost flow on unit capacity networks and convex cost K-flow are as easy as the assignment problem with All-Min-Cuts algorithm. Authors:Dorit ...
[56]
Hitchcock, F.L. (1941) The Distribution of a Product from Several ...
This research aims to propose an algorithm “Incessant Allocation Method” to obtain an initial basic feasible solution for the transportation problems.
[57]
Solving the generalized transportation problem - ScienceDirect
This paper advocates a mathematical programming approach for solving the classical transportation problem ... Hitchcock, 1941. F.L. Hitchcock. The distribution of ...
[58]
Community Structures in Bipartite Networks: A Dual-Projection ... - NIH
May 16, 2014 · Some instances of bipartite graphs include affiliation networks which link people to committees [2], or Petri nets which are used in computer ...
[59]
[PDF] Community-Affiliation Graph Model for Overlapping Network ...
We propose. Community-Affiliation Graph Model, a model-based commu- nity detection method that builds on bipartite node-community affiliation networks. Our ...
[60]
[PDF] A review of recommendation system research based on bipartite graph
The interaction history between users and items is usually stored and displayed in the form of bipartite graphs. Neural network recommendation based on the user ...Missing: seminal | Show results with:seminal
[61]
betweenness_centrality — NetworkX 3.5 documentation
Values of betweenness are normalized by the maximum possible value which for bipartite graphs is limited by the relative size of the two node sets [1].Missing: communication sender- receiver models
[62]
[PDF] Centrality in affiliation networks
In a bipartite graph nodes can be partitioned into two subsets and all lines are between nodes from different subsets. In the bipartite graph for an affiliation ...
[63]
[0707.1616] Modularity and community detection in bipartite networks
Jul 11, 2007 · The modularity of a network quantifies the extent, relative to a null model network, to which vertices cluster into community groups.Missing: seminal | Show results with:seminal
[64]
The clustering coefficient and community structure of bipartite networks
Sep 30, 2007 · Here we propose a modification of the clustering coefficient given by the fraction of cycles with size four in bipartite networks.
[65]
Bipartite — NetworkX 3.5 documentation
The convention used in NetworkX is to use a node attribute named bipartite with values 0 or 1 to identify the sets each node belongs to. This convention is not ...