The matching extension problem in general graphs is co-NP-complete

DOI10.1007/s10878-017-0226-xzbMath1387.05203OpenAlexW2775963553MaRDI QIDQ1743490

Jan Hackfeld, Arie M. C. A. Koster

Publication date: 13 April 2018

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-017-0226-x

zbMATH Keywords

complexityextendabilityperfect matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Connectivity (05C40)

Related Items (5)

1-extendability of independent sets ⋮ Extendability and criticality in matching theory ⋮ The extendability of Cayley graphs generated by transpositions ⋮ 1-extendability of independent sets ⋮ The distance matching extension in \(K_{1,k}\)-free graphs with high local connectedness

Cites Work

• A polynomial algorithm for the extendability problem in bipartite graphs
• Extending matchings in graphs: A survey
• Construction for bicritical graphs and \(k\)-extendable bipartite graphs
• Recent Progress in Matching Extension
• Reducibility among Combinatorial Problems
• Paths, Trees, and Flowers

This page was built for publication: The matching extension problem in general graphs is co-NP-complete