A connected matching in a graph G consists of a set of pairwise disjoint edges whose covered vertices induce a connected subgraph of G. While finding a connected matching of maximum cardinality is a well-solved problem, it is NP-hard to determine an optimal connected matching in an edge-weighted graph, even in the planar bipartite case. We present two mixed integer programming formulations and a sophisticated branch-and-cut scheme to find weighted connected matchings in general graphs. The formulations explore different polyhedra associated to this problem, including strong valid inequalities both from the matching polytope and from the connected subgraph polytope. We conjecture that one attains a tight approximation of the convex hull of connected matchings using our strongest formulation, and report encouraging computational results over DIMACS Implementation Challenge benchmark instances. The source code of the complete implementation is also made available.

Given an undirected graph G=(V,E) and a positive integer k∈1,…,|V|, we initiate the combinatorial study of stable sets of cardinality exactly k in G. Our aim is to instigate the polyhedral investigation of the convex hull of fixed cardinality stable sets, inspired by the rich theory on the classical structure of stable sets. We introduce a large class of valid inequalities to the natural integer programming formulation of the problem. We also present simple combinatorial relaxations based on computing maximum weighted matchings, which yield dual bounds towards finding minimum-weight fixed cardinality stable sets, and particular cases which are solvable in polynomial time.

Graph Theory provides a set of powerful tools (both theorems and algorithms) for problem modeling and solving in numerous domains. Though there are several libraries implementing graph algorithms and targeting different platforms and users, few of those offer parallel implementations. To the best of our knowledge, there is a particular need for an easier to use and extend library, specifically designed to exploit the multicore architecture trend for high performance parallelism. In this paper we describe Magical, a new OpenMP-based C++ multicore graph library. Our focus is to provide an implementation of graph algorithms which is designed for multicore architectures, by means of an easy to use application programming interface. We describe the library design and evaluate its performance by means of a case study concerning a shortest-paths problem.