Problem parzystości Matroidu

Przykład problemu parzystości matroidu na matroidzie graficznym : mając wykres z kolorowymi krawędziami, mający dokładnie dwie krawędzie na kolor, znajdź możliwie największy las, który również ma dokładnie dwie krawędzie na kolor.

W optymalizacji kombinatorycznej problem parzystości matroidu jest problemem znalezienia największego niezależnego zbioru sparowanych elementów w matroidzie . Problem został sformułowany przez Lawlera (1976) jako powszechne uogólnienie dopasowywania grafów i przecięcia matroidów . Nazywa się to również polimatroidalnym lub problemem matchoidowym .

Parzystość matroidów można rozwiązać w czasie wielomianowym dla matroidów liniowych . Jednakże jest to NP-trudne dla niektórych matroidów o zwartej reprezentacji i wymaga więcej niż wielomianowej liczby kroków w modelu matroidowej wyroczni .

Zastosowania algorytmów parzystości matroidowej obejmują znajdowanie dużych podgrafów planarnych i znajdowanie osadzania grafów maksymalnego rodzaju . Algorytmów tych można również użyć do znalezienia połączonych zbiorów dominujących i zbiorów wierzchołków sprzężenia zwrotnego na grafach maksymalnego stopnia trzeciego.

Sformułowanie

Matroidę można zdefiniować na podstawie skończonego zbioru elementów i pojęcia, co to znaczy, że podzbiory elementów są niezależne, z zastrzeżeniem następujących ograniczeń :

• Każdy podzbiór niezależnego zbioru powinien być niezależny.
• Jeśli $zbiorami$$są$ niezależnymi to $,$$niezależny$$_$ element taki _

Przykładami matroidów są matroidy liniowe (w których elementami są wektory w przestrzeni wektorowej z liniową niezależnością ), matroidy graficzne (w których elementami są krawędzie grafu nieskierowanego , niezależne, gdy nie zawierają one cyklu ) oraz podział matroidy (w których elementy należą do rodziny zbiorów rozłącznych i są niezależne, gdy zawierają co najwyżej jeden element w każdym zbiorze). Matroidy graficzne i matroidy podziału są specjalnymi przypadkami matroidów liniowych.

W problemie parzystości matroidu wejście składa się z matroidu wraz z parowaniem jego elementów, tak że każdy element należy do jednej pary. Celem jest znalezienie jak największego podzbioru par, tak aby suma par w wybranym podzbiorze była niezależna. Inna pozornie bardziej ogólna odmiana, w której dozwolone pary tworzą wykres, a nie tylko jedna para na element, jest równoważna: element występujący w więcej niż jednej parze można zastąpić wieloma kopiami elementu, po jednej na parę.

Algorytmy

$Problem$$dla$ matroidów można rozwiązać za pomocą losowego algorytmu czasie $granicach$ matroidu to jego ranga (rozmiar największego niezależnego zbioru), a $wykładnik$ czasowych szybkiego mnożenia macierzy . $,$ macierzy Le Galla, można go rozwiązać w czasie Bez stosowania szybkiego mnożenia macierzy, liniowy problem parzystości matroidu można rozwiązać w czasie. ${\ displaystyle O (nr ^ {2})$ }

Algorytmy te opierają się na sformułowaniu problemu przez algebrę liniową autorstwa Geelena i Iwaty (2005) . Załóżmy, że dane wejściowe do problemu składają się z par $}$ -wymiarowych (ułożonych jako $wektory$ kolumnowe w macierzy o rozmiarze $displaystyle$$\razy 2m}$$r$ ). Wtedy liczba par w rozwiązaniu optymalnym wynosi

${\ Displaystyle {\ Frac {1} {2}} \ operatorname {rank} {\ początek {pmatrix} 0 i M \\ M ^ {T} i T \ koniec {pmatrix }}-M,}$

gdzie jest macierzą diagonalną blokową ${\$ której bloki są podmacierzami postaci $T$

${\ Displaystyle {\ początek {pmatrix} 0 i t_ {i} \\ -t_ {i} i 0 \ koniec {pmatrix}}}$

dla sekwencji zmiennych ${1}, \ kropki t_ {m}}$ t_ Lemat Schwartza – Zippela można zastosować do sprawdzenia, czy ta macierz ma pełny rząd, czy nie $nie ),$ to znaczy, czy rozwiązanie ma rozmiar, losowe wartości zmiennym $,$ czy otrzymana macierz ma wyznacznik zero. Stosując zachłanny algorytm który usuwa pary pojedynczo, ustawiając ich nieokreślone wartości na zero, dopóki macierz pozostaje w pełnym randzie (zachowując macierz odwrotną za pomocą wzoru Shermana- Morrisona, aby sprawdzić rząd po każdym usunięciu), można znaleźć rozwiązanie za każdym razem, gdy ten test pokazuje, że istnieje. Dodatkowe $,$ gdy optymalne rozwiązanie problemu parzystości matroidu ma mniej .

$} \displaystyle n}$$na$${\ displaystyle O (mn$ czasem działania wykresach z i krawędzie. W przypadku prostych wykresów jest O $\$$Displaystyle O (n ^ {2})}$ , ale w multigrafów , może być większy, więc interesujące jest również posiadanie algorytmów z mniejszą zależnością lub żadną zależnością $od$ i $.$ zależnością $displaystyle O ( n^{3})}$$O$ również rozwiązanie graficznego problemu parzystości matroidu w losowo oczekiwanym czasie w czasie gdy każda para krawędzi tworzy ścieżkę.

Chociaż problem parzystości matroidów jest NP-trudny dla dowolnych matroidów, nadal można go skutecznie przybliżyć. Proste algorytmy wyszukiwania lokalnego zapewniają schemat aproksymacji tego problemu w czasie wielomianowym i znajdują rozwiązania, których rozmiar, jako ułamek rozmiaru rozwiązania optymalnego, jest dowolnie bliski jedności. Algorytm zaczyna od pustego zbioru jako rozwiązania i wielokrotnie próbuje zwiększyć rozmiar rozwiązania o jeden, usuwając co najwyżej stałą liczbę. do $\ displaystyle C}$ par z rozwiązania i zastąpienie ich innym zestawem jeszcze jedną parą. Gdy nie jest już możliwe więcej takich ruchów, wynikowe rozwiązanie jest zwracane jako przybliżenie rozwiązania optymalnego. $osiągnąć$ współczynnik przybliżenia $5$$epsilon \rceil }}$ wybrać około ${\ displaystyle 5 ^$ .

Aplikacje

Wiele innych problemów optymalizacyjnych można sformułować jako problemy liniowej parzystości matroidowej i rozwiązać w czasie wielomianowym przy użyciu tego sformułowania.

Dopasowywanie grafów

Maksymalne dopasowanie na grafie to podzbiór krawędzi (żadnych dwóch nie ma wspólnego punktu końcowego), który jest możliwie największy. Można go sformułować jako problem parzystości matroidu w matroidzie podziału, która ma element dla każdego wystąpienia krawędzi wierzchołkowej na wykresie. W tej matroidzie dwa elementy są sparowane, jeśli są to dwa przypadki dla tej samej krawędzi. Podzbiór elementów jest niezależny, jeśli ma co najwyżej jedno wystąpienie na każdy wierzchołek grafu. Pary elementów w rozwiązaniu problemu parzystości matroidu dla tej matroidy to częstości występowania pomiędzy krawędziami w maksymalnym dopasowaniu i ich punktami końcowymi.

Przecięcie Matroidu

Przykład problemu przecięcia matroidów składa się z dwóch matroidów w tym samym zestawie elementów; celem jest znalezienie jak największego i niezależnego podzbioru elementów w obu matroidach. Aby sformułować przecięcie matroidu jako problem parzystości matroidu, skonstruuj nową matroidę, której elementy są rozłączną sumą dwóch kopii danych elementów, po jednej dla każdej matroidy wejściowej. W nowej matroidzie podzbiór jest niezależny, jeśli jego ograniczenie do każdej z dwóch kopii jest niezależne odpowiednio w każdej z dwóch matroid. Połącz elementy nowego matroidu tak, aby każdy element był sparowany ze swoją kopią. Pary elementów w rozwiązaniu problemu parzystości matroidu dla tej matroidy to dwie kopie każdego elementu w rozwiązaniu problemu przecięcia matroidu.

Duże planarne podgrafy

Na dowolnym grafie problem znalezienia największego zbioru trójkątów na danym grafie, bez cykli innych niż wybrane trójkąty, można sformułować jako matroidowy problem parzystości na graficznej matroidzie, której elementami są krawędzie grafu, z jednym parę krawędzi na trójkąt (w razie potrzeby powielając krawędzie, gdy należą one do więcej niż jednego trójkąta). Pary elementów rozwiązania problemu parzystości matroidu dla tej matroidy to dwie krawędzie każdego trójkąta optymalnego zestawu trójkątów. Ten sam problem można również opisać jako znalezienie największego podhipergrafu Berge'a w 3-jednostajnym hipergrafie . W hipergraficznej wersji problemu hiperkrawędziami są trójkąty danego wykresu.

Wykres kaktusowy to wykres, w którym każde dwa cykle mają co najwyżej jeden wspólny wierzchołek. W szczególnym przypadku wykresy, w których każdy cykl jest trójkątem, są z konieczności wykresami kaktusowymi. Największy trójkątny kaktus na danym wykresie można następnie znaleźć, dodając dodatkowe krawędzie z drzewa rozpinającego , bez tworzenia nowych cykli, tak aby powstały podgraf miał te same połączone elementy, co pierwotny wykres. Wykresy kaktusów są automatycznie grafami planarnymi , a problem znalezienia trójkątnych wykresów kaktusów stanowi podstawę najbardziej znanego algorytmu aproksymacyjnego do problemu znalezienia największego podgrafu planarnego danego grafu, ważny krok w planaryzacji . Największy trójkątny kaktus ma zawsze co najmniej 4/9 liczby krawędzi największego płaskiego podgrafu, co poprawia współczynnik aproksymacji o 1/3 uzyskany za pomocą dowolnego drzewa rozpinającego.

Sztywność kombinatoryczna

Szkielet ze sztywnych prętów w płaszczyźnie euklidesowej , połączonych w punktach końcowych elastycznymi przegubami, można unieruchomić w jednym położeniu na płaszczyźnie, przypinając niektóre jego połączenia do punktów płaszczyzny. Minimalna liczba połączeń, które należy unieruchomić w celu zamocowania szkieletu, nazywana jest jego liczbą przypinania. Można go obliczyć na podstawie rozwiązania powiązanego problemu parzystości matroidu.

Osadzenia maksymalnego rodzaju

Drzewo Xuong

Komórkowe osadzenie danego wykresu na powierzchni maksymalnego możliwego rodzaju można uzyskać z drzewa Xuong wykresu. Jest to drzewo rozpinające, którego właściwość polega na tym, że w podgrafie krawędzi nie znajdujących się w drzewie liczba połączonych elementów o nieparzystej liczbie krawędzi jest możliwie najmniejsza.

Aby sformułować problem znalezienia drzewa Xuong jako problemu parzystości matroidu, najpierw podziel każdą krawędź ${\ displaystyle e$ wykresu na ścieżkę, której długość jest równa liczbie innych krawędzi przypadających na $} \displaystyle e}$ . Następnie połącz krawędzie podzielonego wykresu w taki sposób, aby każda para krawędzi na pierwotnym wykresie była reprezentowana przez pojedynczą parę krawędzi na podzielonym wykresie, a każda krawędź na podzielonym wykresie była sparowana dokładnie raz. Rozwiąż problem parzystości matroidu z sparowanymi krawędziami podzielonego wykresu, korzystając z jego matroidy cograficznej (matroidy liniowej, w której podzbiór krawędzi jest niezależny, jeśli jego usunięcie nie oddziela wykresu). Każde drzewo rozpinające oryginalnego grafu, które unika krawędzi używanych w rozwiązaniu parzystości matroidowej, jest z konieczności drzewem Xuong.

Dominacja spójna

Spójny zbiór dominujący w grafie to podzbiór wierzchołków, których podgraf indukowany jest spójny, sąsiadując ze wszystkimi pozostałymi wierzchołkami. Znalezienie najmniejszego połączonego zbioru dominującego na dowolnych grafach jest NP-trudne, ale można je znaleźć w czasie wielomianowym dla grafów maksymalnego stopnia trzeciego. Na wykresie sześciennym , można zastąpić każdy wierzchołek ścieżką o dwóch krawędziach połączoną z końcami jego trzech punktów końcowych i sformułować problem parzystości matroidów na tak wygenerowanych parach krawędzi, korzystając z matroidy cograficznej rozwiniętego grafu. Wierzchołki, których ścieżki nie są wykorzystywane w rozwiązaniu, tworzą minimalny spójny zbiór dominujący. Na wykresie maksymalnego stopnia trzeciego pewne proste dodatkowe przekształcenia redukują problem do jednego na wykresie sześciennym.

Zbiór wierzchołków sprzężenia zwrotnego

Zestaw wierzchołków sprzężenia zwrotnego na wykresie to podzbiór wierzchołków, który dotyka wszystkich cykli. W grafach sześciennych istnieje równanie liniowe odnoszące się do liczby wierzchołków, liczba cyklomatyczna , liczba połączonych składników, rozmiar minimalnego połączonego zbioru dominującego i rozmiar minimalnego zbioru wierzchołków sprzężenia zwrotnego. Wynika z tego, że ten sam matroidalny problem parzystości, który został użyty do znalezienia połączonych zbiorów dominujących, może być również użyty do znalezienia zbiorów wierzchołków sprzężenia zwrotnego na grafach maksymalnego stopnia trzeciego.

Twardość

Problem kliki $można$ na znalezieniu pełnego podgrafu -vertex na danym wykresie -vertex , przekształcić $przykład$ parzystości matroidu w następujący $.$ Zbuduj matroid chodnikowy $sparowanych$ elementach tak, aby na parę wierzchołków przypadała jedna para elementów. Zdefiniuj podzbiór ${\ displaystyle S}$ tych elementów za niezależny, jeżeli spełnia jeden z trzech poniższych warunków:

• $ma$ niż $_$ _
• $ma$ dokładnie $.$ , ale nie $jest$ elementów
• $jest$ połączeniem elementów, $które$$tworzą$ .

Następnie istnieje rozwiązanie problemu parzystości matroidu dla tego matroidu o rozmiarze $o$$gdy$ i tylko wtedy , klikę $. Ponieważ znajdowanie klik o danym rozmiarze jest NP-zupełne, wynika$$z$ tego, że określenie, czy ten typ problemu parzystości macierzy ma rozwiązanie o rozmiarze NP-zupełne.

Ta transformacja problemu nie zależy w żaden głęboki sposób od struktury problemu kliki i działałaby w przypadku każdego innego problemu znajdowania podzbiorów rozmiaru $zbioru$ , które spełniają test obliczeniowy. Stosując to do losowo permutowanego wykresu, który zawiera dokładnie jedną klikę o rozmiarze , można wykazać, że każdy deterministyczny lub losowy algorytm parzystości matroidu, który uzyskuje dostęp do swojego matroidu tylko na podstawie testów niezależności, musi wykonać wykładniczą liczbę k {\ displaystyle $}$ testy.