Some polyhedral results in combinatorial optimization

Abstract

Many combinatorial optimization problems can be conceived of as optimizing a linear function over a polyhedron. Investigating properties of the associated polyhedron has been evidenced to be a powerful schema for solving combinatorial optimization problems, especially for characterizing min-max relations. Three different topics in combinatorial optimization are explored in this thesis, which fall within a unified characterization: integrality of polyhedra.

Various min-max relations in combinatorial optimization can be formulated into packing and covering problems under the framework of hypergraphs. Packing and covering problems regarding the blocking pair of cycles and feedback sets are studied in this thesis. A min-max relation is established in reducible flow graphs, of which the proof yields a combinatorial algorithm for finding a maximum feedback set packing. The necessary and sufficient condition for integrality of the covering polyhedron of semicomplete digraphs is presented, and min-max relations are conjectured under the same condition.

The stable matching problem is of great theoretical interest and practical value in both mathematics and economics. The 2012 Nobel prize in economics being awarded jointly to Roth and Shapley “for the theory of stable allocations and the practice of market design” speaks for its importance. In this thesis, Rothblum’s description of the stable matching polyhedron is generalized to preference systems defined on multigraphs. Moreover, describing stable matchings with a hybrid linear system, i.e., Edmonds-Rothblum system, is discussed.

Another investigation concerns kernels, which contain stable matchings as a special case. Originally being a central concept in cooperative games, kernels have turned out to be applicable in various fields such as graph theory, logic and combinatorics. In this thesis, attempts for giving kernels a polyhedral description in two branches of claw-free graphs, namely line graphs and claw-free Berge graphs, are made. Obstructions are detected and polyhedral descriptions are confirmed for kernels in {claw, clique-cutset}-free Berge graphs.