Masalah grafik dengan karakterisasi yang baik tetapi tidak diketahui dalam

8

Masalah keputusan memiliki karakterisasi yang baik jika ada dalam . Banyak masalah grafik alami memiliki karakterisasi yang baik. Misalnya, Teorema Kuratuwski memberikan karakterisasi grafik planar yang baik. Teorema Konig memberikan karakterisasi grafik bipartit yang baik. Teorema Tutte memberikan karakterisasi grafik yang memiliki kecocokan sempurna. Teorema Euler memberikan karakterisasi grafik Euler yang baik. Semua masalah pengenalan ini memiliki algoritma waktu polinomial.NP∩cHaiNP

Apakah ada masalah grafik alami yang memiliki karakterisasi yang baik tetapi tidak diketahui dalam ? Pointer ke survei masalah seperti itu akan dihargai.P

cc.complexity-theory graph-theory proof-complexity Mohammad Al-Turkistany
sumber

Jawaban:

14

NP∩cHaiNPP

Parity Games dan Stochastic Games dapat dianggap sebagai "masalah grafik".

NP∩cHaiNPP

Siwa Kintali
sumber
Terima kasih Shiva atas jawaban Anda yang bagus. Saya kira Two Bicliques adalah masalah grafik alami. Sadar akan survei masalah grafik seperti itu terutama masalah open standing paling lama?
Mohammad Al-Turkistany
Sayangnya, saya tidak mengetahui survei semacam itu.
Shiva Kintali
Permainan paritas sekarang setidaknya bisa diselesaikan dalam waktu yang semu, lihat jawaban ini . Mungkin itu tidak begitu penting, bahwa mereka tidak dapat diselesaikan dalam waktu polinomial. Mereka dapat dipecahkan dalam praktik, dan itulah yang paling penting.
Thomas Klimpel