A new algorithm for the intersection of a line with the independent set polytope of a matroid

AbstractWe present a new algorithm for the problem of determining the intersection of a half-line Δu={x|x=λu,λ⩾0,u∈R+n} with the independent set polytope of a matroid. We show it can also be used to compute the strength of a graph and the corresponding partition using successive contractions. The algorithm is based on the maximization of successive linear forms on the boundary of the polytope. We prove it is a polynomial algorithm in probability with average number of iterations in O(n5). Finally, numerical tests reveal that it should only require O(n2) iterations in practice