Naoki Kitamura

Naoki Kitamura, Hironori Kiya, Hirotaka Ono

Social deduction games, or hidden-role games, are multiplayer games in which players are assigned private roles and act under asymmetric information about other players' roles and actions. In the canonical example Werewolf, werewolves conceal their roles and mislead the other players, while the seer can obtain role information about a chosen player. Thus, a central functionality of such games is controlling which players can access which information. In typical play, this control is implemented by a trusted human moderator, who assigns roles, mediates secret actions, and reveals outcomes. This reliance raises the barrier to participation and introduces a trusted third party as a single point of failure. In this work, we show that Werewolf can be played without a moderator or any digital device, using only ordinary playing cards. Our construction maintains a shared pool of cards that is observable to all players and manipulated according to a common public procedure, while its interpretation depends on each player's private role. This induces role-dependent views from a single public sequence of card operations. Consequently, even without private messages, werewolves can identify one another and coordinate, and the seer can test whether a chosen player is a werewolf in each round. The proposed implementation is built from card-based physical cryptographic primitives, such as face-down commitments and verifiable shuffles, and higher-level subprotocols for intra-role information sharing, secret action designation, and attribute testing. These subprotocols implement the moderator's core functions while keeping all card operations public and auditable under standard assumptions on physical card operations. We show that the resulting complete moderatorless implementation of Werewolf scales to an arbitrary number n of players using O(n^3) cards.

Hiroki Hatano, Naoki Kitamura, Taisuke Izumi et al.

The independent set reconfiguration problem (ISReconf) is the problem of determining, for given independent sets I_s and I_t of a graph G, whether I_s can be transformed into I_t by repeatedly applying a prescribed reconfiguration rule that transforms an independent set to another. As reconfiguration rules for the ISReconf, the Token Sliding (TS) model and the Token Jumping (TJ) model are commonly considered. While the TJ model admits the addition of any vertex (as far as the addition yields an independent set), the TS model admits the addition of only a neighbor of the removed vertex. It is known that the complexity status of the ISReconf differs between the TS and TJ models for some graph classes. In this paper, we analyze how changes in reconfiguration rules affect the computational complexity of reconfiguration problems. To this end, we generalize the TS and TJ models to a unified reconfiguration rule, called the k-Jump model, which admits the addition of a vertex within distance k from the removed vertex. Then, the TS and TJ models are the 1-Jump and D(G)-Jump models, respectively, where D(G) denotes the diameter of a connected graph G. We give the following three results: First, we show that the computational complexity of the ISReconf under the k-Jump model for general graphs is equivalent for all k >= 3. Second, we present a polynomial-time algorithm to solve the ISReconf under the 2-Jump model for split graphs. We note that the ISReconf under the 1-Jump (i.e., TS) model is PSPACE-complete for split graphs, and hence the complexity status of the ISReconf differs between k = 1 and k = 2. Third, we consider the optimization variant of the ISReconf, which computes the minimum number of steps of any transformation between Is and It. We prove that this optimization variant under the k-Jump model is NP-complete for chordal graphs of diameter at most 2k + 1, for any k >=3.

Yuichi Sudo, Naoki Kitamura, Masahiro Shibata et al.

We study deterministic exploration by a single agent in $T$-interval-connected graphs, a standard model of dynamic networks in which, for every time window of length $T$, the intersection of the graphs within the window is connected. The agent does not know the window size $T$, nor the number of nodes $n$ or edges $m$, and must visit all nodes of the graph. We consider two visibility models, $KT_0$ and $KT_1$, depending on whether the agent can observe the identifiers of neighboring nodes. We investigate two fundamental questions: the minimum window size that guarantees exploration, and the optimal exploration time under sufficiently large window size. For both models, we show that a window size $T = Ω(m)$ is necessary. We also present deterministic algorithms whose required window size is $O(ε(n,m)\cdot m + n \log^2 n)$, where $ε(n,m) = \frac{\ln n}{1 + \ln m - \ln n}$. These bounds are tight for a wide range of $m$, in particular when $m = n^{1+Θ(1)}$. The same algorithms also yield optimal or near-optimal exploration time: we prove lower bounds of $Ω((m - n + 1)n)$ in the $KT_0$ model and $Ω(m)$ in the $KT_1$ model, and show that our algorithms match these bounds up to a polylogarithmic factor, while being fully time-optimal when $m = n^{1+Θ(1)}$. This yields tight bounds when parameterized solely by $n$: $Θ(n^3)$ for $KT_0$ and $Θ(n^2)$ for $KT_1$.