Hello,
this is my first question, I hope it will be clear and correct enough.
I am looking for a way to compare graphs in order to create a partial order among them (based on some kind of subgraph relationship), because I am interested in the resulting minimal graphs.
I know from the literature definitions of graph simulation and bisimulation. The latter appears to be too strong for my goal, so the former is somehow preferable. However, it is not exactly what I was looking for because it requires the labels of similar nodes to be equal. To avoid confusion, here is the definition of simulation I found in the literature:
Let $G=(N,E,V)$ be a direct graph composed of a set $N$ of nodes, a binary relation (the edges) $E\subseteq N \times N$, and a labelling function V which assigns a set of formulae to each node. A relation $S \subseteq N \times N$ is said to be a simulation over $G$ iff:
- $aSb \implies V(a)=V(b)$
- $(aSb\ \land\ aEc) \implies \exists d(cSd\ \land\ bEd)$
What I am interested in is a variation of such definition that involves a subset relationship instead of the equivalence (it also involves two different graphs, so that is not a simulation over the same graph). That is, the first point of the previous definition should change as follows (and $a$ and $b$ belong to different graphs).
- $aSb \implies V(a)\subseteq V(b)$
I tried to look for such a relation between graphs in the literature but I did not find it. Has such simulation already been studied? In case, are there results regarding complexity and/or algorithm to perform it?
