Ensemble indépendant sur des graphiques sans triangle cubique

Je sais que l'ensemble indépendant maximum sur les graphiques sans triangle cubique est NP-complet.

Est-il toujours NP-complet au cas où nous aurions besoin que l'ensemble indépendant soit exactement de la taille ? $|V|/2$

Fondamentalement, l'instance OUI d'un problème d'ensemble indépendant sur un problème de graphes sans triangle cubique doit avoir exactement nœuds. AUCUNE instance n'a un ensemble indépendant de taille inférieur à . $|V|/2$ $|V|/2$

complexity-theory np-complete Mohammad Al-Turkistany
la source

cs.stackexchange.com/questions/1176/… peut être pertinent.

Louis

Quelles sont les instances NO?

Yuval Filmus

@YuvalFilmus Il demande si le problème est $\alpha(G) = |G| / 2$ oùest l'ordre du graphique. Il devrait être possible de garnir certains sommets isolés sur le graphique pour augmenter le nombre d'indépendance. Mohammad, connaissez-vous la réduction? N'est-il pas possible d'ajouter sommets isolés pour obtenir la réduction souhaitée?

| G |

$|G|$

n / 2 - k

$n/2 - k$

Pål GD

Non, je n'ai pas de réduction.

Mohammad Al-Turkistany

@ PålGD La réduction ne fonctionnerait pas, car le problème habituel demande si plutôt que . En fait, il n'est même pas clair que le problème se situe dans NP.

α (G) \geq k

$\alpha(G) \geq k$

α (G) = k

$\alpha(G) = k$

Yuval Filmus

Réponses:

Commençons par prouver que l'ensemble indépendant maximum est de taille au plus . Que sois un ensemble indépendant. Pour chaque sommet , que soit le nombre de ses voisins dans . Si , alors nous savons que . Puisque le graphique est cubique,. Depuis , le nombre de sommets tels que est au moins. D'où . $|V|/2$ $I$ $v$ $\alpha(v)$ $I$ $\alpha(v) \geq 1$ $v \notin I$ $\sum_v \alpha(v) = 3|I|$ $\alpha(v) \leq 3$ $\alpha(v) \geq 1$ $|I|$ $|I| \leq |V|/2$

Quand pouvons-nous avoir l'égalité? Nous devons avoir , donc pour chaque sommet pas , tous ses voisins doivent être . L'inverse est également vrai - pour chaque sommet , tous ses voisins ne sont pas en . En d'autres termes, le graphique doit être bipartite. Cela peut être vérifié en temps polynomial. $\alpha(v) \in \{0,3\}$ $I$ $I$ $I$ $I$

Yuval Filmus
la source

YuvalFilmus Merci beaucoup. Est-ce que cela donne un algorithme de temps polynomial pour mon problème?

Mohammad Al-Turkistany

Je pense que oui - êtes-vous d'accord?

Yuval Filmus