Gegeben ein zweigliedriger Graph , in dem es keine perfekte Übereinstimmung gibt, möchte ich eine kleinste Teilmenge finden, die gegen Halls Bedingung verstößt, dh eine Menge mit minimaler Kardinalität für welche .
Dieses Problem ist die Optimierungsversion einer früheren Frage. Finden einer Teilmenge in einem zweigeteilten Graphen, die gegen Halls Bedingung verstößt , von der ich weiß, dass es einen Polynom-Zeit-Algorithmus zum Finden einer solchen gibt. Gibt es einen Polynomalgorithmus für das Optimierungsproblem?
np-hard
matching
bipartite-matching
Y. Zhang
quelle
quelle
Antworten:
Dies ist keine Antwort - nur eine lange Notiz.
Die Frage bezieht sich auf das Problem der minimalen Scheitelpunktabdeckung mit minimaler Überlappung einer Seite . Angenommen, wir haben eine minimale ScheitelpunktabdeckungC von Größe m . Nach dem Satz von König,m entspricht auch der Größe der maximalen Übereinstimmung, also m<n .
Schon seitC ist eine Scheitelpunktabdeckung, jeder Scheitelpunkt nicht in C muss alle seine Nachbarn in haben C . DamitN(X∖C)⊆Y∩C . Daher:
|N(X∖C)|≤|Y∩C|=m−|X∩C|=m−n+|X∖C|<|X∖C|
damit X∖C ist ein Hall-Violator. Nun, wennX∩C ist also groß X∖C ist klein.
Ich bin mir jedoch nicht sicher, ob ich eineC was maximiert X∩C ergibt auch den kleinsten Hallverletzer.
quelle
tl; dr : Ich habe eine fatale Lücke in diesem Beweis gefunden, dass ich nicht schließen konnte. Ich lasse diese Antwort für den Fall, dass entweder: a) ich herausfinde, wie ich sie reparieren kann, oder b) sie jemanden dazu inspiriert, herauszufinden, wie man sie repariert.
LassenG=(X∪Y,E) sei ein zweiteiliger Graph ohne perfekte Übereinstimmung. Wir werden sagen, dass eine TeilmengeS ist mangelhaft, wenn|N(S)|<|S| . Wir suchen nach einer minimalen, mangelhaften Teilmenge vonX . Der allgemeine Ansatz wird Potenzial gering wie möglich zu identifizieren, mangelhafte Sätze durch Charakterisierung (und finden) alle Mini mal , mangelhafte Sätze, das heißt: mangelhaft SätzeS⊂X das enthält keine mangelhaften Teilmengen. Lassen Sie uns einige Beobachtungen zu den Eigenschaften dieser minimalen, mangelhaften Mengen machen.
Beobachtung 1 : Eine TeilmengeS ist eine minimale mangelhafte Teilmenge von X iff für alle s∈S , der Satz S∖{s} hat eine perfekte Übereinstimmung in G . Dies ist nur der Satz von Hall.
Beobachtung 2 : WennS ist eine minimale mangelhafte Teilmenge von X dann für alle s1,s2∈S gibt es einen Pfad in G von s1 zu s2 . Andernfalls könnten wir uns zersetzenS in zwei (oder mehr) Komponenten, von denen mindestens eine mangelhaft sein müsste, was der Minimalität widerspricht.
Lassen Sie uns jetzt behebenM , einige maximale Übereinstimmung in G . LassenX′⊂X und Y′⊂Y seien Sie die Eckpunkte, mit denen übereinstimmen M und lass U=X∖X′ sei die Teilmenge der nicht übereinstimmenden Eckpunkte in X . Für jede TeilmengeS von X werden wir auch bezeichnen m(S) als die Menge der Eckpunkte in G erreichbar von S über M -Änderungspfade.
In einer Antwort auf die im OP verknüpfte Frage sehen wir einen Beweis dafür, dass, wenn wir nehmenS=U∪(m(U)∩X) dann S ist mangelhaft. Das sorgfältige Lesen dieses Beweises zeigt, dass es nicht nur für funktioniertU aber jede Untermenge von U . Das heißt, wenn wir eine Teilmenge nehmenU1⊆U , dann U1∪(m(U1)∩X) ist eine mangelhafte Teilmenge von X . Insbesondere können wir nehmenU1 ein Singleton-Set sein. Für jedenu∈U , lass uns definieren Du={u}∪(m({u})∩X) .
Lemma 1 :Du ist ein minimaler, mangelhafter Satz für alle u∈U .
Beweis : Das nehmen wir als selbstverständlich anDu ist durch den in der zuvor genannten Antwort angegebenen Beweis mangelhaft. Zu zeigen, dassDu Ist ein minimaler Mangel an Wrt, beobachten wir das Du∖{u} ist einfach eine Teilmenge von X′ , daher gibt es eine perfekte Übereinstimmung innerhalb von G (Nehmen Sie einfach die Einschränkung von M zu Du∖{u} ). Für jeden andereny∈Du Wir folgen dem M -Änderungspfad von y zu u Drehen Sie alle Kanten entlang dieses Pfades um und erhalten Sie eine perfekte Übereinstimmung von Du∖{y} im G . Also, durch Beobachtung 1,Du ist ein minimaler, mangelhafter Satz. □
Ok, jetzt, da wir eine Sammlung von minimalen, mangelhaften Teilmengen von identifiziert habenX müssen wir fragen: was ist mit anderen?
Um eine kleine Struktur hinzuzufügen, betrachten wir eine beliebige MengeS⊆X in der Form sein S=U1∪Z1∪Z2 wo U1⊆U , Z1⊆m(U1) und Z2⊆X′∖m(U1) . Mit anderen Worten, wir brechenS in den Teil, der von nicht erreicht wird M (U1 ), der Teil, der von erreichbar ist U1 über M -wechselnde Pfade (Z1 ) und der Teil, der nicht erreichbar ist U1 über M -wechselnde Pfade (Z2 ). Es ist trivial zu beobachten, obS ist also eine mangelhafte Menge U1 darf nicht leer sein.
Über Lemma 1 haben wir den Fall behandelt, in demZ1=m(U1) und Z2 ist leer. Dies lässt drei Fälle zu untersuchen:
Lemma 2 : Wenn ist so , dass , dann ist nicht minimal, defiziente Teilmenge von .S=U1∪Z1∪Z2⊆X Z2≠∅ S X
Beweis : Sei die Elemente von , die mit in übereinstimmen . Per Definition kann es keine Kanten von oder zu da dies einen alternierenden Pfad von zu Eckpunkten in implizieren würde .M(Z2) Y Z2 M U1 Z1 M(Z2) M U1 Z2
Wenn eine minimale, mangelhafte Menge ist, hat jede Teilmenge von eine vollständige Übereinstimmung. Insbesondere hat eine vollständige Übereinstimmung, beispielsweise . Durch unsere vorherige Beobachtung stellen wir fest, dass diese vollständige Übereinstimmung keinen der Eckpunkte in . Somit ist die Übereinstimmung, die unter Verwendung von zur Übereinstimmung von und zur Übereinstimmung von wird, eine vollständige Übereinstimmung für , was der Annahme widerspricht, dass mangelhaft war.S S U1∪Z1 M1 M1 M(Z2) M1 U1∪Z1 M Z2 S S □
In einer früheren Version dieser Antwort hatte ich Fall 2) vernachlässigt, unter der Annahme, dass er während des Beweises von Lemma 1 irgendwie abgedeckt wurde. Dies ist jedoch nicht der Fall. Es kann minimale, mangelhafte Mengen geben, die nicht wie aussehen . Das folgende Diagramm zeigt ein solches Beispiel. Wenn wir die fettgedruckten Kanten als übereinstimmendes , können wir sehen, dass eine minimale, mangelhafte Menge ist und nicht die Form . Ich konnte noch keine effektive Charakterisierung von minimalen mangelhaften Mengen finden, die in Fall 2 fallen, daher kann ich diesen Beweis derzeit nicht vervollständigen.Du M S={A,B,C} Du
quelle