Consider the family of graphs without k node-disjoint odd cycles, where k is a constant. Determining the complexity of the stable set problem for such graphs G is a long-standing problem. We give a polynomial-time algorithm for the case that G can be further embedded in a (possibly nonorientable) surface of bounded genus. Moreover, we obtain polynomial-size extended formulations for the respective stable set polytopes. To this end, we show that 2-sided odd cycles satisfy the Erdős-Pósa property in graphs embedded in a fixed surface. This extends the fact that odd cycles satisfy the Erdős-Pósa property in graphs embedded in a fixed orientable surface (Kawarabayashi & Nakamoto, 2007). Eventually, our findings allow us to reduce the original problem to the problem of finding a minimum-cost nonnegative integer circulation of a certain homology class, which turns out to be efficiently solvable in our case.

The cut dominant of a graph is the unbounded polyhedron whose points are all those that dominate some convex combination of proper cuts. Minimizing a nonnegative linear function over the cut dominant is equivalent to finding a minimum weight cut in the graph. We give a forbidden-minor characterization of the graphs whose cut dominant can be defined by inequalities with integer coefficients and right-hand side at most 2. Our result is related to the forbidden-minor characterization of TSP-perfect graphs by Fonlupt and Naddef [Math. Program, 53 (1992), pp. 147--172]. We show how to derive each of the results from the other. Furthermore, we establish general properties of forbidden minors for right-hand sides larger than 2.

Given a subset $S$ of $\mathbb{R}^d$, the Helly number $h(S)$ is the largest size of an inclusionwise minimal family of convex sets whose intersection is disjoint from $S$. A convex set is $S$-free if its interior contains no point of $S$. The parameter $f(S)$ is the largest number of maximal faces in an inclusionwise maximal $S$-free convex set. We study the relation between the parameters $h(S)$ and $f(S)$. Our main result is that $h(S)\le (d+1)f(S)$ for every nonempty proper closed subset $S$ of $\mathbb{R}^d$. We also study the Helly number of the Cartesian product of two discrete sets.

We introduce the reverse Chvátal--Gomory rank $r^*(P)$ of an integral polyhedron $P$, defined as the supremum of the Chvátal--Gomory ranks of all rational polyhedra whose integer hull is $P$. A well-known example in dimension two shows that there exist integral polytopes $P$ with $r^*(P)=+\infty$. We provide a geometric characterization of polyhedra with this property in every dimension, and investigate upper bounds on $r^*(P)$ when this value is finite.

Given an integral polyhedron $P\subseteq\mathbb{R}^n$ and a rational polyhedron $Q\subseteq\mathbb{R}^n$ containing the same integer points as $P$, we investigate how many iterations of the Chvátal--Gomory closure operator have to be performed on $Q$ to obtain a polyhedron contained in the affine hull of $P$. We show that if $P$ contains an integer point in its relative interior, then such a number of iterations can be bounded by a function depending only on $n$. On the other hand, we prove that if $P$ is not full-dimensional and does not contain any integer point in its relative interior, then no finite bound on the number of iterations exists.

We show that maximal S-free convex sets are polyhedra when S is the set of integral points in some rational polyhedron of $\mathbb{R}^n$. This result extends a theorem of Lovász characterizing maximal lattice-free convex sets. Our theorem has implications in integer programming. In particular, we show that maximal S-free convex sets are in one-to-one correspondence with minimal inequalities.

We determine the structure of a class of graphs that do not contain the complete graph on five vertices as a “signed minor.” The result says that each graph in this class can be decomposed into elementary building blocks in which maximum packings by odd circuits can be found by flow or matching techniques. This allows us to actually find a largest collection of pairwise edge disjoint odd circuits in polynomial time (for general graphs this is NP‐hard). Furthermore it provides an algorithm to test membership of our class of graphs.

We consider the mixing set with flows: $s+x_t \geq b_t, x_t \leq y_t {\rm for} 1 \leq t \leq n; s \in \R^1_+, x \in \R^n_+, y \in \Z^n_+.$ It models a “flow version” of the basic mixing set introduced and studied by Günlük and Pochet [Math. Program., 90 (2001), pp. 429–457], as well as the most simple stochastic lot‐sizing problem with recourse. More generally it is a relaxation of certain mixed integer sets that arise in the study of production planning problems. We study the polyhedron defined as the convex hull of the above set. Specifically we provide an inequality description, and we also characterize its vertices and rays.

In a graph G, an odd hole is an induced odd cycle of length at least 5. A clique of G is a set of pairwise adjacent vertices. In this paper we consider the class ${\cal C}_k$ of graphs whose cliques have a size bounded by a constant k. Given a graph G in ${\cal C}_k$, we show how to recognize in polynomial time whether G contains an odd hole.

A hole in a graph is a chordless cycle of length greater than three. In this paper we present a decomposition theorem for graphs that contain no even hole. This theorem yields a polytime algorithm to recognize whether a graph contains an even hole.

In propositional logic, several problems, such as satisfiability, MAX SAT and logical inference, can be formulated as integer programs. In this paper, we consider sets of clauses for which the corresponding integer programs can be solved as linear programs. We prove that balanced sets of clauses have this property.

Several problems of propositional logic, such as satisfiability, MAXSAT and logical inference, can be formulated as integer programs. The authors consider sets of clauses for which these integer programs can be solved as linear programs. They prove that balanced sets of clauses have this property.>

Abstract The matching problem in bipartite graphs can be solved by an elegant primal‐dual algorithm. The purpose of this paper is to introduce concepts which make it possible to generalize this algorithm to some classes of hypergraphs. We illustrate the approach by providing a polynomial primal‐dual algorithm for the matching problem in hypergraphs without odd cycles.