Coupe d'appariement (Multi) : Algorithmes, Complexité et Enumération

Une coupe d'appariement d'un graphe est une partition de son ensemble de sommets en deux, de sorte qu'aucun sommet n'ait plus d'un voisin de l'autre côté de la coupe. Le problème de la coupe d'appariement demande si un graphe possède une coupe d'appariement. Ce problème, et sa généralisation d-cut, a suscité une attention considérable de la part de la communauté des algorithmes et de la complexité au cours de la dernière décennie, devenant un exemple canonique pour les algorithmes d'énumération paramétrés et la kernelisation. Dans cet article, nous introduisons et étudions une généralisation de la coupe d'appariement, que nous avons nommée coupe multicut d'appariement : pouvons-nous partitionner l'ensemble des sommets d'un graphe en au moins parties de sorte qu'aucun sommet n'ait plus d'un voisin en dehors de sa partie ? Nous examinons cette question dans plusieurs contextes. Nous commençons par montrer que, contrairement à la coupe d'appariement, c'est NP-difficile sur les graphes cubiques mais que, lorsque est un paramètre, cela admet un noyau quasi-linéaire. Nous montrons également un algorithme exponentiel exact en O(^n{2}) pour les graphes généraux et un algorithme en O(2^O(tt)n^O(1)) pour les graphes de largeur d'arbre au plus t. Nous étudions ensuite les aspects d'énumération paramétrée des coupes multicuts d'appariement. Tout d'abord, nous généralisons le noyau quadratique de Golovach et al. pour Enum Matching Cut paramétré par la couverture de sommets, puis l'utilisons pour concevoir un noyau quadratique pour Enum Matching (Multi)cut paramétré par la distance de suppression de sommets vers co-cluster. Nos contributions finales portent sur la paramétrisation de la distance de suppression de sommets pour les clusters, où nous montrons un algorithme FPT-delay pour Enum Matching Multicut mais que aucun noyau polynomial n'existe à moins que NP coNP/poly ; nous soulignons que nous n'avons pas de telle borne inférieure pour Enum Matching Cut et considérons cela comme notre principale question ouverte.