2
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • $\begingroup$ @D.W. A $d$-regular balanced bipartite graph is always the union of $d$ perfect matchings. Apply Hall's theorem $d$ times. $\endgroup$
    – Yuval Filmus
    Apr 5, 2015 at 21:34
  • $\begingroup$ @YuvalFilmus, my mistake -- thank you for the correction! $\endgroup$
    – D.W. ♦
    Apr 5, 2015 at 21:35
  • $\begingroup$ 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? $\endgroup$
    – D.W. ♦
    Apr 5, 2015 at 21:36
  • $\begingroup$ My question is if there is a formula which will analytically tell me one such decomposition given such a graph. $\endgroup$
    – user6818
    Apr 5, 2015 at 21:37
  • $\begingroup$ 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? $\endgroup$
    – D.W. ♦
    Apr 5, 2015 at 21:40

1 Answer 1

Reset to default
1
$\begingroup$

Will it always return the same set of permutations in the same sequence?

No. If you call the algorithm twice with the same input, it's not necessarily guaranteed to give the same output both times. Many standard max-flow algorithms are non-deterministic, so there is no such guarantee. For instance, consider any algorithm based on selecting augmenting paths. If at any iteration there are multiple augmenting paths that would be acceptable, the max-flow algorithm will typically select one of them arbitrarily. Consequently, it is not deterministic.

However, any such algorithm can easily be made to be deterministic by simply specifying a deterministic rule for resolving all non-deterministic choices. For instance, whenever there are multiple acceptable choices, you can sort all of the acceptable options using some pre-specified order (say, lexicographic order) and always take the first.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.