Complexity of the satisfactory partition problem

Bazgan, Cristina; Tuza, Zsolt; Vanderpooten, Daniel

Bazgan, Cristina; Tuza, Zsolt; Vanderpooten, Daniel (2003), Complexity of the satisfactory partition problem. https://basepub.dauphine.fr/handle/123456789/3937

Voir/Ouvrir

notedeR34.pdf (281.8Kb)

Type

Document de travail / Working paper

Date

2003

Titre de la collection

Note de recherche du LAMSADE

Métadonnées

Afficher la notice complète

Auteur(s)

Bazgan, Cristina
Tuza, Zsolt
Vanderpooten, Daniel

Résumé (EN)

The Satisfactory Partition problem consists in deciding if a given graph has apartition of its vertex set into two nonempty parts such that each vertex has at least asmany neighbors in its part as in the other part. This problem was introduced by Gerberand Kobler [GK98, GK00] and further studied by other authors but its complexity remained open until now. We prove in this paper that Satisfactory Partition, as wellas a variant where the parts are required to be of the same cardinality, are NP-complete.However, for graphs with maximum degree at most 4 the problem is polynomially solvable. We also study generalizations and variants of this problem where a partition into knonempty parts (k ≥ 3) is requested.

Mots-clés

Graph; Complexity; Polynomial Algorithm; NP-complete; Satisfactory partition