Search Results

This chapter examines the complexity of evaluating graph polynomials, related to the Tutte polynomial, for various classes of matroids. It begins with a short introduction to matroids, complexity, and the Tutte polynomial. The intractability results for the Tutte polynomial are then discussed, including proof of the most often quoted result of classifying the hard points for evaluation of the Tutte polynomial in the graphic case. Contrasting results are presented, giving polynomial time algorithms for restricted classes of input, particularly graphs with bounded tree-width. Finally, the complexity results for various classes of matroids are presented.

This chapter defines and formulates a combinatorial optimization problem, called the winner determination problem, and examines its complexity properties. A range of alternative mathematical programming models including integer linear programming, weighted stable set in graphs, knapsack, and matching that covers variants of the problem related to particular bidding languages is also discussed. The chapter further highlights inapproximability results, and reviews the approximation algorithm, which is a polynomial time algorithm. It concludes that the problem, which is represented as an integer program, is NP-complete and can be tackled by applying three fundamentally different approaches, which it discusses.

The excluded-minor theorem provides one characterization of the class of regular matroids. This chapter presents a different characterization of this class: a decomposition theorem for members of the class, which was proved by Seymour. This theorem has a number of important consequences, one of which is that it leads to a polynomial-time algorithm to test whether a given real matrix is totally unimodular.

This chapter proves the main result on the computation of Galois representations. It provides a detailed description of the algorithm and a rigorous proof of the complexity. It first combines the results of chapters 11 and 12 in order to work out the strategy of Chapter 3. This gives the main result, Theorem 14.1.1: a deterministic polynomial time algorithm, based on computations with complex numbers. The crucial transition from approximations to exact values is done, and the proof of Theorem 14.1.1 is finished later in the chapter. The chapter then replaces the complex computations with the computations over finite fields from Chapter 13, and gives a probabilistic (Las Vegas type) polynomial time variant of the algorithm in Theorem 14.1.1.