La complexité du problème suivant a-t-elle été étudiée?
Entrée : un graphe cubique (ou régulier) , une borne supérieure naturelleG = ( V , E ) t
Question : existe-t-il une partition de en parties de taille telle que la somme des ordres des sous-graphes correspondants (non nécessairement connectés) soit au plus ?| E | / 3 3 t
Travaux connexes J'ai trouvé un certain nombre d'articles dans la littérature qui prouvent les conditions nécessaires et / ou suffisantes pour l' existence d'une partition en certains graphiques contenant trois arêtes, qui sont en quelque sorte liées, et quelques autres sur des questions de complexité computationnelle de problèmes qui recoupent le ci-dessus (par exemple, la partition doit produire des sous-graphes isomorphes à ou , et aucun poids n'est associé à une partition donnée), mais aucun d'eux n'a traité exactement le problème ci-dessus. P 4
Énumérer tous ces articles ici serait un peu fastidieux, mais la plupart d'entre eux citent ou sont cités par Dor et Tarsi .
20101024: J'ai trouvé cet article de Goldschmidt et al. , qui prouvent que le problème du partitionnement des arêtes d'un graphe en parties contenant AU PLUS arêtes, de telle sorte que la somme des ordres des sous-graphes induits soit au plus , est NP-complet, même lorsque . Est-il évident que le problème reste NP-complet sur les graphes cubiques, quand on a besoin d'une stricte égalité par rapport à ?t k = 3 k
Information additionnelle
J'ai essayé quelques stratégies qui ont échoué. Plus précisément, j'ai trouvé des contre-exemples qui prouvent que:
maximiser le nombre de triangles ne conduit pas à une solution optimale; ce que je trouve en quelque sorte contre-intuitif, car les triangles sont les sous-graphes dont l'ordre est le plus bas parmi tous les graphes possibles sur trois arêtes;
le partitionnement du graphe en composants connectés ne conduit pas non plus nécessairement à une solution optimale. La raison pour laquelle cela semblait prometteur peut être moins évidente, mais dans de nombreux cas, on peut voir que l'échange de bords afin de connecter un sous-graphique donné conduit à une solution avec un poids plus petit (exemple: essayez cela sur un triangle avec un bord supplémentaire connecté à chacun sommet; le triangle est une partie, le reste est une seconde, avec un poids total 3 + 6 = 9. L'échange de deux bords donne ensuite un chemin et une étoile, avec un poids total 4 + 4 = 8.)
la source
Réponses:
Voici une suggestion sur la façon de montrer que c'est NP difficile. Je ne sais pas si cela fonctionne ou non. Considérons d'abord le même problème sur les multigraphes. La dureté NP peut être plus facile à prouver là-bas. Essayez de réduire à partir de MAX CUT cubique qui est difficile à NP, même pour approximer (Berman et Karpinski "On Some Tight Inapproximability Results"). Divisez chaque arête en deux et à chacun des nouveaux sommets de degré 2, attachez un sommet avec auto-boucle. Votre partition maximale correspond-elle à une coupe maximale?
-
Voici un peu plus d'explications.
(1) Le problème de la maximisation (nombre de sources + nombre de puits) sur toutes les orientations d'un graphique cubique est lié à MAXCUT par une fonction linéaire. Cela nécessite de montrer une certaine corrélation entre les coupes maximales et les orientations maximales des sources et des puits. Dans une direction, dans une coupe maximale (U, V), nous pouvons orienter toutes les arêtes de U vers V. Les arêtes internes E (U) forment une correspondance, de sorte que celles-ci peuvent être orientées arbitrairement et de manière similaire pour E (V), et le nombre total de sources et de puits est une fonction linéaire de la taille de la coupe. Dans l'autre sens, étant donné une orientation maximale des sources et des puits, la partition U = sommets de degré 0 ou 1, V = sommets de degré 2 ou 3 donne une coupe.
(2) Dans la transformation de bissectrice de bord que j'ai décrite ci-dessus, dans une configuration optimale, chaque boucle est colorée de la même manière que le bord à côté, et wlog ce bord est coloré de la même manière que certains autres bords (sans boucle) à côté de cette. Ainsi, chaque bord bissecté a une couleur provenant de sa boucle attachée et une autre couleur. Cela correspond à une orientation et (1) s'applique.
la source