Composition of Graphs and the Triangle-Free Subgraph Polytope

In this paper, we study a composition (decomposition) technique for the triangle-free subgraph polytope in graphs which are decomposable by means of 3-sums satisfying some property. If a graph G decomposes into two graphs G ₁ and G ₂, we show that the triangle-free subgraph polytope of G can be described from two linear systems related to G ₁ and G ₂. This gives a way to characterize this polytope on graphs that can be recursively decomposed. This also gives a procedure to derive new facets for this polytope. We also show that, if the systems associated with G ₁ and G ₂ are TDI, then the system characterizing the polytope for G is TDI. This generalizes previous results in R. Euler and A.R. Mahjoub (Journal of Comb. Theory series B, vol. 53, no. 2, pp. 235–259, 1991) and A.R. Mahjoub (Discrete Applied Math., vol. 62, pp. 209–219, 1995).     

The 2-Edge-Connected Subgraph Polyhedron

We study the polyhedron P(G) defined by the convex hull of 2-edge-connected subgraphs of G where multiple copies of edges may be chosen. We show that each vertex of P(G) is also a vertex of the LP relaxation. Given the close relationship with the Graphical Traveling Salesman problem (GTSP), we examine how polyhedral results for GTSP can be modified and applied to P(G). We characterize graphs for which P(G) is integral and study how this relates to a similar result for GTSP. In addition, we show how one can modify some classes of valid inequalities for GTSP and produce new valid inequalities and facets for P(G).     

Solution Structure of Some Inverse Combinatorial Optimization Problems

In this paper we consider some inverse combinatorial optimization problems, that is, for a given set of feasible solutions of an optimization problem, we wish to know: under what weight vectors (or capacity vectors) will these feasible solutions become optimal solutions? We analysed shortest path problem, minimum cut problem, minimum spanning tree problem and maximum-weight matching problem, and found that in each of these cases, the solution set of the inverse problem is charaterized by solving another combinatorial optimization problem. The main tool in our approach is Fulkerson's theory of blocking and anti-blocking polyhedra with some necessary revisions.     

On Some Polyhedra Covering Problems

Let P ⁰, P ¹ be two simple polyhedra and let P ² be a convex polyhedron in E ³. Polyhedron P ⁰ is said to be covered by polyhedra P ¹ and P ² if every point of P ⁰ is a point of P ¹ P ². The following polyhedron covering problem is studied: given the positions of P ⁰, P ¹, and P ² in the xy-coordinate system, determine whether or not P ⁰ can be covered by P ¹ P ² via translation and rotation of P ¹ and P ²; furthermore, find the exact covering positions of these polyhedra if such a cover exists. It is shown in this paper that if only translation is allowed, then the covering problem of P ⁰, P ¹ and P ² can be solved in O(m ² n ²(m + n)l)) polynomial time, where m, n, and l are the sizes of P ⁰, P ¹, and P ², respectively. The method can be easily extended to the problem in E ^d for any fixed d > 3.