Trouvez les sommets à supprimer du graphique pour obtenir le plus petit composant le plus grand

Étant donné un graphique , trouvez sommets , dont la suppression aboutirait à un graphique avec la plus petite composante la plus grande. $G = (V, E)$$k$$\{v^*_1,\dots,v^*_k\}$

Je suppose que pour grandet grand le problème est difficile (NP-difficile), mais je m'intéresse aux petites valeurs de ( ).$n = |V|$$k$$k$$k \in \{1, 2, 3, 4\}$

Pour , je pense qu'il est possible de trouver le meilleur sommet à supprimer en effectuant une seule recherche de profondeur en premier du graphique (c'est-à-dire en vérifiant les points d'articulation).$k = 1$$\{v^*_1\}$

Pour , il serait possible de trouver les meilleurs sommets en effectuant profondeur d'abord (chacune d'elles pour le graphique ). Une approche similaire pourrait être appliquée dans le cas .$k = 2$$\{v^*_1, v^*_2\}$$n$$G_i = G / \{v_i\}$$k > 2$

Je me demande s'il y a une meilleure solution que cela.

(Connexes: compter le nombre minimum de sommets sans nécessairement les énumérer )

Le problème que vous décrivez est connu sous le nom de connectivité d'ordre des composants dans le domaine des mesures de vulnérabilité des graphiques . La version de décision du problème est la suivante:

Connectivité de l'ordre des composants :

Entrée: graphique$G = (V,E)$, entiers $k$ et $\ell$

Question: Existe-t-il un ensemble de sommets$X \subseteq V$ de taille au plus $k$ de telle sorte que la taille de la plus grande composante de $G - X$ est tout au plus $\ell$?

Le problème est évidemment NP-complet car il généralise la couverture des sommets; le cas où$\ell=1$est la couverture du sommet. Par conséquent, le problème ne peut pas être fixé comme paramètre paramétrable lorsqu'il est paramétré par$\ell$ (sauf si $FPT = W[1]$). Le problème est également connu pour être$W[1]$-hard lorsqu'il est paramétré par $k$. Par conséquent, nous devons recourir à des algorithmes avec un temps de fonctionnement exponentiel dans$k+\ell$.

Question très intéressante. Pour entrée$G,k,\ell$, une approche par force brute serait:

branching(G,k,l):
    Find a connected set of vertices D of G of size l+1
    if no such D exists:
            return True // no component of size > l
    for v in D:
        if branching(G-v,k-1,l):
            return True
    return False

L'algorithme s'exécute dans le temps $(\ell + 1)^k \cdot n^2$.

Observez que toute instance oui $G,k,\ell$ du problème a une largeur d'arbre, et même une largeur de chemin $k+\ell$. Cela peut être observé en voyant que la prise d'un ensemble de suppression$X$ de taille au plus $k$ donne un graphique $G-X$ où chaque composant connecté a une taille maximale $\ell$. Par conséquent, une décomposition de chemin valide consiste simplement à construire un sac pour chacun des composants dans$G-X$ puis ajoutez tous $X$à chaque sac. Il s'ensuit que toute instance oui a$|E(G)| \leq n(k+\ell)$.

Un problème connexe a été étudié dans le passé sous le nom d'intégrité du graphique, ou intégrité de sommet pour distinguer la version de suppression de sommet et la version de suppression de bord:

Intégrité du sommet :

Entrée: graphique$G = (V,E)$, entier $p$

Question: Existe-t-il un ensemble de sommets$X \subseteq V$ tel que $|X| + \max_{D \in cc(G-X)}|D| \leq p$?

Autrement dit, la somme de l'ensemble de suppression et la taille du composant maximal doivent être minimisées. Ce problème est également NP-difficile. Voir, par exemple,

• Clark, LH, Entringer, RC, Fellows, MR: Complexité informatique de l'intégrité. J. Combin. Math. Combiner. Comput 2, 179-191 (1987)
• Fellows, M., Stueckle, S .: L'ordre d'immersion, les sous-graphiques interdits et la complexité de l'intégrité du réseau. J. Combin. Math. Combiner. Comput 6, 23–32 (1989)