The computational complexity of the Edge-Perfect Graph and the Totally Balanced Packing Game recognition problems

Edge-perfect graphs were introduced by Escalante et al (2009). An edge-subgraph of a given graph is an induced subgraph obtained by deletion of the endpoints of a subset of edges. A graph is edge-perfect if the stability and the edge covering numbers coincide for every edge-subgraph.In this work we prove that the recognition of edge-perfect graphs is an NP-hard problem. As a by-product, we derive the NP-completeness of two related problems in graphs.From the NP-hardness of the edge-perfection recognition problem we answer the open question on the recognition of totally balanced packing game defining matrices —raised by Deng et al. in 2000—, obtaining that this problem is NP-hard in contrast with the polynomiality for the covering case due to van Velzen (2005).