Graph representation using edge sets

Question

Given a directed graph $(V,E)$ with $E\subseteq V\times V$, a source vertex $v_0\in V$ from which all other vertices are reachable, and a set $I$ of unique identifiers for the edges in $E$ (i.e., there is a bijection $I \rightarrow E$), we can construct a set $M\subseteq V \times \mathcal{P}(I)$ containing exactly those $(v,S)$ such that there is a path from $v_0$ to $v$ using exactly the edges represented by $S$ (in any order and repetition). For example, the graph $(\{A,B\},\{(A,B),(B,A)\})$ with $v_0=A$ and $I(a)=(A,B), I(b)=(B,A)$ would be represented as $\{(A,\emptyset),(B,\{a\}),(A,\{a,b\}),(B,\{a,b\})\}$.

I wonder under which conditions the inverse construction is possible: assuming $M$ is "consistent" (there is at least one graph satisfying it), what conditions are needed for $M$ to represent a unique graph? Certainly $M$ has to satisfy some kind of "closure" property, like: for every $(v,S)\in M$ (with $S\neq\emptyset$), there exists $(u,P)\in M$ such that $|S|=|P|+1$. Then a (hopefully deterministic) algorithm would construct $G$ by picking elements from $M$ in order of increasing cardinality.

Edit: of course the closure property should be that for every $(v,S)\in M$ (with $S\neq\emptyset$), there exists $(u,P)\in M$ such that $S= P\uplus\{x\}$. But this is not strong enough if self-loops are allowed: $\{(A,\emptyset),(B,\{a\}),(B,\{a,b\})\}$ represents two non-isomorphic graphs (one with $b=(B,A)$, the other with $b=(B,B)$).

Edit: I just noticed that there are counter-examples even without self-loops: $M=\{(A,\emptyset),(B,\{a\}),(C,\{a,b\}),(C,\{a,b,c\})\}$ may imply $c=(C,B)$ or $c=(C,A)$ (or $c=(C,C)$).

Has somebody worked on this kind of problem?

Answer 1

I think you can build $G$ in iterations:

• $M$ contains all $(v, \{e\})$ where $v \in \Gamma(v_0)$ ($\Gamma$ being neighborhood); so you can identify all edges to nodes that are distance 1 from $v_0$, as well as the nodes themselves; you can also identify the edges between nodes in $\Gamma(v_0)$ by looking for pairs $(v, \{e_1, e_2\})$, where $v \in \Gamma(v_0)$ and $e_1$ is an edge between $v_0$ and some $u \in \Gamma(v_0)$.
• then, iteratively, you can identify all edges and nodes in the subgraph of $G$ induced on the vertices which are distance at most $i$ to $v_0$ (call it $G_{i}$), using $G_{i-1}$. The idea is the same as above: you look for pairs $(v, S)$, where all but one edges in $S$ are in $G_{i-1}$; this gives $V(G_i \setminus G_{i-1})$. Then you can identify edges between vertices $u, v \in V(G_i \setminus G_{i-1})$ by looking for pairs $(v, S)$, where $S = S' \cup \{e_1\} \cup \{e_2\}$, such that $S' \subseteq E(G_{i-1})$, and $e_1$ has one point in $G_{i-1}$ and the other point is $u$; $e_2$ is the edge $(u, v)$.

Are you aware of the reconstruction and edge reconstruction conjectures? They have the same spirit as your probelm and, as far as I know, are open. Check out this beautiful half page proof by Lovasz that the edge reconstruction conjecture is true for any graph that has more edges than its compliment.