Fixed cardinality stable sets

Speaker: Phillippe Samer

Title: Fixed cardinality stable sets

Abstract:  

Given a graph G=(V,E) and a set of conflicting edge pairs C ⊆ E×E, a conflict-free spanning tree in G is a set of edges T ⊆ E inducing a spanning tree in G, such that for each (e,f) ∈ C, at most one of the edges e and f is in T. Motivated by the NP-hard problem of finding conflict-free spanning trees of minimum weight, we study fixed cardinality stable sets (or independent sets, i.e. a subset of pairwise non-adjacent vertices) of minimum weight. We plan to indicate how we're approaching the problem from the standpoint of polyhedral combinatorics and integer linear programming (ILP). We introduce an exponentially-sized class of valid inequalities, whose separation problem turns out to be interesting in its own right.

For registration, please send an email to Ahmad Hemmati.