Die maximale Übereinstimmung M mit der Bedingung G [M] ist 2K_2-frei

11

Gibt es in der Literatur etwas in der Nähe des folgenden Problems:

Gibt es bei einem zweigeteilten Graphen mit ausgeglichener Zweiteiligkeit { U , W } eine perfekt passende M in G, so dass für jeweils 2 Kanten u 1 w 1 , u 2 w 2M eine Kante vorhanden ist u 1 w 2 oder Kante u 2 w 1 (oder beides) in G ?G(V.,E.){U.,W.}}M.Gu1w1,u2w2M.u1w2u2w1G

Mit anderen Worten gibt es eine perfekte Abstimmung , so dass die induzierte Teilgraph G [ M ] ist 2 K 2 -frei. (Mit ausgeglichener Zweiteilung meinte ich | U | = | W | .)M.G[M.]]2K.2|U.|=|W.|

Die zusätzliche Bedingung ist so etwas wie ein entgegengesetztes Extrem zu dem, das beim induzierten Matching-Problem verwendet wird. Ein anderes möglicherweise verwandtes Problem ist das Problem, eine maximale Größenanpassung in dem zweigeteilten Graphen G zu finden, so dass die Kontraktion der Kanten in M die Anzahl der im Graphen verbleibenden Kanten minimiert.M.GM.

Ich habe die Liste der Matching-Probleme von Plummer in Matching und Vertex-Packing überprüft : Wie "schwer" sind sie? ohne Erfolg.

PS: Dieses Problem ist ein Spezialfall dieses Entscheidungsproblem: - Für ein gegebenes gibt es ein maximales Matching M eines zweiteiligen Graphen G , so dass G [ M ] ist 2 K 2 -frei und | M | > k . Wenn der Eingabegraph zweigeteilt ist und k = | U | Wir bekommen das obige Problem.kN.M.GG[M.]]2K.2|M.|>kk=|U|

Vielen Dank.

Cyriac Antony
quelle
perfekte Übereinstimmung kann nicht korrektes Wort sein. Wir fragen grundsätzlich, ob es eine maximale Übereinstimmung mit der Größe mit der Eigenschaft erwähnt. |U.|
Cyriac Antony
In gewissem Sinne bitten wir um etwas Gegenteiliges zu dem, was man als starkes Matching bezeichnet. Ein stark übereinstimmendes in einem Graphen G ist ein übereinstimmendes M, so dass es keine Kante in G gibt, die zwei Kanten von M verbindetM.GM.GM.
Cyriac Antony
Entschuldigung, mit meinte ich den durch Scheitelpunkte induzierten Teilgraphen von G 'in' MG[M.]]GM.
Cyriac Antony

Antworten:

5

Überraschung! (für mich).
Diese Art von Übereinstimmungen ist bereits in der Literatur untersucht. Sie werden als verbundene Übereinstimmungen bezeichnet .

Sie wurden von Plummer, Stiebitz und Toft in ihrer Studie über Hadwiger-Vermutungen vorgestellt. Siehe das Kapitel "Connected Matchings" von Cameron im Buch "Combinatorial Optimization - Eureka, You Shrink!"

Der Status der verbundenen Übereinstimmungen in zweigeteilten Graphen (nicht unbedingt ausgewogen) ist nach bestem Wissen offen ( ich werde aktualisieren ). Die gewichtete Version des Problems ist NP-vollständig für zweigeteilte Graphen. Das Problem ist die polynomielle Zeit, die für zweigeteilte Akkordgraphen lösbar ist.

Update: Das Problem ist NP-vollständig für ausgeglichene zweigeteilte Graphen (dh das genaue Problem, das in der Frage gestellt wird). Dies wird in der Arbeit " Multitasking-Kapazität: Härteergebnisse und verbesserte Konstruktionen " von Alon et al. Sie berichten auch, dass es schwierig ist, die Größe eines größten verbundenen Matchings innerhalb eines Faktors von n1- -ϵ zu approximieren, es sei denn, NP = co-RP.

Zuvor hinzugefügte Anmerkungen (für interessierte Personen aufbewahrt):
" Verbundene Übereinstimmungen in zweigeteilten Akkordgraphen " von Jobson et al. (doi: https://doi.org/10.1016/j.disopt.2014.06.003 ) und " Verbundene Übereinstimmungen in speziellen Familien von Graphen " von Caragianis (These) sind zwei bemerkenswerte Referenzen.

Cyriac Antony
quelle
1

Es gibt einen anderen Weg, diese Frage zu stellen. Gibt es eine perfekt passende eines ausgeglichenen zweigliedrigen Graphen G, so dass jedes Kantenpaar in M in G genau einen Abstand von 1 voneinander hat ? (Der Abstand zwischen den Kanten e und e ' ist die Länge eines kürzesten Weges von einem Scheitelpunkt von e zu einem Scheitelpunkt von e ' ).M.GM.G
ee'ee'

Aus diesem Grund reduziert sich die zusätzliche Bedingung darauf, eine Teilmenge von Scheitelpunkten aus dem Liniendiagramm von G zu finden, die paarweise in einem Abstand von genau 2 liegen. Somit besteht das Problem , einen Satz von Scheitelpunkten maximaler Größe in einem Abstand von genau 2 von jedem zu finden Das andere ist ein Kandidatenproblem (um dem fraglichen Problem nahe zu sein). In der kürzlich erschienenen Arbeit über die algorithmischen Aspekte einer starken Subfärbung (von MA Shalu, S. Vijayakumar, S. Devi Yamini und TP Sandhya) nennen sie dieses Problem eine starke Menge.L.(G)G

Es ist bekannt, dass das Stong-Set-Problem in einigen Graphklassen NP-vollständig ist. Ich kenne seinen Status in Liniendiagrammen von zweiteiligen Diagrammen nicht. Das Papier sagt, dass es auf zweiteiligen Graphen NP-vollständig ist. Unser Interesse wird hier in der Klasse der Liniendiagramme von zweigeteilten Graphen liegen.

Cyriac Antony
quelle
bearbeitet, um einen Fehler zu korrigieren; Ich dachte, Liniendiagramme von zweiteiligen Graphen sind zweiteilig. :)
Cyriac Antony
Ich denke, Ihre Definition des Abstands zwischen Kanten sollte +1 enthalten (nach der aktuellen Definition würden sich die Kanten von M im Abstand 1 befinden, da es eine Kante gibt - einen Pfad der Länge 1 -, die jedes Kantenpaar verbindet von M, aber du meinst eigentlich Abstand 2).
Florent Foucaud
korrigiert es als "Kanten ... sind im Abstand 1 voneinander". Vielen Dank @Florent Foucaud
Cyriac Antony
Das funktioniert, aber jetzt entspricht Ihr "Abstand der Kanten" leider nicht dem Scheitelpunktabstand der entsprechenden Scheitelpunkte im Liniendiagramm.
Florent Foucaud
1
Denken Sie daran, dass eine maximale Übereinstimmung in einem Diagramm einer maximalen unabhängigen Menge in seinem Liniendiagramm entspricht, um die Modellierung Ihrem Problem näher zu bringen. Daher suchen Sie im Liniendiagramm nach einer starken Menge, die auch eine maximale unabhängige Menge ist (insbesondere muss es sich auch um eine dominierende Menge handeln).
Florent Foucaud