← All problems
Unverified

Complexity of Maximising reachability for target sets of size 1

Fijalkow and Horn studied generalised reachability games on graphs, which requires Eve (Player 1) to visit vertices from several different target sets. If all target sets are of size 1, the problem is solvable in PTIME. We are interested in the complexity of determining how many target sets Eve can guarantee to visit, i.e, given an arena, target vertices v1,v2,…,vnv_1, v_2, \dots, v_n, and a k≤nk\leq n, does Eve have a strategy that ensures at least kk targets are visited? This is known to be in PSPACE and NP-hard. Can we obtain better upper or lower bounds?

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu