Odd faces as a parameter for maximum independent set in embedded graphs
Source: arxiv.org/abs/2611.21256
We give a polynomial-time algorithm for finding a maximum weight independent set in a graph embedded in a surface of bounded genus and with a bounded number of vertex-disjoint odd faces. In particular, we obtain an algorithm for graphs with an even-faced embedding in a torus and for planar graphs with a bounded number of odd faces, answering a question of Thomassé (2018) and a question of Choi, Gorsky, Kim, McFarland, and Wiederrecht (2025) respectively. We reduce the original problem to finding a minimum cost non-negative integer circulation with homology constraints in the dual of a…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.21256
curl -X POST /api/v1/records/arxiv/2611.21256/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.21256/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'