Maksymalne dopasowanie M z warunkiem G [M] jest wolne od 2K_2

Czy w literaturze jest coś zbliżonego do następującego problemu:

Biorąc pod uwagę dwuczęściowy wykres ze zrównoważonym dwuczęściowym , czy istnieje idealne dopasowanie w tak że dla każdej 2 krawędzi występuje krawędź lub krawędź (lub oba) w ?$G(V,E)$$\{U,W\}$$M$$G$$u_1w_1, u_2w_2\in M$$u_1w_2$$u_2w_1$$G$

Innymi słowy, czy istnieje idealne dopasowanie tak że indukowany podgrupa jest . (Ze zrównoważonym dwuczęściowym miałem na myśli .)$M$$G[M]$$2K_2$$|U|=|W|$

Dodatkowy warunek jest czymś w rodzaju przeciwnej skrajności niż w przypadku indukowanego problemu dopasowania. Innym potencjalnie powiązanym jest problem znalezienia maksymalnego rozmiaru pasującego na grafie dwustronnym tak że skurcz krawędzi w minimalizuje liczbę krawędzi pozostałych na wykresie.$M$$G$$M$

Sprawdziłem listę problemów związanych z dopasowywaniem podanych przez Plummer w Dopasowywaniu i pakowaniu wierzchołków: jak „twarde” są? bezskutecznie.

PS: Ten problem jest szczególnym przypadkiem tego problemu decyzyjnego: - Dla danego , czy istnieje maksymalne dopasowanie grafu dwustronnego tak że wynosi i . Jeżeli wykres wejściowy jest zbalansowany dwustronny, aotrzymujemy powyższy problem.$k\in\mathbb{N}$$M$$G$$G[M]$$2K_2$$|M|>k$$k=|U|$

Dziękuję Ci.

Niespodzianka! (dla mnie).
Ten rodzaj dopasowań jest już badany w literaturze. Nazywa się je połączonymi dopasowaniami .

Zostali przedstawieni przez Plummer, Stiebitz i Toft w swoich badaniach nad hipotezą Hadwigera. Zobacz rozdział „Połączone dopasowania” Camerona w książce „Optymalizacja kombinatoryczna - Eureka, ty się kurczysz!”

Status połączonych dopasowań w grafach dwustronnych (niekoniecznie zbalansowanych) jest otwarty według mojej najlepszej wiedzy ( zaktualizuję ). Ważona wersja problemu jest NP-kompletna dla grafów dwustronnych. Problem polega na rozwiązaniu czasu wielomianowego dla dwuwartościowych grafów akordowych.

Aktualizacja: problem jest NP-kompletny dla zrównoważonych grafów dwustronnych (tj. Dokładnie problem zadany w pytaniu). Zostało to udowodnione w pracy „ Wielozadaniowość: wyniki twardości i ulepszone konstrukcje ” autorstwa Alon i in. Informują również, że znalezienie wielkości największego połączonego dopasowania jest trudne do przybliżenia w granicach chyba że NP = co-RP.$n^{1-\epsilon}$

Uwagi dodane wcześniej (zachowane dla zainteresowanych osób):
„ Połączone dopasowania na akordach dwustronnych grafów ” Jobsona i in. (doi: https://doi.org/10.1016/j.disopt.2014.06.003 ) i „ Połączone dopasowania w specjalnych rodzinach wykresów ” Caragianisa (teza) to dwa godne uwagi odniesienia.

Istnieje inny sposób zadawania tego pytania. Czy istnieje idealne dopasowanie?$M$ zrównoważonego wykresu dwudzielnego $G$ tak, że każda para krawędzi w $M$ jest dokładnie w odległości 1 od siebie w $G$?
(Odległość między krawędziami$e$ i $e’$ jest długością najkrótszej ścieżki od wierzchołka $e$ do wierzchołka $e’$).

Dzięki temu dodatkowy warunek ogranicza się do znalezienia podzbioru wierzchołków z wykresu liniowego $L(G)$ z $G$które są parami w odległości dokładnie 2. Zatem problem znalezienia zestawu maksymalnego rozmiaru wierzchołków w odległości dokładnie 2 od siebie jest problemem potencjalnym (być blisko problemu). W najnowszym artykule na temat algorytmicznych aspektów silnego podkolorowania (MA Shalu, S. Vijayakumar, S. Devi Yamini i TP Sandhya) nazywają ten problem silnym zestawem.

Wiadomo, że problem zestawu sztywnego jest NP-zupełny w niektórych klasach grafów. Nie znam jego statusu na liniowych wykresach dwudzielnych. Artykuł mówi, że jest on NP-kompletny na grafach dwustronnych. Naszym zainteresowaniem będzie tutaj klasa grafów liniowych grafów dwustronnych.