Agent Arrangement Problem

Tomoki Nakamigawa; Tadashi Sakuma

paper

Agent Arrangement Problem

arXiv:1212.2306

Abstract

An {\em arrangement} of an ordered pair $(G_{A}, G_{M})$ of graphs is defined as a function $f$ from $V (G_{A})$ to $V (G_{M})$ such that, for each vertex $c$ of $G_{M}$ , the vertex-set $f^{- 1} (c)$ of $G_{A}$ either is $\emptyset$ (the case when $c \neq \in f (V (G_{A}))$ ) or induces a connected subgraph of $G_{A}$ and that the family ${f^{- 1} (y) : y \in V (G_{M}), f^{- 1} (y) \neq = \emptyset}$ is a partition of $V (G_{A})$ . Let $f$ be an arrangement of $(G_{A}, G_{M})$ , let $pq$ be an edge of $G_{M}$ and let $U$ be a subset of $f^{- 1} (p)$ such that each of the three graphs $G_{A} [U]$ , $G_{A} [f^{- 1} (p) ∖ U]$ and $G_{A} [f^{- 1} (q) \cup U]$ is ether connected or $\emptyset$ and that $(f^{- 1} (p) \cup f^{- 1} (q)) ∖ U \neq = \emptyset$ . A {\em transfer} of $U$ from $p$ to $q$ is defined as the modification $f^{'}$ of $f$ such that $f^{'} (x) := f (x)$ for every $x \in / U$ and $f^{'} (u) := q$ for every $u \in U$ . Two arrangements $f$ and $g$ of $(G_{A}, G_{M})$ are called {\em t-equivalent} if they can be transformed into each other by a finite sequence of transfers. An ordered pair $(G_{A}, G_{M})$ of graphs is called {\em almighty} if every two arrangements of the pair $(G_{A}, G_{M})$ are t-equivalent. In this study, we consider the following two decision problems. [{\bf (P1)}]{For a given pair of arrangements $f$ and $g$ of a given ordered pair $(G_{A}, G_{M})$ of graphs, decide whether $f$ is t-equivalent to $g$ or not.} [{\bf (P2)}]{For a given ordered pair $(G_{A}, G_{M})$ of graphs, decide whether the pair $(G_{A}, G_{M})$ is almighty or not.} We show an $\Od(|E(G_A)|+(|V(G_M)|+|E(G_A)|)|V(G_A)|)$-time algorithm for {\bf (P1)}, and prove the $\co\np$-completeness of {\bf (P2)}.

32 pages, 5 figures