[LMM12] On the NP-Completeness of the Perfect Matching Free Subgraph Problem

Revue Internationale avec comité de lecture : Journal Theoretical Computer Science, vol. 423, pp. 25-29, 2012, (doi:10.1016/j.tcs.2011.12.065)

Auteurs: M. Lacroix , R. Mahjoub , S. Martin , C. Picouleau

motcle:

Résumé: Given a bipartite graph G = (U âˆª V, E) such that |U| = |V | and every edge is labelled true or false or both, the perfect matching free subgraph problem is to determine whether or not there exists a subgraph of G containing, for each node u of U, either all the edges labelled true or all the edges labelled false incident to u, and which does not contain a perfect matching. This problem arises in the structural analysis of differential-algebraic systems. The purpose of this paper is to show that this problem is NP-complete. We show that the problem is equivalent to the stable set problem in a restricted case of tripartite graphs. Then we show that the latter remains NP-complete in that case. We also prove the NP-completeness of the related minimum blocker problem in bipartite graphs with perfect matching.

Equipe: oc

Collaboration: LIPN , LAMSADE

BibTeX

@article {
	LMM12,
	title	=	"{On the NP-Completeness of the Perfect Matching Free Subgraph Problem}",
	author	=	"M. Lacroix and R. Mahjoub and S. Martin and C. Picouleau",
	journal	=	"Theoretical Computer Science",
	year	=	2012,
	volume	=	423,
	pages	=	"25-29",
	doi	=	"10.1016/j.tcs.2011.12.065",
}