Niezależny zestaw na sześciennych grafach bez trójkątów

Wiem, że maksymalny niezależny zestaw na sześciennych grafach bez trójkątów jest NP-zupełny.

Czy nadal jest NP-kompletny, jeśli potrzebujemy, aby niezależny zestaw miał dokładnie taką samą wielkość ? $|V|/2$

Zasadniczo YES wystąpienie problemu z niezależnym zestawem na szesnastkowym grafie bez trójkątów musi mieć dokładnie węzły. ŻADNA instancja nie ma niezależnego zestawu rozmiarów mniejszych niż . $|V|/2$ $|V|/2$

complexity-theory np-complete Mohammad Al-Turkistany
źródło

cs.stackexchange.com/questions/1176/... mogą być istotne.

Louis,

Jakie są przypadki NIE?

Yuval Filmus,

@YuvalFilmus Pyta, czy problemem jest $\alpha(G) = |G| / 2$ gdzie

jest kolejnością na wykresie. Powinno być możliwe umieszczenie na wykresie niektórych izolowanych wierzchołków w celu zwiększenia liczby niezależności. Mohammad, znasz redukcję? Czy nie jest możliwe dodanie

izolowanych wierzchołków, aby uzyskać pożądaną redukcję?

| G |

$|G|$

n / 2 - k

$n/2 - k$

Pål GD

Nie, nie mam zniżki.

Mohammad Al-Turkistany,

@ PålGD Redukcja nie zadziała, ponieważ zwykły problem dotyczy tego, czy

zamiast

. W rzeczywistości nie jest nawet jasne, że problem dotyczy NP.

α (G) \geq k

$\alpha(G) \geq k$

α (G) = k

$\alpha(G) = k$

Yuval Filmus,

Odpowiedzi:

Zacznijmy od udowodnienia, że maksymalny zbiór niezależny jest od wielkości co najwyżej . Pozwól być niezależnym zestawem. Dla każdego wierzchołka , niech jest szereg jego sąsiadów . Jeśli , to wiemy, że . Ponieważ wykres jest sześcienny, . Ponieważ $|V|/2$ $I$ $v$ $\alpha(v)$ $I$ $\alpha(v) \geq 1$ $v \notin I$ $\sum_v \alpha(v) = 3|I|$ , liczba wierzchołków jest taka, że wynosi co najmniej $\alpha(v) \leq 3$ $\alpha(v) \geq 1$ . Stąd . $|I|$ $|I| \leq |V|/2$

Kiedy możemy mieć równość? Musimy mieć $\alpha(v) \in \{0,3\}$ , więc nie dla każdego wierzchołka w wszyscy jej sąsiedzi muszą być w . Odwrotna jest również prawdą - dla każdego wierzchołka w wszyscy jej sąsiedzi nie są w . Innymi słowy, wykres musi być dwustronny. Można to sprawdzić w czasie wielomianowym. $I$ $I$ $I$ $I$

Yuval Filmus
źródło

YuvalFilmus Bardzo dziękuję. Czy to daje algorytm wielomianu czasu dla mojego problemu?

Mohammad Al-Turkistany

Myślę, że tak - zgadzasz się?

Yuval Filmus