Hierarchical Graph Accessibility Problem (HGAP)

Input

A hierarchical graph $G = (V, E)$ and two designated vertices $s$ and $t$.

Problem

Is there a path between $s$ and $t$ in the expansion graph of $G$?

Definitions

A hierarchical graph $\Gamma = (G_1, \ldots, G_k)$ consists of $k$ subcells $G_i$, $1 \leq i \leq k$. Each subcell is a graph that contains three types of vertices called pins, inner vertices, and nonterminals. The pins are the vertices through which the subcell can be connected to from the outside. The inner vertices cannot be connected to from the outside. The nonterminals stand for previously defined subcells. A nonterminal inside $G_i$ has a name and a type. The name is a unique number or string. The type is a number from $1, \ldots, i - 1$. A nonterminal $v$ of type $j$ stands for a copy of subcell $G_j$. The neighbors of $v$ are in a one-to-one correspondence with the pins of $G_j$ via a mapping that is specified as part of $\Gamma$.

An expansion graph is a hierarchical graph expanded. The graph is expanded by expanding cell $G_k$ recursively. To expand subcell $G_i$, expand its subcells $G_1, \ldots, G_{i-1}$ recursively and replace each nonterminal $v$ of type $j$ with a copy of the expansion of subcell $G_j$.

Status

$\P$-complete (Lengauer and Wagner [1]).

Remarks

The reduction to show hardness is from AGAP. Hierarchical versions of the following problems are also $\P$-complete: graph accessibility in undirected graphs, determining whether a directed graph contains a cycle, and determining whether a given graph is bipartite [1]. There are several other very restricted versions of hierarchical graph problems that are $\P$-complete. See [1] for details.