Une propriété de graphe est appelée héréditaire si elle se ferme par rapport à la suppression de sommets (c'est-à-dire que tous les sous-graphes induits héritent de la propriété). Une propriété de graphe est appelée additive si elle est fermée par rapport à la prise d'unions disjointes.
Il n'est pas difficile de trouver des propriétés héréditaires, mais pas additives. Deux exemples simples:
(1) Le graphique est complet.
(2) Le graphique ne contient pas deux cycles sommet-disjoints.
Dans ces cas, il est évident que la propriété est héritée par des sous-graphes induits, mais en prenant deux graphes disjoints qui ont la propriété, leur union peut ne pas la conserver.
Les deux exemples ci-dessus sont des propriétés décidables par polytemps (bien que pour (2), elles soient un peu moins triviales). Si nous voulons des propriétés plus dures, elles pourraient toujours être créées en suivant le modèle de (2), mais en remplaçant les cycles par des types de graphiques plus compliqués. Ensuite, cependant, on peut facilement courir dans la situation où le problème ne reste pas même dans , selon les hypothèses de complexité standard, tels que N P de la c o N P . Il semble moins trivial de trouver un exemple qui reste dans N P , mais c'est toujours difficile.
Question: Connaissez-vous une propriété de graphe (de préférence naturelle) complète héréditaire mais non additive?
la source
Réponses:
De toute évidence, la prise de sous-graphiques induits ne peut pas augmenter la taille minimale d'une telle partition. En revanche, lorsque vous prenez l'union disjointe de deux graphes, vous devez prendre l'union de la partition en cliques de chacun.
la source
Considérez ce problème
Il reste NP complet même si les propriétés sont héréditaires.
Désormais, une solution du problème ci-dessus pour un graphique fournit également une solution pour les sous-graphiques induits. Mais en prenant l'union de graphes de la même famille que G pourrait ne pas être résolu en utilisant cette solution.
Par exemple, le partitionnement de graphes généraux dans des graphes à intervalles unitaires disjoints est NP complet, mais en prenant l'union de tous les bords possibles (ce qui rend le graphe complet) résout le problème trivialement.
la source
Si (1) est vrai, il devrait répondre à votre question, car il donne une propriété héréditaire, mais clairement pas additive.
(NOTE AJOUTÉE: la conjecture (2) est différente de la "conjecture de couverture à double cycle" de Szekeres et Seymour, malgré l'homonymie).
la source