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