On the partial order polytope of a digraph

We introduce the partial order polytope of a digraphD, defined as the convex hull of the incidence vectors of all transitive acyclic arc sets ofD. For this polytope we prove some classes of inequalities to be facet-defining and show that there is a polynomial separation algorithm for each of these classes. The results imply a polynomial separation algorithm for a class of valid inequalities of the clique partitioning polytope that includes the two-chorded odd cycle inequalities. The polyhedral results concerning the partial order polytope are of interest since a cutting plane based algorithm to solve the maximum weighted transitive acyclic subdigraph problem can be used to solve the maximum weighted acyclic subdigraph problem, the maximum weighted linear ordering problem and a flexible manufacturing problem. For the acyclic subdigraph polytope we show that the separation of simplet-reinforcedk-fence-inequalities is -complete.     

Facets of the balanced (acyclic) induced subgraph polytope

A signed graph is a graph whose edges are labelled positive or negative. A signed graph is said to be balanced if the set of negative edges form a cut. The balanced induced subgraph polytopeP(G) of a graphG is the convex hull of the incidence vectors of all node sets that induce balanced subgraphs ofG. In this paper we exhibit various (rank) facet defining inequalities. We describe several methods with which new facet defining inequalities ofP(G) can be constructed from known ones. Finding a maximum weighted balanced induced subgraph of a series parallel graph is a polynomial problem. We show that for this class of graphsP(G) may have complicated facet defining inequalities. We derive analogous results for the polytope of acyclic induced subgraphs.Research supported in part by the Natural Sciences and Engineering Research Council of Canada; the second author has also been supported by C.P. Rail.     

Polyhedral studies on the convex recoloring problem

A coloring of the vertices of a graph G is convex if, for each assigned color d, the vertices with color d induce a connected subgraph of G. We address the convex recoloring problem, defined as follows. Given a graph G and a coloring of its vertices, recolor a minimum number of vertices of G, so that the resulting coloring is convex. This problem is known to be NP-hard even when G is a path. We show an integer programming formulation for the weighted version of this problem on arbitrary graphs, and then specialize it for trees. We study the facial structure of the polytope defined as the convex hull of the integer points satisfying the restrictions of the proposed ILP formulation, present several classes of facet-defining inequalities and discuss separation algorithms.     

The node-edge weighted 2-edge connected subgraph problem: Linear relaxation, facets and separation

Let G=(V,E) be a undirected k-edge connected graph with weights c_e on edges and w_v on nodes. The minimum 2-edge connected subgraph problem, 2ECSP for short, is to find a 2-edge connected subgraph of G, of minimum total weight. The 2ECSP generalizes the well-known Steiner 2-edge connected subgraph problem. In this paper we study the convex hull of the incidence vectors corresponding to feasible solutions of 2ECSP. First, a natural integer programming formulation is given and it is shown that its linear relaxation is not sufficient to describe the polytope associated with 2ECSP even when G is series-parallel. Then, we introduce two families of new valid inequalities and we give sufficient conditions for them to be facet-defining. Later, we concentrate on the separation problem. We find polynomial time algorithms to solve the separation of important subclasses of the introduced inequalities, concluding that the separation of the new inequalities, when G is series-parallel, is polynomially solvable.     

The perfectly Matchable Subgraph Polytope of an arbitrary graph

The Perfectly Matchable Subgraph Polytope of a graphG=(V, E), denoted byPMS(G), is the convex hull of the incidence vectors of thoseXV which induce a subgraph having a perfect matching. We describe a linear system whose solution set isPMS(G), for a general (nonbipartite) graphG. We show how it can be derived via a projection technique from Edmonds' characterization of the matching polytope ofG. We also show that this system can be deduced from the earlier bipartite case [2], by using the Edmonds-Gallai structure theorem. Finally, we characterize which inequalities are facet inducing forPMS(G), and hence essential.     

Rank of maximum matchings in a graph

The matching polytope is the convex hull of the incidence vectors of all (not necessarily perfect) matchings of a graphG. We consider here the problem of computing the dimension of the face of this polytope which contains the maximum cardinality matchings ofG and give a good characterization of this quantity, in terms of the cyclomatic number of the graph and families of odd subsets of the nodes which are always nearly perfectly matched by every maximum matching.This is equivalent to finding a maximum number of linearly independent representative vectors of maximum matchings ofG; the size of such a set is called thematching rank ofG. We also give in the last section a way of computing that rank independently of those parameters.Note that this gives us a good lower bound on the number of those matchings.     

Path-closed sets

Given a digraphG = (V, E), call a node setT ⊆V path-closed ifv, v′ εT andw εV is on a path fromv tov′ impliesw εT. IfG is the comparability graph of a posetP, the path-closed sets ofG are the convex sets ofP. We characterize the convex hull of (the incidence vectors of) all path-closed sets ofG and its antiblocking polyhedron inR ^v , using lattice polyhedra, and give a minmax theorem on partitioning a given subset ofV into path-closed sets. We then derive good algorithms for the linear programs associated to the convex hull, solving the problem of finding a path-closed set of maximum weight sum, and prove another min-max result closely resembling Dilworth’s theorem.     

The convex hull of degree sequences of signed graphs

As shown in [D. Hoffman, H. Jordon, Signed graph factors and degree sequences, J. Graph Theory 52 (2006) 27-36], the degree sequences of signed graphs can be characterized by a system of linear inequalities. The set of all n-tuples satisfying this system of linear inequalities is a polytope P_n. In this paper, we show that P_n is the convex hull of the set of degree sequences of signed graphs of order n. We also determine many properties of P_n, including a characterization of its vertices. The convex hull of imbalance sequences of digraphs is also investigated using the characterization given in [D. Mubayi, T.G. Will, D.B. West, Realizing degree imbalances of directed graphs, Discrete Math. 239 (2001) 147-153].     

On separation and adjacency problems for perfectly matchable subgraph polytopes of a graph

A subgraph F of graph G is called a perfectly matchable subgraph if F contains a set of independent edges convering all the vertices in F. The convex hull of the incidence vectors of perfectly matchable subgraphs of G is a 0–1 polytope. We characterize the adjacency of vertices on such polytopes. We also show that when G is bipartite, the separation problem for such polytones can be solved by maximum flow algorithms.     

A polyhedral approach to the alldifferent system

This paper examines the facial structure of the convex hull of integer vectors satisfying a system of alldifferent predicates, also called an alldifferent system. The underlying analysis is based on a property, called inclusion, pertinent to such a system. For the alldifferent systems for which this property holds, we present two families of facet-defining inequalities, establish that they completely describe the convex hull and show that they can be separated in polynomial time. Consequently, the inclusion property characterises a group of alldifferent systems for which the linear optimization problem (i.e. the problem of optimizing a linear function over that system) can be solved in polynomial time. Furthermore, we establish that, for systems with three predicates, the inclusion property is also a necessary condition for the convex hull to be described by those two families of inequalities. For the alldifferent systems that do not possess that property, we establish another family of facet-defining inequalities and an accompanied polynomial-time separation algorithm. All the separation algorithms are incorporated within a cutting-plane scheme and computational experience on a set of randomly generated instances is reported. In concluding, we show that the pertinence of the inclusion property can be decided in polynomial time.     

On the structure of the monotone asymmetric travelling salesman polytope I: hypohamiltonian facets

The monotone asymmetric travelling salesman polytope P?ⁿ_T is defined to be the convex hull of the incidence vectors of all hamiltonian circuits and all subsets of these in a complete diagraph of order n. We prove that certain hypohamiltonian diagraphs G=(V,E), i.e. diagraphs which are not hamiltonian but such that G–υ is hamiltonian for all υ?V, induce facets x(E)?n–1 of P?ⁿ_T. This result indicates that P?ⁿ_T has very complicated facets and that it is very unlikely that an explicit complete characterization of P?ⁿ_T can ever be given.     

Facet-inducing web and antiweb inequalities for the graph coloring polytope

For a graph G and its complement , we define the graph coloring polytope P(G) to be the convex hull of the incidence vectors of star partitions of . We examine inequalities whose support graphs are webs and antiwebs appearing as induced subgraphs in G. We show that for an antiweb in G the corresponding inequality is facet-inducing for P(G) if and only if is critical with respect to vertex colorings. An analogous result is also proved for the web inequalities.     

The graph of perfect matching polytope and an extreme problem

For graph G, its perfect matching polytope Poly(G) is the convex hull of incidence vectors of perfect matchings of G. The graph corresponding to the skeleton of Poly(G) is called the perfect matching graph of G, and denoted by PM(G). It is known that PM(G) is either a hypercube or hamilton connected [D.J. Naddef, W.R. Pulleyblank, Hamiltonicity and combinatorial polyhedra, J. Combin. Theory Ser. B 31 (1981) 297-312; D.J. Naddef, W.R. Pulleyblank, Hamiltonicity in (0-1)-polytope, J. Combin. Theory Ser. B 37 (1984) 41-52]. In this paper, we give a sharp upper bound of the number of lines for the graphs G whose PM(G) is bipartite in terms of sizes of elementary components of G and the order of G, respectively. Moreover, the corresponding extremal graphs are constructed.     

Edge covering coloring of nearly bipartite graphs

LetG be a simple graph with vertex setV(G) and edge setE(G). A subsetS ofE(G) is called an edge cover ofG if the subgraph induced byS is a spanning subgraph ofG. The maximum number of edge covers which form a partition ofE(G) is called edge covering chromatic number ofG, denoted by χ′_c(G). It known that for any graphG with minimum degreeδ,δ -1 ≤χ′_c(G) ≤δ. If χ′_c(G) =δ, thenG is called a graph of CI class, otherwiseG is called a graph of CII class. It is easy to prove that the problem of deciding whether a given graph is of CI class or CII class is NP-complete. In this paper, we consider the classification of nearly bipartite graph and give some sufficient conditions for a nearly bipartite graph to be of CI class.     

The cut cone III: On the role of triangle facets

The cut polytopeP _n is the convex hull of the incidence vectors of the cuts (i.e. complete bipartite subgraphs) of the complete graph onn nodes. A well known class of facets ofP _n arises from the triangle inequalities:x _ij +x _ik +x _jk ≤ 2 andx _ij -x _ik -x _jk ≤ 0 for 1 ≤i,j, k ≤n. Hence, the metric polytope M_n, defined as the solution set of the triangle inequalities, is a relaxation ofP _n . We consider several properties of geometric type for P_n, in particular, concerning its position withinM _n . Strengthening the known fact ([3]) thatP _n has diameter 1, we show that any set ofk cuts,k ≤ log₂ n, satisfying some additional assumption, determines a simplicial face ofM _n and thus, also, ofP _n . In particular, the collection of low dimension faces ofP _n is contained in that ofM _n . Among a large subclass of the facets ofP _n , the triangle facets are the closest ones to the barycentrum of P_n and we conjecture that this result holds in general. The lattice generated by all even cuts (corresponding to bipartitions of the nodes into sets of even cardinality) is characterized and some additional questions on the links between general facets ofP _n and its triangle facets are mentioned.