# Necessary and sufficient conditions for the existence of a combinatorial algorithm for a given problem.

Last semester, I took a combinatorial optimization course where the reference book was Combinatorial Optimization by William J. Cook et al. It was very interesting for me to see the relationship between some great algorithms (like disjktra's shortest path algorithm, edmonds' maximum matching algorithm ...) and LP duality.

My question is about a general framework on constructing combinatorial algorithms based on LP duality.

For a given problem what are the necessary and sufficient conditions for the existence of such algorithms. I think duality gap should be the first necessary condition and to have a totally unimodal matrix could be sufficient.

Maybe the answer is written in that book and I should read it again carefully.

• Before you answer this question you have to decide whether or not you can come up with a sufficiently general framework for defining a combinatorial algorithm. – Andrew D. King Jan 21 '11 at 17:15
• I'm not even quite sure what the question really is. – Suresh Venkat Jan 21 '11 at 18:26
• I have to agree with Suresh; there is no standard definition for "combinatorial algorithm". Do you mean "smells like LP", or do you mean "no games with bits, even in the analysis" (like Dijkstra's algorithm), or something else? Keep in mind that there is no polynomial-time combinatorial algorithm for LP., according to the second definition. – Jeffε Jan 21 '11 at 21:18

## 2 Answers

Some people in combinatorial optimization use the word "combinatorial algorithm" to mean "algorithm without using ellipsoid method (or interior-point methods)." For example, Schrijver's Fulkerson-prize-winning paper has a title "A combinatorial algorithm minimizing submodular functions in strongly polynomial time." The co-winners (Iwata, Fleischer, and Fujishige) also have "A combinatorial strongly polynomial algorithm for minimizing submodular function."

As far as I see the field of combinatorial optimization, people there actually try to give an answer to the posed question, and still struggle. Cunningham's survey "Matching, matroids, and extensions" (Mathematical Programming B91 (2002) 515-542) is a bit old by now, but you can see how generalizations of Edmonds' blossom algorithm and concepts on matroid lead to combinatorial polynomial-time algorithms for other problems. Please note that the field has been advanced since the survey, and good sources are probably some papers from IPCO (Integer Programming and Combinatorial Optimization).

I would like to point out that an big open problem is to find a combinatorial algorithm for the maximum independent set problem for perfect graphs running in strongly polynomial time.

• That was the problem that immediately came to my mind as well. – Andrew D. King Jan 22 '11 at 4:21

With the caveat that I am not quite sure what you're asking about, have you looked at the book on Approximation Algorithms by Vijay Vazirani ? There are two techniques (that are quite related to each other) for using LPs to design combinatorial algorithms. One is of course the primal-dual method that Vijay has propounded for a while, and is explained nicely in the book. Another is the local-ratio method developed by Reuven Bar-Yehuda and others, which it tuns out is also closely related to primal-dual methods. Another perspective that's proven to be useful is the 'pricing' model, which has a more game-theoretic flavor but is also another way of navigating primals and duals in a combinatorial manner.

• The use of primal-dual method can be traced back earlier. For example, cstheory.stackexchange.com/q/3964/2955. – Yoshio Okamoto Jan 21 '11 at 23:03
• yes, I didn't mean to imply anything else: merely that for approximation problems, it's been a successful way of generating combinatorial algorithms. – Suresh Venkat Jan 21 '11 at 23:05