Czy istnieje problem, który jest łatwy w przypadku wykresu sześciennego, ale trudny w przypadku wykresów o maksymalnym stopniu 3?

Wykresy sześcienne to wykresy, w których każdy wierzchołek ma stopień 3. Zostały one szeroko zbadane i jestem świadomy, że kilka problemów trudnych dla NP pozostaje trudnych dla NP nawet ograniczonych do podklas grafów sześciennych, ale niektóre inne stają się łatwiejsze. Nadklasą wykresów sześciennych jest klasa grafów o maksymalnym stopniu . $\Delta \leq 3$

Czy jest jakiś problem, który można rozwiązać w czasie wielomianowym dla wykresów sześciennych, ale jest to trudny NP dla wykresów o maksymalnym stopniu ? $\Delta \leq 3$

graph-theory graph-algorithms np-hardness

— Vinicius dos Santos
źródło

Odpowiedź Degenrate który pokazuje, że mogą być różne zawiłości (choć nie jest NP-trudne): Finding

jest stały czas na wykresach liniowych, ale sześciennych na wykresach z

. :-)

δ

$\delta$

Δ \leq 3

$\Delta \le 3$

— William Macrae

Słuszna uwaga. :-)

— Vinicius dos Santos

Dla złych wyborów kodowania może być nawet

-hard gdy

, ale to będzie dużo bardziej wartościowe, aby znaleźć problem, który nie polega na złym kodowaniu, a nawet lepiej, jeśli ten problem jest dobrze badane jeden.

N P

$NP$

Δ \leq 3

$\Delta \le 3$

— William Macrae

Aby rozwinąć komentarz Williama, oto sztuczny problem. Czy na podstawie wykresu sekwencja stopni , interpretowana jako kodowanie instancji 3-SAT, reprezentuje instancję zadowalającą? $G$ $G$ (Zakładając, że kodowanie jest takie, że sekwencja wszystkich 3 stopni reprezentuje zadowalające przypisanie dla każdego

.) :-)

n

$n$

— Neal Young,

Zobacz także cstheory.stackexchange.com/questions/1215/..., aby uzyskać więcej inspiracji (np. Problemy trudne na drzewach o maksymalnym stopniu 3, ale banalne, jeśli nie ma węzłów liści).

— Jukka Suomela,

$(G,k)$ $G$ $k$

— David Eppstein
źródło

„... wówczas rozwiązaniem jest albo najdłuższy cykl, albo maksymalne dopasowanie ...”. W jaki sposób twoje roszczenie zależy od k? Nie dotyczy to wszystkich k.

— Tyson Williams

k

$k$

k = n

$k=n$

n

$n$

P

$P$

David, maksymalne dopasowanie (o rozmiarze większym niż 1) w G nie jest połączonym podgramem G. Czy masz na myśli powiedzieć „... albo najdłuższy cykl, albo pojedynczą krawędź, ...”?

— Tyson Williams,

Ok ok. Dzisiejszy dzień nie wydaje mi się dobry, aby być rygorystycznym - prawdopodobnie za dużo indyka. Dodałem trochę języka, aby wykluczyć ten wyjątkowy przypadek.

— David Eppstein,

@YininCao Ponieważ wykres jest połączony, ale nie jest regularny, nie ma możliwości wybrania 3-regularnego podgrafu. Załóżmy, że tak. Następnie istnieje wierzchołek, który nie został wybrany, ponieważ wykres nie jest regularny. Ponieważ wykres jest połączony, ten wierzchołek jest połączony z wybranym 3-regularnym wierzchołkiem. Ale to oznacza, że istnieje wierzchołek stopnia 4, sprzeczność.

— Tyson Williams,