Fixed cardinality stable sets

Autor: Dag Haugland, Phillippe Samer
Rok vydání: 2021
Předmět:
Theoretical computer science
programming science and theory: 421 [VDP]
Convex hull
Kombinatorisk optimalisering
0211 other engineering and technologies
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Teoretisk databehandling
programmeringsspråk og -teori: 421 [VDP]
Combinatorics
Cardinality
Integer
Simple (abstract algebra)
TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY
Combinatorial Optimization
Discrete Mathematics and Combinatorics
Undirected graph
Integer programming
Time complexity
Diskret matematikk
Mathematics
Matematisk optimering
Applied Mathematics
Mathematical optimization
021107 urban & regional planning
Discrete mathematics
Dual (category theory)
010201 computation theory & mathematics
MathematicsofComputing_DISCRETEMATHEMATICS
Zdroj: Discrete Applied Mathematics
ISSN: 0166-218X
DOI: 10.1016/j.dam.2021.01.019
Popis: 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.
Databáze: OpenAIRE
Externí odkaz: