AlexArdelean's blog

Maximum Matching in polytime on special kinds of graphs
By AlexArdelean, history, 4 years ago, In English

Hello! I have encountered a problem that boils down to finding maximum matching on a graph that unfortunately is not bipartite. Fortunately though, I observed that the complementary graph is! Is it possible to find maximum matching in polytime on such a graph? I can unfortunately not link the problem.

  • Vote: I like it
  • +28
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 4   Vote: I like it +16 Vote: I do not like it

I solved it myself. If the complementary graph is bipartite the original graph is basically $$${2}$$$ complete subgraphs with some edges between them. Let $$${N}$$$ be the number of nodes. If $$${N}$$$ is odd the answer is $$${{N}{-}{N}{mod}{2}}$$$. If the $$${2}$$$ subgraphs have any edges between them then the answer is $$${N}$$$. Else it depends whether or not both components have odd number of nodes, or both have even number. In the first case the answer is $$${{N}{-}{2}}$$$, in the latter it's $$${N}$$$. Thing is I made a mistake and the original problem doesn't actually boil down to this so this blog is pointless

→ Reply