Recognizing pinch-graphic matroids

• 成果类型: Article
• 署名作者: Guenin, Bertrand; Heo, Cheolwon
• 署名单位: University of Waterloo; Korea Institute for Advanced Study (KIAS)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-023-01951-7
• 发表日期: 2024
• 页码: 113-134
• 关键词: theorem

摘要

Even-cycle matroids are elementary lifts of graphic matroids. An even-cycle matroid is pinch-graphic if it has a signed-graph representation with a blocking pair. We present a polynomial algorithm to check if an internally 4-connected binary matroid is pinch-graphic. Combining this with a result in Guenin and Heo (Small separations in pinch-graphic matroids. Math Program (2023). https://doi.org/10.1007/s10107-023-01950-8) this allows us to check, in polynomial time, if an arbitrary binary matroid is pinch-graphic.