Trudny problem obliczeniowy na specjalnej klasie grafów dwustronnych

11

Interesują mnie właściwości klasy grafów dwustronnych których wszystkie węzły w są 3-regularne, wszystkie węzły w są 2-regularne, a. Po pierwsze, czy jest to dobrze znana klasa grafów? Po drugie, $G(X \cup Y, E)$ $X$ $Y$ $|X|=|2Y/3|$

Czy istnieje przykład nierozwiązywalnego problemu obliczeniowego ograniczonego do tej klasy grafów dwustronnych?

complexity-theory graph-theory

— Mohammad Al-Turkistany
źródło

4

Biorąc pod uwagę 3-regularny wykres możesz zbudować dwustronny wykres z wymaganymi właściwościami wybierając i i dla każdej krawędzi add krawędzie . Myślę więc, że można znaleźć trudne problemy, zaczynając od trudnych problemów na 3-regularnych wykresach. $G = \{V,E\}$ $G'$ $X = V$ $Y = E$ $e_k = (u_i,u_j) \in E$ $(u_i, e_k), (e_k, u_j)$

Na przykład, ISOMORFIZM SUBGRAFOWY jest trudny dla NP dla twojej klasy grafów.

Redukcja pochodzi z cyklu Hamiltona na 3-regularnych wykresach: biorąc pod uwagę 3-regularny wykres , zbuduj odpowiedni i sprawdź podgrupa który jest zamkniętym prostym cyklem o długości. ma podgraph izomorficzny do wtedy i tylko wtedy, gdy ma cykl hamiltonowski. $G$ $G' = \{X \cup Y, E'\}$ $H'$ $2|V|$ $G'$ $H'$ $G$

— Vor
źródło

3

Te wykresy są wykresami częstości występowania wykresów sześciennych, czyli 2-ciągów 3-regularnych wykresów. Będę pisać na wykresie padania . $I(G)$ $G$

Biorąc pod uwagę wykres oraz całkowitą , to jest NP-zupełny, aby ustalić, czy „s liczba przejście jest co najwyżej (tzn czy można wyciągnąć w płaszczyźnie z co najwyżej krawędzie przecinające się wzajemnie), nawet jeśli jest ograniczone do sześciennych. Oczywiście, na przecięcie nie ma wpływu dodanie dodatkowego wierzchołka na środku każdej krawędzi. (Źródło: Hlineny, „Przekreślanie liczby jest trudne dla grafów sześciennych”, J. Combin. Teoria. B 96 (4): 455–471; DOI .) $G$ $k$ $G$ $k$ $G$ $k$ $G$

Możliwe, że problem przepustowości dla tych wykresów jest NP-zupełny, ponieważ jest NP-zupełny dla drzew, w których każdy wierzchołek ma stopień co najwyżej trzy. (Źródło: problem GT40 w Garey i Johnson dla grafów ogólnych; dla drzew niskiego stopnia, Garey, Graham, Johnson i Knuth, „Wyniki złożoności dla minimalizacji przepustowości”, SIAM J. Appl. Math. 34: 477-495; Citeseer . )

Różne problemy z kompletnym NP pozostają na wykresach sześciennych, co prowadzi do problemów z kompletnym NP na odpowiednich wykresach występowania, które są w miarę naturalne. Na przykład pytanie, czy wykres sześcienny ma dominujący zestaw wielkości co najwyżej jest równoważne pytaniu, czy jest sumą co najwyżej kopii . Podobnie niezależny zestaw na wykresie sześciennym odpowiada zestawowi rozłącznych kopii w . $G$ $k$ $I(G)$ $k$ $I(K_{1,3})$ $I(K_{1,3})$ $I(G)$

— David Richerby
źródło