Packing triangles in tournaments

Abstract

A rich variety of combinatorial optimization problems can be naturally formu- lated as integer linear programs. Linear programs admit a polynomial algorithm known as ellipsoidal algorithm. In contrast, integer programs are generally N P - hard, which means there is no polynomial algorithm for them unless P = N P . An integer program is equivalent to its linear programming relaxation if the corresponding polyhedron is integral. The notion of total dual integrality in- troduced by Edmonds and Giles in 1977 has proved to be a powerful tool for identifying such integrality. One major task of polyhedral combinatorics is to establish total dual integrality for linear systems arose from combinatorial struc- tures, which not only means ellipsoidal algorithm is applicable but also reveals elegant min-max relation. In this thesis, we consider the triangle packing and covering problem in tournaments. The main goal is to give structural characterization for all tour- naments T such that the linear system Ax ≥ 1, x ≥ 0 is total dual 1/3-integral (1/3-TDI), where A is the vertex-triangle incidence matrix of T . In other words, they are tournaments T = (V, A) satisfying the following min-max relation: for any nonnegative integral weight function w defined on V , the maximum size of a collection C of triangles (directed, with repetition allowed) in T such that each vertex v is used at most 3w(v) times by elements in C equals the minimum w-weight of a collection U of vertices (with repetition allowed) in T such that each triangle meets U at least three times. Although this min-max relation is innocent-looking, there are few results concerning 1/3-TDI system in literature. In this thesis we develope a powerful tool in establishing 1/k-TDI system, which reduce the min-max relation to a property with transparent combinatorial nature. The main body of our proof consists of a thorough investigation towards the collections of triangles in a family of tournaments. Such method can be regarded as a combination of the structure- driven approach and linear algebraic approach and is perhaps of more interest. Furthermore, we believe that a natural generalization of our proof can be further applied to other similar packing and covering problems.