Editing Bipartite graph (section)

==Algorithms==

===Testing bipartiteness===
It is possible to test whether a graph is bipartite, and to return either a two-coloring (if it is bipartite) or an odd cycle (if it is not) in [[linear time]], using [[depth-first search]] (DFS). The main idea is to assign to each vertex the color that differs from the color of its parent in the DFS forest, assigning colors in a [[preorder traversal]] of the depth-first-search forest. This will necessarily provide a two-coloring of the [[spanning forest]] consisting of the edges connecting vertices to their parents, but it may not properly color some of the non-forest edges. In a DFS forest, one of the two endpoints of every non-forest edge is an ancestor of the other endpoint, and when the depth first search discovers an edge of this type it should check that these two vertices have different colors. If they do not, then the path in the forest from ancestor to descendant, together with the miscolored edge, form an odd cycle, which is returned from the algorithm together with the result that the graph is not bipartite. However, if the algorithm terminates without detecting an odd cycle of this type, then every edge must be properly colored, and the algorithm returns the coloring together with the result that the graph is bipartite.<ref>{{citation
 | last = Sedgewick | first = Robert | author-link = Robert Sedgewick (computer scientist)
 | edition = 3rd
 | pages = 109–111
 | publisher = Addison Wesley
 | title = Algorithms in Java, Part 5: Graph Algorithms
 | year = 2004}}.</ref>

Alternatively, a similar procedure may be used with [[breadth-first search]] in place of DFS. Again, each node is given the opposite color to its parent in the search forest, in breadth-first order. If, when a vertex is colored, there exists an edge connecting it to a previously-colored vertex with the same color, then this edge together with the paths in the breadth-first search forest connecting its two endpoints to their [[lowest common ancestor]] forms an odd cycle. If the algorithm terminates without finding an odd cycle in this way, then it must have found a proper coloring, and can safely conclude that the graph is bipartite.<ref>{{citation
 | last1 = Kleinberg | first1 = Jon | author1-link = Jon Kleinberg
 | last2 = Tardos | first2 = Éva | author2-link = Éva Tardos
 | pages = 94–97
 | publisher = Addison Wesley
 | title = Algorithm Design
 | year = 2006}}.</ref>

For the [[intersection graph]]s of <math>n</math> [[line segment]]s or other simple shapes in the [[Euclidean plane]], it is possible to test whether the graph is bipartite and return either a two-coloring or an odd cycle in time <math>O(n\log n)</math>, even though the graph itself may have up to <math>O(n^2)</math> edges.<ref>
{{citation
 | last = Eppstein | first = David | author-link = David Eppstein
 | arxiv = cs.CG/0307023
 | doi = 10.1145/1497290.1497291
 | issue = 2
 | journal = ACM Transactions on Algorithms
 | mr = 2561751
 | page = Art. 15
 | title = Testing bipartiteness of geometric intersection graphs
 | volume = 5
 | year = 2009
 | s2cid = 60496
}}.</ref>

===Odd cycle transversal===
{{main|Odd cycle transversal}}
[[File:Odd Cycle Transversal of size 2.png|thumb|A graph with an odd cycle transversal of size 2: removing the two blue bottom vertices leaves a bipartite graph.]]
[[Odd cycle transversal]] is an [[NP-complete]] [[algorithm]]ic problem that asks, given a graph ''G'' = (''V'',''E'') and a number ''k'', whether there exists a set of&nbsp;''k'' vertices whose removal from ''G'' would cause the resulting graph to be bipartite.<ref name=yannakakis1978node>{{citation
 | last = Yannakakis | first = Mihalis | author-link = Mihalis Yannakakis
 | contribution = Node-and edge-deletion NP-complete problems
 | doi = 10.1145/800133.804355
 | pages = 253–264
 | title = Proceedings of the 10th ACM Symposium on Theory of Computing (STOC '78)
 | year = 1978
 | title-link = Symposium on Theory of Computing | s2cid = 363248
| doi-access = free
 }}</ref> The problem is [[Parameterized complexity|fixed-parameter tractable]], meaning that there is an algorithm whose running time can be bounded by a polynomial function of the size of the graph multiplied by a larger function of ''k''.<ref name=reed2004finding>{{citation
 | last1 = Reed | first1 = Bruce | author1-link = Bruce Reed (mathematician)
 | last2 = Smith | first2 = Kaleigh
 | last3 = Vetta | first3 = Adrian
 | doi = 10.1016/j.orl.2003.10.009
 | issue = 4
 | journal = Operations Research Letters
 | mr = 2057781
 | pages = 299–301
 | title = Finding odd cycle transversals
 | volume = 32
 | year = 2004| citeseerx = 10.1.1.112.6357
}}.</ref> The name ''odd cycle transversal'' comes from the fact that a graph is bipartite if and only if it has no odd [[Cycle (graph theory)|cycles]].  Hence, to delete vertices from a graph in order to obtain a bipartite graph, one needs to "hit all odd cycle", or find a so-called odd cycle [[Transversal (combinatorics)|transversal]] set.  In the illustration, every odd cycle in the graph contains the blue (the bottommost) vertices, so removing those vertices kills all odd cycles and leaves a bipartite graph.

The ''edge bipartization'' problem is the algorithmic problem of deleting as few edges as possible to make a graph bipartite and is also an important problem in graph modification algorithmics. This problem is also [[fixed-parameter tractable]], and can be solved in time <math display="inline">O\left(2^k m^2\right)</math>,<ref name=guo2006compression>{{citation
 | last1 = Guo | first1 = Jiong
 | last2 = Gramm | first2 = Jens
 | last3 = Hüffner | first3 = Falk
 | last4 = Niedermeier | first4 = Rolf
 | last5 = Wernicke | first5 = Sebastian
 | doi = 10.1016/j.jcss.2006.02.001
 | journal =  Journal of Computer and System Sciences
 | volume = 72
 | issue = 8
 | pages = 1386–1396
 | title = Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
 | year = 2006
| doi-access = free
 }}</ref> where ''k'' is the number of edges to delete and ''m'' is the number of edges in the input graph.

===Matching===
{{main|Matching (graph theory)}}
A [[Matching (graph theory)|matching]] in a graph is a subset of its edges, no two of which share an endpoint. [[Polynomial time]] algorithms are known for many algorithmic problems on matchings, including [[maximum matching]] (finding a matching that uses as many edges as possible), [[maximum weight matching]], and [[stable marriage]].<ref>{{citation
 | last1 = Ahuja | first1 = Ravindra K.
 | last2 = Magnanti | first2 = Thomas L.
 | last3 = Orlin | first3 = James B.
 | contribution = 12. Assignments and Matchings
 | pages = 461–509
 | publisher = Prentice Hall
 | title = Network Flows: Theory, Algorithms, and Applications
 | year = 1993}}.</ref> In many cases, matching problems are simpler to solve on bipartite graphs than on non-bipartite graphs,<ref>{{harvtxt|Ahuja|Magnanti|Orlin|1993}}, p. 463: "Nonbipartite matching problems are more difficult to solve because they do not reduce to standard network flow problems."</ref> and many matching algorithms such as the [[Hopcroft–Karp algorithm]] for maximum cardinality matching<ref>{{citation|first1=John E.|last1=Hopcroft|author1-link=John Hopcroft|first2=Richard M.|last2=Karp|author2-link=Richard Karp|title=An ''n''<sup>5/2</sup> algorithm for maximum matchings in bipartite graphs|journal=SIAM Journal on Computing|volume=2|issue=4|pages=225–231|year=1973|doi=10.1137/0202019}}.</ref> work correctly only on bipartite inputs.

As a simple example, suppose that a set <math>P</math> of people are all seeking jobs from among a set <math>J</math> of jobs, with not all people suitable for all jobs. This situation can be modeled as a bipartite graph <math>(P,J,E)</math> where an edge connects each job-seeker with each suitable job.<ref>{{harvtxt|Ahuja|Magnanti|Orlin|1993}}, Application 12.1 Bipartite Personnel Assignment, pp. 463–464.</ref> A [[perfect matching]] describes a way of simultaneously satisfying all job-seekers and filling all jobs; [[Hall's marriage theorem]] provides a characterization of the bipartite graphs which allow perfect matchings. The [[National Resident Matching Program]] applies graph matching methods to solve this problem for [[Medical education in the United States|U.S. medical student]] job-seekers and [[Residency (medicine)|hospital residency]] jobs.<ref>{{citation
 |last         = Robinson
 |first        = Sara
 |date         = April 2003
 |issue        = 3
 |journal      = SIAM News
 |page         = 36
 |title        = Are Medical Students Meeting Their (Best Possible) Match?
 |url          = http://www.siam.org/pdf/news/305.pdf
 |access-date  = 2012-08-27
 |archive-url  = https://web.archive.org/web/20161118115832/http://www.siam.org/pdf/news/305.pdf
 |archive-date = 2016-11-18
 |url-status     = dead
}}.</ref>

The [[Dulmage–Mendelsohn decomposition]] is a structural decomposition of bipartite graphs that is useful in finding maximum matchings.<ref>{{harvtxt|Dulmage|Mendelsohn|1958}}.</ref>