Game Dracula

Latar Belakang
Pertanyaan ini dimotivasi oleh permainan papan yang disebut 'Drakula'. Dalam game ini ada satu vampir dan empat pemburu, tujuan para pemburu adalah untuk menangkap vampir. Permainan berlangsung di Eropa. Permainan terlihat sebagai berikut:
1. Pemain pemburu menempatkan semua pemburu di kota-kota. Lebih dari satu pemburu dapat ditempatkan di kota yang sama.
2. Pemain vampir menempatkan vampir di kota.
3. Pemain secara bergantian memindahkan makhluk mereka ke kota-kota tetangga.
4. Pemain pemburu pada gilirannya dapat memindahkan pemburu sebanyak yang dia inginkan.
5. Kesulitan utama adalah bahwa pemain vampir tahu sepanjang waktu di mana pemburu berada, tetapi pemain pemburu hanya tahu posisi awal vampir.
6. Ketika seorang pemburu dan vampir bertemu di sebuah kota maka pemain vampir kalah.

Pertanyaan
Untuk grafik dan angka n dan , apakah ada strategi yang menjamin pemain pemburu, yang mengontrol memburu, untuk menangkap vampir dalam waktu kurang dari putaran ? Dapat diasumsikan bahwa adalah planar. Apakah masalah ini sudah dipelajari? Beberapa referensi akan dihargai.$G$$n$$k$$n$$k$$G$

Gim yang Anda gambarkan sangat mirip gim kops dan 1 Perampok, seperti yang dijelaskan dalam artikel ini oleh Clarke dan Macgillivray: http://www.sciencedirect.com/science/article/pii/S0012365X12000064 . Pada dasarnya, ini dimainkan dengan menempatkan k dan perampok pada simpul grafik dan meminta polisi untuk menangkap perampok dengan bergerak di sepanjang tepi.

Perbedaan utama dari gim Anda dan yang satu ini adalah jarak pandang sebagian dari para pemburu, sedangkan pada polisi dan perampok klasik, polisi tahu persis di mana perampok itu berada dan sebaliknya. Juga, di polisi dan perampok waktunya tidak terbatas.

Bahkan dengan informasi lengkap, jika waktu tidak terbatas, telah ditunjukkan bahwa menentukan apakah k-cop pada akhirnya dapat menangkap perampok dalam waktu yang terbatas ketika perampok dan polisi bermain secara optimal adalah waktu eksponensial selesai ( http://arxiv.org /abs/1309.5405 ) ketika k tidak diperbaiki. Oleh karena itu, karena permainan Anda lebih sulit untuk dimainkan oleh polisi, saya kira itu juga tidak dapat diselesaikan dalam waktu polinomial ketika waktu tidak terbatas. Saya pikir jumlah gerakan yang diperlukan untuk menangkap polisi perampok dapat dibatasi di atas, dengan mengatakan c, dan jika jumlah langkah k diizinkan untuk pemburu dekat dengan nomor ini c, maka permainan pemburu dan vampir akan menjadi setidaknya lebih sulit untuk diselesaikan daripada k polisi dan perampok (lihat artikel Bonato et al.: Waktu penangkapan grafik).

Seperti dicatat oleh @MarcusRitt dalam komentar, ini dikenal sebagai pencarian grafik. Namun, saya ingin menambahkan bahwa varian spesifik yang Anda jelaskan (yaitu, terkait jumlah putaran yang dimainkan dengan jumlah pencari yang digunakan) juga telah diselidiki, yang tidak dicatat dalam artikel Wikipedia. Menariknya, transisi dari ruang pencarian ke waktu pencarian mempertahankan karakterisasi masalah (dengan memperkenalkan versi "ganda" yang sesuai dari masing-masing parameter).

Lihat artikel "Pencarian grafik dan waktu pencarian" oleh Brandenburg dan Herrmann di SOFSEM 2006.

$v$$v$$1$$1$$k$, juga untuk grafik planar dimungkinkan untuk memperkirakan jumlah polisi (dan kemudian mendapatkan dekomposisi yang sesuai) dalam waktu polinomial. Mungkin Anda tertarik untuk membaca lebih lanjut dari catatan kuliah ini .