Fixed cardinality stable sets

LUNCH SEMINAR (November, 2019)

Main content

Speaker: Phillippe Samer

Title: Fixed cardinality stable sets


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.