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!

— 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

$q$

Sparametryzowane aspekty złożoności tego problemu zostały omówione w tym ostatnim artykule .

— vb le
źródło

Od jakiegoś czasu zastanawiałem się nad tym miłym problemem ... Czy możesz opisać redukcję? Nie mam dostępu do gazety. Dzięki!

— user13667

@ user13667 Możesz poprosić autorów o przesłanie kopii ich artykułu. Myślę, że byliby z tego zadowoleni.

— czas le

Zbadano również pokrewne pytanie dotyczące znalezienia zabarwienia, które maksymalizuje liczbę kolorów przy jednoczesnym zminimalizowaniu wielkości największej grupy kolorów. Na przykład, ta praca magisterska ma kilka szczegółowych wyników.

— Neeldhara