Jaka jest złożoność tego problemu kolorowania krawędzi?

Ostatnio spotkałem następujący wariant kolorowania krawędzi.

Biorąc pod uwagę połączony niekierowany wykres, znajdź kolorystykę krawędzi, która wykorzystuje maksymalną liczbę kolorów, jednocześnie spełniając ograniczenie, że dla każdego wierzchołka krawędzie padające na używają co najwyżej dwóch kolorów. $v$ $v$

Po pierwsze sądzę, że problem jest trudny do rozwiązania. Klasyczne twarde proofy NP na problemy z koloryzacją grafów są przeważnie redukowane z 3SAT. Ale moim zdaniem te dowody nie są przydatne w przypadku tego problemu, ponieważ krawędzie padające na wierzchołek można pokolorować tym samym kolorem, więc nie możemy konstruować elementów logicznych na wykresie.

Czy ten problem może być trudny NP? Jeśli tak, jaki jest dowód? Jeśli nie możemy nałożyć grzywny na dowód, czy istnieje jakakolwiek metoda na określenie złożoności tego problemu?

Dzięki!

cc.complexity-theory np-hardness complexity-classes graph-colouring RIC_Eien
źródło

Być może mieszanie lub kolorowanie hypergraphowe może być początkiem? Na przykład dx.doi.org/10.1016/j.disc.2008.04.019

András Salamon

Wygląda na to, że twój problem występuje w P, w dwóch krokach: (1) twój problem jest równoważny ze znalezieniem podzbioru krawędzi o maksymalnym rozmiarze, tak że każdy wierzchołek ma stopień co najwyżej dwa, i (2) ten drugi problem wydaje się być w P przez, powiedzmy, redukcję do dopasowania. Jeśli chodzi o (1), zwróć uwagę, że każde rozwiązanie twojego problemu z k kolorami daje podgrupa stopnia 2 wielkości k (po prostu zachowaj jedną krawędź z każdego koloru), i odwrotnie, każdy podgrupa stopnia 2 wielkości k daje rozwiązanie z k kolorów (po prostu pokoloruj każdą krawędź podsgrafu własnym kolorem, pokoloruj pozostałe krawędzie dowolnym kolorem). czego mi brakuje?

Neal Young

Przykro mi, że w twojej odpowiedzi jest kilka błędów. Początkowo problem „znalezienia podzbioru krawędzi o maksymalnym rozmiarze, tak aby każdy wierzchołek miał co najwyżej dwa stopnie”, jest NP-trudny, redukcja do 3SAT (tak naprawdę nie wiem, jak mogłaby mieć redukcję dopasowania). Co więcej, „jakikolwiek wykres podrzędny stopnia 2 o rozmiarze k” nie daje „rozwiązania z k kolorów”, na przykład Kompletny wykres. Dziękuję wszystkim tym samym.

RIC_Eien

Tak, masz rację. Około (2) krok „pokoloruj resztę krawędzi dowolnym kolorem” może dać niektóre krawędzie wierzchołków trzech kolorów. Osobno Marek Chrobak zasugerował mi następujący algorytm. Myślę, że daje to przybliżenie 3: (i) znajdź maksymalne dopasowanie M; (ii) pokoloruj każdą krawędź w M swoim niepowtarzalnym kolorem; (iii) pokoloruj pozostałe krawędzie na biało.

Neal Young

@RIC_Eien: Ryzyko dalszego zawstydzenia. Czy jesteś pewien, że „problem” ze znalezieniem podzbioru krawędzi o maksymalnym rozmiarze, tak że każdy wierzchołek ma stopień co najwyżej dwa, jest NP-trudny? Biorąc pod uwagę G = (V, E), utwórz dwustronną G2 = (U, W, E2), gdzie dla każdego wierzchołka v w V jest v 'w U i v' 'w W, a E2 = {(u', w ''): (u, w) w E}. Zatem dopasowania w G2 odpowiadają zestawom krawędzi stopnia 2 w G, a korespondencja zachowuje rozmiar? (Ponieważ każdy cykl k C w G odpowiada w G2 albo cyklowi 2 k (jeśli k nieparzystemu) lub dwóm cyklom k (jeśli k parzystym).) Tak więc maksymalne dopasowanie w G2 rozwiązuje to. Czego mi brakuje tym razem?

Neal Young

Jaka jest złożoność tego problemu kolorowania krawędzi?

Odpowiedzi: