Wszędzie, gdzie czytam o najrzadszym problemie cięcia, mówi tylko, że wiadomo, że jest to problem NP . Gdzie mogę znaleźć na to dowód? Który znany problem NP -twardości sprowadza się do najrzadszego problemu cięcia?
Nie znalazłem żadnego dowodu w książce Vazirani - Algorytmy aproksymacji, która przedstawia algorytm Leightona Rao, ani w książce „Komputery i nietykalność” - która podsumowuje wiele problemów z NP . Nie mogłem go znaleźć, wyszukując (z oczywistymi ciągami wyszukiwania) w Google. Jest jeden artykuł Chawli i in., Który zakłada hipotezę UGC Khota i dowodzi twardości przybliżenia najrzadszego cięcia. Miałem nadzieję zobaczyć dowód, który nie zakłada żadnych przypuszczeń.
Dowód powinien po prostu zredukować znany problem twardości NP do najrzadszego cięcia.
Dziękuję Ci,
Arpita Korwar.
źródło
Odpowiedzi:
[Przeniesiony z komentarza]
Artykuł „ Rzadkie cięcia i wąskie gardła na wykresach ” Davida W. Matuli, Farhada Shahrokhi daje redukcję problemu maksymalnego cięcia. Dowód twardości Max-cuta można znaleźć w Garey Johnson.
źródło