Classes maximales pour quel plus grand ensemble indépendant peut-on trouver en temps polynomial?

28

L' ISGCI répertorie plus de 1100 classes de graphiques. Pour beaucoup d'entre eux, nous savons si le JEU INDÉPENDANT peut être décidé en temps polynomial; elles sont parfois appelées classes IS-easy . Je voudrais compiler une liste de classes IS-easy maximales . Ces classes forment ensemble la limite de la tractabilité (connue) de ce problème.

Puisqu'on peut simplement ajouter un nombre fini de graphiques à n'importe quelle classe IS-easy infinie sans affecter la tractabilité, certaines restrictions sont en règle. Limitons les classes à celles qui sont héréditaires (fermées par la prise de sous-graphiques induits, ou de manière équivalente, définies par un ensemble de sous-graphiques induits exclus). De plus, considérons uniquement les familles sans X pour un ensemble X avec une petite description. Il pourrait y aussi être infinies chaînes ascendantes des classes traitables (tels que -Free et les classes décrites par David Eppstein ci - dessous), mais nous allons limiter l' attention aux classes se sont avérés être IS-easy.(P,star1,2,k)

Voici ceux que je connais:

Connaît-on d'autres classes maximales de ce type?


Edit: Voir aussi une question connexe posée par Yaroslav Bulatov concernant les classes définies par les mineurs exclus, qu'est-ce qui est facile pour les graphiques mineurs exclus? et voir les propriétés globales des classes héréditaires? pour une question plus générale que j'ai posée précédemment sur les cours héréditaires.

Comme le souligne Jukka Suomela dans ses commentaires, le cas des mineurs exclus est également intéressant (et poserait une question intéressante), mais ce n'est pas le sujet ici.

Pour éviter l'exemple de David, une classe maximale devrait également être définissable comme les graphiques sans X, où tous les graphiques de X n'ont pas de sommet indépendant.

Classes données dans les réponses ci-dessous:


Ajouté le 09-10-2013: le résultat récent de Lokshtanov, Vatshelle et Villanger, mentionné par Martin Vatshelle dans une réponse, remplace certaines des classes maximales précédemment connues.

En particulier, free étant IS-easy subsumes ( P 5 , cricket)-free, ( P 5 , K n , n )-free, ( P 5 , X 82 , X 83 )-free, and ( P 5 , maison) -gratuit étant IS-facile.P5P5P5Kn,nP5X82X83P5

Cela signifie que toutes les classes de graphes héréditaires définies par un seul sous-graphe induit interdit avec jusqu'à cinq sommets peuvent maintenant être définitivement classées comme IS-easy ou non IS-easy.

Malheureusement, la preuve que les graphiques sans forment une classe IS-easy ne semble pas fonctionner pour les graphiques sans P 6 , donc la prochaine frontière est de classer toutes les classes de graphiques héréditaires définies par un seul graphique à six sommets.P5P6

Je reste particulièrement intéressé par les classes de la forme IS-facile -Free pour une collection de graphiques avec une infinité de classes d'isomorphismes, mais où -free n'IS-facile pour tout .XY Y XXOuiOuiX

András Salamon
la source
1
Qu'en est-il des graphiques avec une largeur d'arbre bornée? Je suppose qu'ils sont déjà contenus dans l'une des classes que vous avez mentionnées?
Jukka Suomela
@Jukka: pour autant que je sache, la largeur d'arbre bornée n'est pas possible de capturer avec un petit ensemble de sous-graphiques induits exclus. Par exemple, la largeur d'arbre 2 est sans ; cela génère un ensemble infini de sous-graphiques induits exclus. D'un autre côté, un "arbre k partiel" pourrait bien être qualifié de "petite" description. Qu'est-ce que tu penses? K4
András Salamon
ás: Oh, il semble que je n'ai pas lu votre question assez attentivement, je pensais que vous vous intéressiez également aux familles de graphes caractérisées en termes de mineurs interdits.
Jukka Suomela
2K2O(n2)
@ Hsien-Chih Chang: Merci d'avoir mentionné la classe Balas-Yu, j'avais oublié celle-là. Oui, cela apporterait certainement une réponse pertinente.
András Salamon,

Réponses:

10

La question est déjà un peu plus ancienne, mais l'ISGCI peut être utile ici.

Lorsque vous démarrez l'application ISGCI Java et accédez au menu Problèmes -> Classes limites / ouvertes -> Ensemble indépendant, vous obtenez une boîte de dialogue avec 3 listes.

La liste Maximal P contient toutes les classes C (en ISGCI) sur lesquelles IS peut être résolu en temps polynomial, de sorte qu'il existe une superclasse minimale de C sur laquelle IS n'est pas connu pour être en P (c'est-à-dire NP-complet, ouvert ou inconnu de l'ISGCI). Sélectionner une classe et cliquer sur «Dessiner» dessinera la classe et les superclasses trouvées en remontant le style BFS dans la hiérarchie d'inclusion autant que nécessaire pour trouver une classe sur laquelle IS n'est pas connu pour être en P.

La liste Minimal NP-complete va dans l'autre sens: elle contient les classes sur lesquelles IS est NP-complete, de sorte que toutes les sous-classes maximales ne sont pas aussi NP-complete. Le dessin descend dans la hiérarchie jusqu'à ce qu'une classe non complète NP soit trouvée.

La liste ouverte contient des classes pour lesquelles le problème est ouvert ou inconnu. Le dessin parcourt les super / sous-classes jusqu'à atteindre une classe qui n'est pas ouverte.

Lors de la création d'un dessin, il est judicieux de définir la coloration sur le problème Ensemble indépendant (Problèmes -> Couleur du problème -> Ensemble indépendant).


En ce qui concerne la question de Standa Zivny, les 20 classes suivantes sont répertoriées dans ISGCI avec une complexité connue pour le problème IS non pondéré, mais avec une complexité inconnue pour le cas pondéré (ISGCI ne peut pas distinguer les algorithmes polynomiaux "simples" et "compliqués"):

gc_11 étendu P 4 - chargé
gc_128 EPT
gc_415 bien couvert
gc_428 (K 3,3 -e, P 5 , X 98 )
-sans gc_648 (K 3,3 -e, P 5 )
-sans gc_752 clique co-héréditaire-Helly
gc_756 (E, P)
-sans gc_757 (P, T 2 )
-sans gc_758 (P, P 8 )
-sans gc_759 (K 3,3 -e, P 5 , X 99 )
-sans gc_808 (C 6 , K 3, 3 + e, P, P 7 , X 37 , X 41 ) sans
gc_811 (P, étoile1,2,5 ) - sans
gc_812 (P 5 , P 2 ∪ P 3 ) - sans
gc_813 (P, P 7 ) - sans
gc_818 (P, étoile 1,2,3 ) - sans
gc_819 (P, étoile 1, 2,4 )
-gc_841 gratuit (2K 3 + e, A, C 6 , E, K 3,3 -e, P 6 , R, X 166 , X 167 , X 169 , X 170 , X 171 , X 172 , X 18 , X 45 , X 5 , X 58 , X 84 , X 95 , X98 , A, C 6 , E, P 6 , R, X 166 , X 167 , X 169 , X 170 , X 171 , X 172 , X 18 , X 45 , X 5 , X 58 , X 84 , X 95 , X 98 , antenne, co-antenne, co-domino, co-poisson, co-maison jumelle, domino, poisson, maison jumelle)
-gratuit gc_894 co-circulaire parfait
gc_895 fortement circulaire parfait
(3K 2 , E, P 2 ∪ P 4 , net) - sans

Il est certain qu'un certain nombre d'entre eux auront également des algorithmes connus pour le cas pondéré. Les ajouts et corrections sont toujours les bienvenus à l'adresse indiquée sur la page web de l'ISGCI!

Ernst de Ridder
la source
merci pour le pointeur sur la fonctionnalité de l'application Java pour trouver les classes maximales tractables, et la liste des classes pour lesquelles le cas pondéré est ouvert. Et bien sûr merci pour votre travail sur l'ISGCI!
András Salamon
12

Un article intéressant à examiner pourrait être:

A. Brandstadt, VV Lozin, R. Mosca: ensembles indépendants de poids maximum dans les graphiques sans pomme, SIAM Journal on Discrete Mathematics 24 (1) (2010) 239–254. doi: 10.1137 / 090750822

La classe infinie de pommes est définie comme les cycles C_k, k> = 5, chacun avec une tige.

Vous ne mentionnez pas si votre notion de facilité SI inclut le problème SI pondéré. Les graphiques sans chaise (ou graphiques sans fourche) sont connus pour être faciles à utiliser:

VE Alekseev, Algorithme polynomial pour trouver les plus grands ensembles indépendants dans les graphiques sans fourches, Discrete Applied Mathematics 135 (1-3) (2004) 3-16. doi: 10.1016 / S0166-218X (02) 00290-1

La tractabilité du cas pondéré est une extension non triviale, voir:

VV Lozin, M. Milanic: Un algorithme polynomial pour trouver un ensemble indépendant de poids maximum dans un graphique sans fourche, Journal of Discrete Algorithms 6 (4) (2008) 595–604. doi: 10.1016 / j.jda.2008.04.001

Y a-t-il d'autres classes (intéressantes) où le problème SI pondéré est beaucoup plus difficile / insoluble / ouvert que le cas non pondéré?

Standa Zivny
la source
1
Question intéressante, pourrait valoir la peine d'être publiée séparément.
András Salamon
Dans la définition des pommes, vous voulez dire k ≥ 4, non?
David Eppstein
Oui, k> = 4, désolé pour la faute de frappe.
Standa Zivny
10

Selon Vassilis Giakoumakis et Irena Rusu, Disc. Appl. Math. 1997 , les graphiques sans (P5, maison) (ou graphes sans (P5, coP5)) sont faciles à utiliser.

Un autre, crédité par l'ISGCI à V. Lozin, R. Mosca Disc. Appl. Math. 2005 , est la famille des graphiques sans (griffe K2 u) .

Il pourrait également y avoir des chaînes ascendantes infinies de classes tractables

Il y a définitivement des chaînes ascendantes infinies. Si H est un ensemble fini de graphiques pour lesquels les graphiques sans H sont IS-faciles, soit H 'les graphiques formés en ajoutant un sommet indépendant à chaque graphique en H. Alors les graphiques sans H sont également IS-faciles: il suffit d'appliquer l'algorithme sans H aux ensembles de non-voisins de chaque sommet. Par exemple, comme le décrit l'ISGCI, les graphiques sans co-gemme sont IS-faciles car un co-gemme est un P4 plus un sommet indépendant et les graphiques sans P4 sont IS-faciles. Donc, vous voulez probablement limiter votre question aux classes maximales dans lesquelles tous les sous-graphiques interdits n'ont pas de sommet indépendant.

David Eppstein
la source
Merci pour les cours supplémentaires et pour avoir mis en évidence une construction facile de chaînes infinies! Va reformuler.
András Salamon
Il en va de même pour les graphiques sans griffes, selon l'entrée de Wikipedia sur Ensemble indépendant: en.wikipedia.org/wiki/…
gphilip
3
@gphilip: sans griffes sont inclus à la fois sans chaise et sans griffe (K2 u).
David Eppstein
8

P5

Soit H un graphe sur au plus 5 sommets, alors la complexité de l'ensemble indépendant est connue sur la classe des graphes sans H.

P5H=P2P3

Martin Vatshelle
la source