Submodular Functions and Perfect Graphs

• 成果类型: Article
• 署名作者: Abrishami, Tara; Chudnovsky, Maria; Dibek, Cemil; Vuskovic, Kristina
• 署名单位: University of Hamburg; Princeton University; Princeton University; University of Leeds
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2021.0302
• 发表日期: 2025
• 关键词: algorithm

摘要

We give a combinatorial polynomial-time algorithm to find a maximum weight independent set in perfect graphs of bounded degree that do not contain a prism or a hole of length four as an induced subgraph. An even pair in a graph is a pair of vertices all induced paths between which are even. An even set is a set of vertices every two of which are an even pair. We show that every perfect graph that does not contain a prism or a hole of length four as an induced subgraph has a balanced separator which is the union of a bounded number of even sets, where the bound depends only on the maximum degree of the graph. This allows us to solve the maximum weight independent set problem using the well-known submodular function minimization algorithm.