Persistency of Linear Programming Relaxations for the Stable Set Problem

Elisabeth Rodríguez-Heck, Karl Stickler, Matthias Walter*, Stefan Weltge

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

72 Downloads (Pure)

Abstract

The Nemhauser-Trotter theorem states that the standard linear programming (LP) formulation for the stable set problem has a remarkable property, also known as (weak) persistency: for every optimal LP solution that assigns integer values to some variables, there exists an optimal integer solution in which these variables retain the same values. While the standard LP is defined by only non-negativity and edge constraints, a variety of stronger LP formulations have been studied and one may wonder whether any of them has the this property as well. We show that any stronger LP formulation that satisfies mild conditions cannot have the persistency property on all graphs, unless it is always equal to the stable-set polytope.

Original languageEnglish
Title of host publicationInteger Programming and Combinatorial Optimization - 21st International Conference, IPCO 2020, Proceedings
EditorsDaniel Bienstock, Giacomo Zambelli
PublisherSpringer
Pages351-363
Number of pages13
ISBN (Electronic)978-3-030-45771-6
ISBN (Print)978-3-030-45770-9
DOIs
Publication statusPublished - 14 Apr 2020
Event21st International Conference on Integer Programming and Combinatorial Optimization, IPCO 2020 - London, United Kingdom
Duration: 8 Jun 202010 Jun 2020
Conference number: 21
http://www.lse.ac.uk/IPCO-2020

Publication series

NameLecture Notes in Computer Science
Volume12125
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference21st International Conference on Integer Programming and Combinatorial Optimization, IPCO 2020
Abbreviated titleIPCO 2020
Country/TerritoryUnited Kingdom
CityLondon
Period8/06/2010/06/20
OtherOnline conference
Internet address

Keywords

  • Integer linear programming
  • Persistency
  • Stable set
  • 22/2 OA procedure

Fingerprint

Dive into the research topics of 'Persistency of Linear Programming Relaxations for the Stable Set Problem'. Together they form a unique fingerprint.

Cite this