Given an indirected graph G = (V;E), a Vertex k-Separator is a subset of the vertex set V such that, when the separator is removed from the graph, the remaining vertices can be partitioned into k subsets that are pairwise edge-disconnected. In this paper we focus on the Balanced Vertex k-Separator Problem, i.e., the problem of finding a minimum cardinality separator such that the sizes of the resulting disconnected subsets are balanced. We present a compact Integer Linear Programming formulation for the problem, and present a polyhedral study of the associated polytope. We also present an Exponential-Size formulation, for which we derive a column generation and a branching scheme. Preliminary computational results are reported comparing the performance of the two formulations on a set of benchmark instances.

Given G = (V;E) an undirected graph and a nonnegative cost function c : E → ℚ, the 2-edge connected spanning subgraph problem (TECSP for short) is to find a two-edge connected subgraph HP = (V; F) of G with minimum cost (i.e., c(F) = Σe∈Fc(e) is minimum). If c(e) > 0 for all e ∈ E then every optimal solution for TECSP is an inclusionwise minimal two-edge connected subgraph. In this paper we provide preliminary results, from a polyhedral point of view, concerning the inclusionwise minimal solutions of TECSP. This problem is clearly NP-Hard. We propose an ILP formulation for the problem and study the associated polytope for the wheels. Morever, we describe some valid inequalities and propose a branch-and-cut algorithm for the problem.

Given a graph $G=(V,E)$ with nonnegative weights on the edges, the maximum induced bipartite subgraph problem (MIBSP) is to find a maximum weight bipartite subgraph $(W,E[W])$ of G. Here $E[W]$ is the edge set induced by W. An edge subset $F\subseteq E$ is called independent if there is an induced bipartite subgraph of G whose edge set contains F. Otherwise, it is called dependent. In this paper we characterize the minimal dependent sets, that is, the dependent sets that are not contained in any other dependent set. Using this, we give an integer linear programming formulation for MIBSP in the natural variable space, based on an associated class of valid inequalities called dependent set inequalities. Moreover, we show that the minimum dependent set problem with nonnegative weights can be reduced to the minimum circuit problem in a directed graph, and can then be solved in polynomial time. This yields a polynomial-time separation algorithm for the dependent set inequalities as well as a polynomial-time cutting plane algorithm for solving the linear relaxation of the problem. We also discuss some polyhedral consequences.