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

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,\text{star}_{1,2,k})$

Voici ceux que je connais:

• graphiques parfaits
• $(P,\text{star}_{1,2,5})$ -sans
• $(K_{3,3}-e, P_5)$ -Free
• co-Meyniel
• presque bipartite
• sans chaise
• ( , cricket) - gratuit$P_5$
• $(P_5,K_{n,n})$ -sans n (pour tout fixe )$n$
• $(P_5, X_{82}, X_{83})$ -sans

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:

• sans pomme (suggéré par Standa Živný)
• ( , maison) - gratuit$P_5$ (suggéré par David Eppstein)
• ( griffe) -sans$K_2 \cup$ (suggéré par David Eppstein)

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.$P_5$$P_5$$P_5$$K_{n,n}$$P_5$$X_{82}$$X_{83}$$P_5$

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.$P_5$$P_6$

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 .$X$Y Y ⊂ $X$$Y$$Y \subset X$

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 ₅ , X ₉₈ )
-sans gc_648 (K _3,3 -e, P ₅ )
-sans gc_752 clique co-héréditaire-Helly
gc_756 (E, P)
-sans gc_757 (P, T ₂ )
-sans gc_758 (P, P ₈ )
-sans gc_759 (K _3,3 -e, P ₅ , X ₉₉ )
-sans gc_808 (C ₆ , K _{3, 3} + e, P, P ₇ , X ₃₇ , X ₄₁ ) sans
gc_811 (P, étoile_1,2,5 ) - sans
gc_812 (P ₅ , P ₂ ∪ P ₃ ) - sans
gc_813 (P, P ₇ ) - sans
gc_818 (P, étoile _1,2,3 ) - sans
gc_819 (P, étoile _{1, 2,4} )
-gc_841 gratuit (2K ₃ + e, A, C ₆ , E, K _3,3 -e, P ₆ , R, X ₁₆₆ , X ₁₆₇ , X ₁₆₉ , X ₁₇₀ , X ₁₇₁ , X ₁₇₂ , X ₁₈ , X ₄₅ , X ₅ , X ₅₈ , X ₈₄ , X ₉₅ , X₉₈ , A, C ₆ , E, P ₆ , R, X ₁₆₆ , X ₁₆₇ , X ₁₆₉ , X ₁₇₀ , X ₁₇₁ , X ₁₇₂ , X ₁₈ , X ₄₅ , X ₅ , X ₅₈ , X ₈₄ , X ₉₅ , X ₉₈ , 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 ₂ , E, P ₂ ∪ P ₄ , 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!

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é?

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.

$P_5$

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.

$P_5$$H = P_2 \cup P_3$