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,

Odpowiedzi:

$(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,