Agent Arrangement Problem

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 $\mathrm{\varnothing }$ (the case when $c\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)\mathrm{\ne }\mathrm{\varnothing }\}$ 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)\setminus U]$ and $G_A[f^{-1}(q)\cup U]$ is ether connected or $\mathrm{\varnothing }$ and that $\big(f^{-1}(p)\cup f^{-1}(q) \big) \setminus U \neq \emptyset$\mathrm{.}A\text{em}transferof$U$from$p$to$q$ is defined as the modification $f^{\mathrm{\prime }}$ of $f$ such that $f^{\mathrm{\prime }}(x):=f(x)$ for every $ x \notin U$and$f^{\prime}(u):=q$forevery$u \in U$\mathrm{.}Twoarrangements$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 $\text{Od}(\mathrm{\mid }E(G_A)\mathrm{\mid }+(\mathrm{\mid }V(G_M)\mathrm{\mid }+\mathrm{\mid }E(G_A)\mathrm{\mid })\mathrm{\mid }V(G_A)\mathrm{\mid })$-time algorithm for {\bf (P1)}, and prove the $\text{co}\text{np}$-completeness of {\bf (P2)}.