Finden Sie heraus, welche Scheitelpunkte aus dem Diagramm gelöscht werden sollen, um die kleinste größte Komponente zu erhalten

8

Wenn ein Graph G=(V,E) , finden Sie k Eckpunkte {v1,,vk} , deren Entfernung zu einem Graph mit der kleinsten größten Komponente führen würde.

Ich nehme für große n=|V|und groß k das Problem schwierig (NP-hart), aber ich interessiere mich für kleine Werte von k ( k{1,2,3,4} ).

Für k=1 ist es meines Erachtens möglich, den besten zu entfernenden Scheitelpunkt {v1} zu finden, indem eine einzelne Tiefensuche des Graphen durchgeführt wird (dh Artikulationspunkte überprüft werden).

Für k=2 wäre es möglich, die besten Eckpunkte {v1,v2} indem n Tiefensuchen durchgeführt werden (jede davon für den Graphen Gi=G/{vi} ). Ein ähnlicher Ansatz könnte im Fall angewendet werden k>2.

Ich frage mich, ob es eine bessere Lösung gibt.

(Verwandte: Zählen der minimalen Anzahl von Scheitelpunkten, ohne sie unbedingt aufzuzählen )

MindaugasK
quelle
Nun, es verallgemeinert die Scheitelpunktabdeckung, die nach Scheitelpunkten S = { v 1 , , fragt.so dass G - S eine größte Komponente der Singleton-Größe hat. S={v1,,vk}GS
Pål GD
Ps., Ein parametrisierter Algorithmus ist ein FPT-Algorithmus, wenn er für einige c in der Zeit läuftf(k)ncc , und ein Algorithmus ist ein XP-Algorithmus, wenn er in läuft . nf(k)
Pål GD
Können Sie uns weitere Informationen geben? Der Hintergrund dieses Problems interessiert mich sehr.
Pål GD
Ich war mit diesem Problem konfrontiert, als ich nach maximal gemeinsamem Teilgraphen von zwei Graphen suchte. Überprüfen Sie die Kommentare in Ihrer Antwort :)
MindaugasK

Antworten:

9

Das von Ihnen beschriebene Problem wird im Bereich der Schwachstellenmaße von Diagrammen als Komponentenordnungskonnektivität bezeichnet . Die Entscheidungsversion des Problems lautet wie folgt:

Konnektivität der Komponentenreihenfolge :

Eingabe: Graph , ganze Zahlen k und G=(V,E)k

Frage: Gibt es eine Reihe von Eckpunkten einer Größe von höchstens k, so dass die Größe der größten Komponente von G - X höchstens beträgt?XVkGX

Das Problem ist offensichtlich NP-vollständig, da es die Scheitelpunktabdeckung verallgemeinert; der Fall, wenn ist, ist die Scheitelpunktabdeckung. Daher kann das Problem nicht behoben werden, wenn der Parameter durch parametrisiert wird (es sei denn, F P T = W [ 1 ] ). Es ist auch bekannt, dass das Problem W [ 1 ] -hart ist, wenn es durch k parametrisiert wird . Daher müssen wir auf Algorithmen mit einer exponentiellen Laufzeit in k + zurückgreifen .=1FPT=W[1]W[1]kk+

Sehr interessante Frage. Für die Eingabe ein Brute-Force-Ansatz:G,k,

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

Der Algorithmus läuft in der Zeit .(+1)kn2

Beachten Sie, dass jede Ja-Instanz des Problems eine Baumbreite und tatsächlich eine Pfadbreite von höchstens k + ℓ hat . Dies kann durch Sehen , dass die Einnahme einer Deletion Satz beobachtet wird X der Größe höchstens k ergibt einen Graphen G - X wo jede verbundene Komponente Größe höchstens hat l . Daher besteht eine gültige Pfadzerlegung darin, einfach einen Beutel für jede der Komponenten in G - zu konstruieren.G,k,k+XkGXund dannjedem Beutel dasgesamte X hinzuzufügen. Daraus folgt, dass jede yes-Instanz | hat E ( G ) |GXX .|E(G)|n(k+)

Ein verwandtes Problem wurde in der Vergangenheit unter dem Namen Graph Integrity oder Vertex Integrity untersucht, um die Vertex-Löschversion und die Kantenlöschversion zu unterscheiden:

Vertex-Integrität :

Eingabe: Graph , ganze Zahl pG=(V,E)p

Frage: Gibt es eine Menge von Eckpunkten so dass | X | + max D c c ( G - X ) | D | p ?XV|X|+maxDcc(GX)|D|p

Das heißt, die Summe aus dem Löschsatz und der Größe der maximalen Komponente sollte minimiert werden. Dieses Problem ist auch NP-schwer. Siehe z.

  • Clark, LH, Entringer, RC, Fellows, MR: Rechenkomplexität der Integrität. J. Combin. Mathematik. Combin. Comput 2, 179–191 (1987)
  • Fellows, M., Stueckle, S.: Die Immersionsreihenfolge, verbotene Untergraphen und die Komplexität der Netzwerkintegrität. J. Combin. Mathematik. Combin. Comput 6, 23–32 (1989)
Pål GD
quelle
Nun, eigentlich arbeite ich mit chemischen Graphen, die mit sehr hoher Wahrscheinlichkeit planar sind.
MindaugasK
Dann können Sie den Satz des planaren Separators (Lipton und Tarjan) überprüfen, der besagt, dass Sie ausgeglichenes Trennzeichen. O(n)
Pål GD
Ich habe dieses Problem gelöst, wie ich in der Frage vorgeschlagen habe, indem ich getan habe V | + 1- Tiefe-zuerst-Suche (eine zum Finden von Artikulationspunkten, | V | zum Finden von Paaren von Artikulationspunkten). Die maximale Komponente chemischer Graphen (Moleküle), die spärlich sind, kann häufig ausreichend klein gemacht werden, indem nur 1-2 Atome (Eckpunkte) gelöscht werden (mit seltenen Ausnahmen). Ich suchte keine optimale Lösung, ich wollte nur 1, 2 oder 3 Atome, deren Entfernung das Molekül in kleine Stücke "schneiden" würde, und DFS war ausreichend. |V|+1|V|
MindaugasK
Eigentlich war das Problem, das ich in der Frage angegeben habe, nicht genau das, das ich lösen wollte. Jedem Scheitelpunkt waren auch Gewichte zugeordnet. Daher wollte ich Eckpunkte auswählen, die nicht nur zu einer kleinen größten Komponente führen, sondern auch eine kleine Gewichtssumme.
MindaugasK
Dies an sich war ein Teilproblem eines anderen Problems: Finden Sie die maximale gemeinsame zusammenhängende Substruktur von 2 gegebenen Molekülen (finden Sie die maximale gemeinsame verbundene induzierte Unterstruktur von 2 Graphen). Nachdem Sie ein einzelnes Atom von einem Molekül mit allen möglichen Zuordnungen von einem anderen abgebildet haben, können Sie dieses Atom aus der Betrachtung entfernen, und es ist schön, wenn es das Molekül "schneidet". Vielleicht sollte ich dies als eine andere Frage angeben.
MindaugasK