# About having analytic control over any algorithm which finds perfect matchings.

A trivial algorithm to decompose a degree-d (n,n)-bipartite graph into d disjoint perfect matchings is this : direct all the edges from left to right and put capacity one on each of them - then add a super-source and a super sink with appropriately directed edges from them to each of the vertices on their side with capacity one - now run max-flow on it and that picks out a perfect matching - now remove this perfect matching and repeat - continue doing this till you have exhausted all the original edges - this clearly gives you the needed decomposition of the original graph into disjoint perfect matchings.

So one can think of this algorithm as basically returning you a set of d disjoint permutations on the set of n elements.

• Can one say what permutations will be returned? (Will it always return the same set of permutations in the same sequence?)

• Its possible that the answer to the above question is implementation dependent and in that case is there some "standard" implementation for which one can analytically write down the permutations that would be returned as a function of the input graph?

• Or is there any other way to solve this question where one analytically knows the permutations that will be generated?

• @D.W. A $d$-regular balanced bipartite graph is always the union of $d$ perfect matchings. Apply Hall's theorem $d$ times. Apr 5 '15 at 21:34
• @YuvalFilmus, my mistake -- thank you for the correction!
– D.W.
Apr 5 '15 at 21:35
• I'm not quite sure what you mean by "know what permutation will be returned" or "say what permutation will be returned". What would counting as knowing/being able to say what permutations will be returned? If you make the algorithm deterministic (as explained in my answer), then you can successfully predict what permutations will be returned simply by running the algorithm once. Does this count? If it doesn't, can you specify more clearly what you mean by those statements?
– D.W.
Apr 5 '15 at 21:36
• My question is if there is a formula which will analytically tell me one such decomposition given such a graph. Apr 5 '15 at 21:37
• 1. What counts as a formula? If I give you an algorithm and tell you "run it; its output gives you the first decomposition in the sequence", does that count as a formula? Note that if you allow a suitably large class of operators in the formula, then formulas become Turing-complete, so the answer will be trivially yes -- is this what you are looking for? If not, you will need to specify what class of formulas are allowable. 2. What is the context? What is the motivation? Why do you want a formula? How will you use any such formula? Why isn't an algorithm good enough?
– D.W.
Apr 5 '15 at 21:40