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.