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

Jan Hackfeld Arie M. C. A. Koster

Published in: J. Comb. Optim. (2018)

Keyphrases

np complete
graph matching
special case
polynomial time complexity
randomly generated
polynomially solvable
pspace complete
matching algorithm
neural network
constraint satisfaction problems
search algorithm
data management
graph theory
graph databases
maximum cardinality