Separation routine and extended formulations for the stable set problem in claw-free graphs

• 成果类型: Article
• 署名作者: Faenza, Yuri; Oriolo, Gianpaolo; Stauffer, Gautier
• 署名单位: Columbia University; University of Rome Tor Vergata; Kedge Business School
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-020-01502-4
• 发表日期: 2021
• 页码: 53-84
• 关键词: algorithms; polytope

摘要

The maximum weighted stable set problem in claw-free graphs is a well-known generalization of the maximum weighted matching problem, and a classical problem in combinatorial optimization. In spite of the recent development of fast(er) combinatorial algorithms and some progresses in the characterization of the corresponding stable set polytope, the problem of providing a decent linear description for this polytope (Grotschel et al. in Geometric algorithms and combinatorial optimization, Springer, New York, 1988) is still open. The main contribution of this paper is to propose an algorithmic answer to that question by providing a polynomial-time and computationally attractive separation routine for the stable set polytope of claw-free graphs, that only requires a combinatorial decomposition algorithm, the solution of (moderate sized) compact linear programs, and Padberg and Rao's algorithm for separating over the matching polytope. In particular, it is a generalization of the latter and avoids the heavy computational burden of resorting to the ellipsoid method, on which the only poly-time separation routine known so far relied. Besides, our separation routine comes with a 'small' (but not polynomial) extended linear programming formulation and a procedure to derive a linear description of the stable set polytope of claw-free graphs in the original space.