Submodular Functions and Perfect Graphs

Tara Abrishami (), Maria Chudnovsky (), Cemil Dibek () and Kristina Vušković ()
Additional contact information
Tara Abrishami: Department of Mathematics, University of Hamburg, 20148 Hamburg, Germany
Maria Chudnovsky: Department of Mathematics, Princeton University, Princeton, New Jersey 08544
Cemil Dibek: Department of Operations Research and Financial Engineering, Princeton University, Princeton, New Jersey 08544
Kristina Vušković: School of Computing, University of Leeds, Leeds LS2 9JT, United Kingdom

Mathematics of Operations Research, 2025, vol. 50, issue 1, 189-208

Abstract: 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.

Keywords: Primary: 05C17; Secondary: 05C69; 05C85; 90C27; perfect graphs; submodular functions; maximum weight independent set; even sets (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.0302 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:50:y:2025:i:1:p:189-208

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().