Abstract:
The game of rendezvous with adversaries is a game on a graph played by two players: Facilitator
and Divider. Facilitator has two agents and Divider has a team of k ≥ 1 agents. While the initial
positions of Facilitator’s agents are fixed, Divider gets to select the initial positions of his agents.
Then, they take turns to move their agents to adjacent vertices (or stay put) with Facilitator’s goal
to bring both her agents at same vertex and Divider’s goal to prevent it. The computational question
of interest is to determine if Facilitator has a winning strategy against Divider with k agents. Fomin,
Golovach, and Thilikos [WG, 2021] introduced this game and proved that it is PSPACE-hard and
co-W[2]-hard parameterized by the number of agents.
This hardness naturally motivates the structural parameterization of the problem. The authors
proved that it admits an FPT algorithm when parameterized by the modular width and the number
of allowed rounds. However, they left open the complexity of the problem from the perspective of
other structural parameters. In particular, they explicitly asked whether the problem admits an
FPT or XP-algorithm with respect to the treewidth of the input graph. We answer this question
in the negative and show that Rendezvous is co-NP-hard even for graphs of constant treewidth.
Further, we show that the problem is co-W[1]-hard when parameterized by the feedback vertex set
number and the number of agents, and is unlikely to admit a polynomial kernel when parameterized
by the vertex cover number and the number of agents. Complementing these hardness results, we
show that the Rendezvous is FPT when parameterized by both the vertex cover number and the
solution size. Finally, for graphs of treewidth at most two and girds, we show that the problem can
be solved in polynomial time.