Finden Sie einen Hall-Violator mit minimaler Kardinalität

7

Gegeben ein zweigliedriger Graph (X,YE), 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 SX für welche |N(S)|<|S|.

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 gibtSX. Gibt es einen Polynomalgorithmus für das Optimierungsproblem?

Y. Zhang
quelle
Es ist auch interessant, einen Hall-Violator mit maximaler Kardinalität zu finden .
Erel Segal-Halevi
2
Es ist auch interessant, einen der am meisten verletzenden Hall-Übertreter zu finden, nämlich SX für welche |S||N(S)|nimmt Maximalwert.
John L.
Es könnte am interessantesten sein, eine Reihe von Kanten mit der geringsten Kardinalität oder nur der geringsten Kardinalität zu finden, sodass nach dem Hinzufügen dieser Kanten eine perfekte Übereinstimmung möglich ist.
John L.

Antworten:

2

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 seit C ist eine Scheitelpunktabdeckung, jeder Scheitelpunkt nicht in C muss alle seine Nachbarn in haben C. DamitN(XC)YC. Daher:

|N(XC)||YC|=m|XC|=mn+|XC|<|XC|
damit XCist ein Hall-Violator. Nun, wennXC ist also groß XC ist klein.

Ich bin mir jedoch nicht sicher, ob ich eine C was maximiert XC ergibt auch den kleinsten Hallverletzer.

Erel Segal-Halevi
quelle
1

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.


Lassen G=(XY,E)sei ein zweiteiliger Graph ohne perfekte Übereinstimmung. Wir werden sagen, dass eine TeilmengeSist 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ätzeSXdas 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 sS, 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 Xdann für alle s1,s2Sgibt 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 beheben M, einige maximale Übereinstimmung in G. LassenXX und YY seien Sie die Eckpunkte, mit denen übereinstimmen M und lass U=XX sei die Teilmenge der nicht übereinstimmenden Eckpunkte in X. Für jede TeilmengeS von Xwerden 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 Sist 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 nehmenU1U, dann U1(m(U1)X) ist eine mangelhafte Teilmenge von X. Insbesondere können wir nehmenU1ein Singleton-Set sein. Für jedenuU, lass uns definieren Du={u}(m({u})X).

Lemma 1 :Du ist ein minimaler, mangelhafter Satz für alle uU.

Beweis : Das nehmen wir als selbstverständlich anDuist 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 anderenyDuWir folgen dem M-Änderungspfad von y zu uDrehen 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 haben Xmüssen wir fragen: was ist mit anderen?

Um eine kleine Struktur hinzuzufügen, betrachten wir eine beliebige Menge SX in der Form sein S=U1Z1Z2 wo U1U, Z1m(U1) und Z2Xm(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 dem Z1=m(U1) und Z2ist leer. Dies lässt drei Fälle zu untersuchen:

  1. Z2 ist nicht leer
  2. |U1|>1 und Z1m(U1)
  3. Z1 und sind beide leer (dh: ).Z2SU

Lemma 2 : Wenn ist so , dass , dann ist nicht minimal, defiziente Teilmenge von .S=U1Z1Z2XZ2SX

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)YZ2MU1Z1M(Z2)MU1Z2

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. SSU1Z1M1M1M(Z2)M1U1Z1MZ2SS

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.DuMS={A,B,C}Du

Geben Sie hier die Bildbeschreibung ein

mhum
quelle
Ich habe diese schöne Antwort gerade bemerkt. Eine Frage zur Klarstellung: Kann "M-Wechselweg" eine einzige Kante haben? Es scheint, dass jede einzelne Kante, ob in M ​​oder nicht, technisch "M-alternierend" ist. Wenn ja, dann kann Fall 1 von Lemma 2 viel kürzer gemacht werden: Wenn von , dann ist es in ; Zwischen ihm und befindet sich eine einzelne Kante , sodass von aus zugänglich ist . v2MU1zzU1
Erel Segal-Halevi
Andererseits habe ich Fall 2 von Lemma 2 nicht verstanden: Was ist, wenn alle mit übereinstimmen , aber im Pfad sind sie durch Kanten verbunden, die nicht in ? Dann können wir einen M-Wechselweg von nach , der sich jedoch nicht auf einen M-Wechselweg von nach . z,v2,v3MMv2uzu
Erel Segal-Halevi
@ ErelSegal-Halevi In Bezug auf Ihren ersten Kommentar bin ich mir nicht sicher, ob ich das vollständig verstehe. müsste ein Element von damit es nicht in und es nicht unbedingt eine Kante zwischen und . Was Ihren zweiten Kommentar betrifft, denke ich, dass Sie einen Punkt haben. Ich konnte diesen Teil des Beweises nicht reproduzieren. Ich muss diesen Teil überdenken und sehen, ob ich ihn retten kann. v2YU1v2U1
mhum
zum ersten Kommentar: In der Tat habe ich nicht bemerkt, dass in , danke für die Klarstellung. v2Y
Erel Segal-Halevi
1
@ ErelSegal-Halevi Ich habe gute und schlechte Nachrichten. Die gute Nachricht ist, dass ich die Lücke im Beweis reparieren konnte, den Sie mit einer viel einfacheren Beobachtung identifiziert haben. Die schlechte Nachricht ist, dass ich bei der Überprüfung meiner Arbeit ein viel größeres Problem gefunden habe, das ich noch nicht beheben konnte.
mhum