Est-ce que Logical Min-Cut NP-Complete?

Définition du problème Logical Min Cut (LMC)

Supposons que est un digraphe non pondéré, et sont deux sommets de , et est accessible à partir de . Le problème LMC étudie comment rendre inaccessible à partir de en supprimant certaines arêtes de respectant les contraintes suivantes:s t V t s t s $G = (V, E)$$s$$t$$V$$t$$s$$t$$s$$G$

1. Le nombre de bords supprimés doit être minimal.
2. Nous ne pouvons pas supprimer tous les bords de sortie d'un sommet de (c'est-à-dire qu'aucun sommet avec des bords sortants ne peut avoir tous ses bords sortants supprimés).$G$

Cette deuxième contrainte est appelée suppression logique. Nous recherchons donc une suppression logique et minimale de certains bords de telle sorte que soit inaccessible à partir de .t $G$$t$$s$

Tentatives de solution

Si nous ignorons la contrainte de suppression logique du problème LMC, ce sera le problème de coupe minimale dans le digraphe non pondéré , il sera donc résolu polynomialement (théorème de coupe minimale de débit maximal).$G$

Si nous ignorons la contrainte de suppression minimale du problème LMC, elle sera de nouveau solvable polynomialement dans un DAG: trouver un sommet tel que soit accessible depuis et ne soit pas accessible depuis . Considérons alors un chemin qui est un chemin arbitraire de à . Considérons maintenant le chemin comme un sous-graphe de : la réponse sera chaque bord de sortie du sous-graphe . Il est évident que le sommet peut être trouvé par DFS dans en temps polynomial. Malheureusement, cet algorithme ne fonctionne pas en généralk s t k p s k p G p k $k$$k$$s$$t$$k$$p$$s$$k$$p$$G$$p$$k$$G$ pour un graphe dirigé arbitraire.

J'ai essayé de résoudre le problème LMC par une technique de programmation dynamique mais le nombre d'états requis pour résoudre le problème est devenu exponentiel. De plus, j'ai essayé de réduire certains problèmes NP-Complete tels que 3-SAT, max2Sat, max-cut et clique au problème LMC que je n'ai pas réussi à trouver de réduction.

Personnellement, je pense que le problème LMC est NP-complet même si est un DAG binaire (c'est-à-dire un DAG où aucun nœud n'a un degré supérieur à 2).$G$

Des questions

1. Le problème LMC est-il NP-complet dans un digraphe arbitraire ? (question principale)$G$
2. Le problème LMC est-il NP-Complete dans un DAG arbitraire ?$G$
3. Le problème LMC est-il NP-Complete dans un DAG binaire arbitraire ?$G$

Soit G = (V, E) un DAG pondéré, s et t deux sommets de G, et LSTMC = (G, s, t) une instance du problème logique de st min-cut. Il est évident que le problème LSTMC est NP. Maintenant, nous devons montrer que le LSTMC est NP-Hard. Nous réduisons le problème de l'ensemble de frappe au problème LSTMC. Soit S = {s1, s2, ..., sn} les ensembles donnés et {a1, a2, ..., am} l'union de tous les ensembles. Etant donné le nombre k1, le problème de décision du problème d'ensemble frappant indique s'il existe un ensemble A avec des éléments k1 tels que chaque élément de S (chaque ensemble si st i = 1..n) contient au moins un élément de A. Nous dénoter le problème d'ensemble de frappe comme HS (S). Nous construisons le DAG G 'pondéré à partir de l'ensemble S par l'algorithme HS2LSTMC. Cet algorithme considère s comme le sommet source du DAG G '. Pour chaque ensemble si de HS st i = 1..n, l'algorithme considère le sommet correspondant, si, et ajoute un bord avec un poids infini de s à chaque si. Ensuite, pour chaque élément aj de l'union des ensembles d'entrée st j = 1..m, l'algorithme considère le sommet correspondant, aj, et ajoute un bord avec un poids nul de chaque si à n'importe quel aj st aj ∈si dans HS. Enfin, l'algorithme considère deux sommets finaux appelés t et k, et ajoute deux arêtes de chaque aj st j = 1..m aux deux sommets finaux. Il est clair que G 'peut être réalisé en temps polynomial.

Maintenant, nous devons démontrer que HS (S) a une réponse avec k1 éléments si et seulement si LSTMC = (G ′, s, t) a une réponse avec des arêtes logiquement supprimées de telle sorte que la somme des poids des arêtes supprimées soit k1.

Par souci de simplicité, nous effectuons cette partie de la preuve, en fournissant un exemple:

Dans la figure suivante, supposons que S = {s1, s2, s3} tel que s1 = {1, 2, 3}, s2 = {1, 4} et s3 = {2, 5}. La figure 2 montre le DAG G 'pondéré du problème LSTMC correspondant au problème d'ensemble de frappes HS (S). Dans cet exemple, l'ensemble A, à savoir l'union de tous les éléments de S, est A = {1, 2, 3, 4, 5}. Nous avons | S | = 3 et | A | = 5. Cet exemple montre comment une instance arbitraire du problème de l'ensemble de frappe peut être résolue à l'aide d'une instance spécifique du problème de st min-cut logique dans un DAG pondéré. Si nous calculons une réponse à LSTMC = (G ′, s, t) et considérons les bords supprimés de la réponse qui sont sous la forme de (aj, t) appelés E1 (1 ≤ j ≤ m), alors l'ensemble de queue de E1 est une réponse à HS (S). Une réponse au problème LSTMC est l'ensemble de bords E1 = {(s1, 2), (s1, 3), (s2, 4), (s3, 5), (1, t), (2, t)}. Ainsi, l'ensemble de queue du sous-ensemble E2 = {(1, t), (2,

Voici (une tentative) un algorithme polynomial pour le arbitraire binaire LMC DAG .$G$

Cela répond à la question n ° 3. (Désolé pour l'écriture désordonnée à l'avance. :))

Pour commencer, jeter « pour toujours » tout sommet pas accessible de . Nous ne nous en soucions pas, car ils ne font partie d'aucun chemin s - t .$s$$s$$t$

Ensuite, définissez les sous-DAG et B , initialement vides. Alors, pour tous les sommets v ∈ G - { s , t } ,$A$$B$$v \in G-\{s, t\}$

Testez s'il existe un chemin de à t . Si oui, ajoutez v à A . Sinon, ajoutez - v à B .$v$$t$$v$$A$$v$$B$

Soit les arêtes de et B celles induites par les sommets de chaque ensemble (pour l'instant, ignorez toutes les arêtes de s à A , de A à t et de A à B ; notez également qu'il n'y a pas d'arêtes de B à t par construction).$A$$B$$s$$A$$A$$t$$A$$B$$B$$t$

Ensuite, calculer la fermeture transitive de . A savoir, nous sommes intéressés à trouver une série de sommets { a * } qui sont les « feuilles » de la sous-DAG A .$A$$\{a^*\}$$A$

Fixer un tel . Observer qu'il doit y avoir un bord dirigé depuis un * à t . C'est parce que, par construction, (i) il y a un chemin s - t à travers un ∗ , (ii) il n'y a pas de chemin de a ∗ à B , et (iii) puisque A est lui-même un DAG et a ∗ est une feuille de A , il n'y a pas de chemin entre a ∗ et un autre sommet de A vers t .$a^*$$a^*$$t$$s$$t$$a^*$$a^*$$B$$A$$a^*$$A$$a^*$$A$$t$

Maintenant, il doit également y avoir une arête dirigée de chaque sommet dans vers un sommet dans B , ou certains des { a ∗ } ont une arête unique vers t . Dans les deux cas, nous sommes autorisés à supprimer toute une * → t bord.$\{a^*\}$$B$$\{a^*\}$$t$$a^*\rightarrow t$

Si = 1, alors soit nous devons supprimer l'arête de l'unique a ∗ → t , soit il y a un sommet plus tôt dans le chemin s - t contenant un ∗ qui a deux chemins vers t - un à travers un ∗ et un directement. Dans le cas où celui-ci pourrait tenir, nous enregistrons un ∗ → t et procédons "à reculons goulûment" (détails ci-dessous).$|\{a^*\}|$$a^*\rightarrow t$$s$$t$$a^*$$t$$a^*$$a^*\rightarrow t$

Si > 1, alors nous devons soit supprimer toutes les arêtes de { a ∗ } → t , soit il y a un certain nombre d'arêtes k < | { a ∗ } | plus tôt dans la fermeture transitive de A qui déconnecte tous les chemins de s à travers le { a ∗ } à t .$|\{a^*\}|$$\{a^*\}\rightarrow t$$k < |\{a^*\}|$$A$$s$$\{a^*\}$$t$

C'est là que nous utilisons le fait que le graphe est un DAG binaire.$G$

Considérons l'ensemble des prédécesseurs de . Étant donné que chacun de ces sommets a au plus deux degrés, il existe exactement trois cas:$\{a^*\}$

Cas 1. prédécesseur A a un hors-bord à un sommet dans et un hors-bord à un sommet en B .$\{a^*\}$$B$

Dans ce cas, peu importe que nous supprimions l'arête du prédécesseur au sommet dans ou l'arête du sommet dans { a ∗ } à t . Par conséquent, nous pouvons «ignorer» ce sommet (et vérifier si le chemin vers l'arrière fusionne avec le chemin d'un autre sommet dans { a ∗ } ).$\{a^*\}$$\{a^*\}$$t$$\{a^*\}$

Cas 2. Un prédécesseur a un bord extérieur à un sommet dans et un autre prédécesseur de { a ∗ } .$\{a^*\}$$\{a^*\}$

Dans ce cas, nous devons soit supprimer les deux bords de à t , soit supprimer un seul bord antérieur du chemin de s au prédécesseur qui déconnecte les deux chemins.$\{a^*\}$$t$$s$

Cas 3. Un prédécesseur a un bord extérieur à deux sommets dans .$\{a^*\}$

Ceci est identique au cas 2. Peu importe que nous supprimions l'une des arêtes de ce prédécesseur et les autres arêtes correspondantes de à t , ou les deux arêtes de { a ∗ } à t . Nous voulons juste savoir si nous pouvons déconnecter le chemin de s par ce prédécesseur à t avec un seul bord plus tôt dans le chemin de s au prédécesseur.$\{a^*\}$$t$$\{a^*\}$$t$$s$$t$$s$

Au total, alors que nous parcourons les prédécesseurs dans la fermeture transitive de , nous pouvons goulûment suivre les choix «les meilleurs jusqu'à présent». Autrement dit, à chaque étape, nous avons un choix évident qui implique la suppression d'un certain nombre d'arêtes, mais nous voulons attendre de voir si une meilleure option est disponible. Une fois qu'une meilleure option est trouvée, nous pouvons «oublier» l'option précédente. Par conséquent, un choix gourmand à chaque couche de prédécesseurs suffit (tant que nous attendons la fin pour nous engager dans n'importe quel choix).$A$

Par conséquent, avec une mémorisation de base, les complexités temporelles et spatiales de ce processus semblent être au plus . Cela laisse de côté le fait que, alors que nous pouvons identifier localement / avidement quand nous avons trouvé un «choix moins cher», il est a priori peu clair quels bords précédemment enregistrés à supprimer. Par conséquent, nous enregistrons l'ordre dans lequel nous vérifions les bords au fur et à mesure. Après avoir trouvé une meilleure option, nous répétons la recherche jusqu'à ce point afin de trouver les bords précédemment enregistrés à supprimer. La complexité temporelle totale de cette étape est O ( | E | 2 ) et la complexité spatiale O ( | E |$O(|E|)$$O(|E|^2)$$O(|E|)$.

Au total, la complexité temporelle est pour l'initialisation, plus O ( | V | 3 ) pour la fermeture transitive, plus O ( | E | 2 ) pour la recherche. Le temps total est O ( | V | 2 + | E | | V | + | V |$O(|V|\cdot(|V|+|E|))$$O(|V|^3)$$O(|E|^2)$ .$O(|V|^2+|E||V|+|V|^3+|E|^2) = {\bf O(|V|^3+|E|^2)}$

À la fin du processus, nous obtenons l'ensemble minimal d'arêtes requis pour déconnecter de t tout en préservant au moins un bord extérieur de chaque sommet du graphique (ou nous découvrons qu'une solution est impossible en cours de route et abandonnons).$s$$t$