Relacje równoważności obejmują problem (w teorii grafów)

Relację równoważności na skończonym zestawie wierzchołków można przedstawić za pomocą nieukierunkowanego wykresu, który jest rozłącznym połączeniem klików. Zestaw wierzchołków reprezentuje elementy, a krawędź reprezentuje równoważność dwóch elementów.

Jeśli mam wykres i wykresy , mówimy, że jest objęty jeśli zbiór krawędzi jest równy zjednoczeniu zbiorów krawędzi . Zestawy krawędzi nie muszą być rozłączne. Zauważ, że każdy niekierowany wykres $G$ $G_1,\dots,G_k$ $G$ $G_1,\dots,G_k$ $G$ $G_1,\dots,G_k$ $G_1,\dots,G_k$ $G$ może być objęty skończoną liczbą relacji równoważności (tj. rozłącznym połączeniem wykresów klików).

Mam kilka pytań:

Co można powiedzieć o minimalnej liczbie relacji równoważności wymaganych do pokrycia wykresu ? $G$
Jak obliczyć tę minimalną liczbę?
Jak obliczyć wyraźne minimalne pokrycie , tj. Zestaw relacji równoważności, których rozmiar jest minimalny, a który obejmuje ? $G$ $G$
Czy ten problem ma jakieś zastosowania oprócz logiki partycji ( dualność logiki podzbiorów )?
Czy ten problem ma dobrze ustaloną nazwę?

Biorąc pod uwagę różne nieporozumienia wskazane w komentarzach, oto kilka zdjęć ilustrujących te pojęcia. Jeśli masz pomysł na łatwiejszą do zrozumienia terminologię (zamiast „pokrycia”, „relacji równoważności”, „rozłącznego połączenia kliki” i „niekoniecznie rozłącznego” połączenia zestawów krawędzi), daj mi znać.

Oto obraz wykresu i jednej relacji równoważności obejmującej go: wykres i jedna relacja równoważności pokrywająca go

Oto obraz wykresu i obejmujących go dwóch relacji równoważności: wykres i dwie relacje równoważności obejmujące go
Powinno być całkiem oczywiste, że wymagane są co najmniej dwie relacje równoważności.

Oto obraz wykresu i obejmujących go trzech relacji równoważności: wykres i trzy relacje równoważności obejmujące go
Mniej oczywiste jest, że wymagane są co najmniej trzy relacje równoważności. Można użyć Lemma 1.9 z Dual of the Logic of Subsets, aby pokazać, że to prawda. Uogólnienie tego lematu na operacje nand z więcej niż dwoma danymi wejściowymi było motywacją do tego pytania.

algorithms graph-theory clique

— Thomas Klimpel
źródło

Jest to dobrze znany problem NP-Complete . en.wikipedia.org/wiki/Clique_cover_problem

— ogrodnik

@StephenBly Być może jest to znany problem, ale podany przez ciebie link do Wikipedii tak naprawdę mi nie pomaga. Artykuł mówi o problemie z pokrywą wierzchołków, ale pytanie tutaj dotyczy problemu z pokrywą krawędzi. Zauważ też, że relacja równoważności nie jest kliką, lecz rozłącznym związkiem klik.

— Thomas Klimpel

Co masz na myśli mówiąc, że relacja równoważności jest rozłączeniem związku klik? Zestaw wierzchołków reprezentuje elementy, a krawędź reprezentuje równoważność dwóch elementów. Jeśli nie jest to reprezentacja, której używasz, powinieneś to wyjaśnić.

— ogrodnik

n - 1

$n-1$

n

$n$

n - 1

$n-1$

@YuvalFilmus Pytanie dotyczy najmniejszej liczby relacji równoważności, których związek jest dokładnie relacją krawędzi danego wykresu, a nie której związek zawiera tylko dany wykres.

— David Richerby,

Odpowiedzi:

$\text{eq}(G)$ $\text{cc}(G)$

Istnieją specjalne klasy wykresów, w których znana jest dokładna wartość lub dobra górna granica dla dowolnej liczby. Ogólnie, zgodnie z moją najlepszą wiedzą, najlepsze granice daje Alon [1]:

\log_{2)} n - \log_{2)} re \leq równ (sol) \leq cc (sol) \leq 2) {mi}^{2)} (Δ + 1)^{2)} \ln n,

$\log_2 n - \log_2 d \leq \text{eq}(G) \leq \text{cc}(G) \leq 2e^2 (\Delta+1)^2 \ln n,$

$\Delta$ $G$ $\lceil n^2/4 \rceil$

$\sf NP$ $\text{eq}(G)$ $\sf NP$

[1] Alon, Noga. „Objęcie wykresów minimalną liczbą relacji równoważności”. Combinatorica 6.3 (1986): 201-206.

[2] Blokhuis, Aart i Ton Kloks. „O równoważności obejmującej liczbę podziałów”. Listy przetwarzające informacje 54.5 (1995): 301–304.

[3] Kučera, Luděk, Jaroslav Nešetřil i Aleš Pultr. „Złożoność wymiaru trzeciego i niektóre pokrewne cechy wykresów pokrywające krawędzie”. Theoretical Computer Science 11.1 (1980): 93-106.

— Juho
źródło

Wniosek 1.3 z [1] jest dokładnie tym, czego potrzebowałem (w wersji, która dotyczy uzupełnień ścieżki). Teraz nie mam już wymówki, by nie pisać artykułu o ogólnej implikacji „(A, B, C, ...) sugeruje (Z, Y, X, ...)” (sekwencja z rachunku sekwencyjnego) w partycji logika i podobne nieklasyczne logiki. Ale chyba nie będę go pisać przez co najmniej pół roku. A może w międzyczasie znajdę nową wymówkę.

— Thomas Klimpel,

@ThomasKlimpel To świetnie! (Nie fakt, że możesz znaleźć nową wymówkę, ale to było pomocne :-))

— Juho

Chociaż nie znam nazwy takiego problemu, mogę pokazać, że jest to trudny NP.

W przypadku wykresu bez trójkąta wszystkie klasy równoważności muszą być zgodne. Minimalna liczba klas równoważności pokrywająca wykres jest równa indeksowi chromatycznemu wykresu.

Zgodnie z tym artykułem znalezienie wskaźnika chromatycznego dla grafu bez trójkąta jest NP-całkowite.

— Chao Xu
źródło