<p>I think you can build $G$ in iterations: </p>

<ul>
<li>$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)$.</li>
<li>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&#39; \cup \{e_1\} \cup \{e_2\}$, such that $S&#39; \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)$.</li>
</ul>

<p>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 <a href="http://157.181.226.4/~lovasz/scans/line-reconstruction.pdf" rel="nofollow">this</a> beautiful half page proof by Lovasz that the edge reconstruction conjecture is true for any graph that has more edges than its compliment.</p>

CC BY-SA 3.0
2011-06-01T13:41:35.917Z
Thank you for spelling out what I had in mind:) I had never heard of the [reconstruction conjecture](http://en.wikipedia.org/wiki/Reconstruction_conjecture) before, thanks for that pointer.
warakawa
CC BY-SA 3.0
2011-06-03T14:16:30.350Z
I just noticed that my closure property is not strong enough for the above algorithm to produce a unique graph in case we allow self-loops (that's the kind of graph I had in mind), see my edit.
warakawa
CC BY-SA 3.0
2011-06-03T14:32:42.370Z
Even without self-loops, it is too weak (see edit).
warakawa
CC BY-SA 3.0
2011-06-03T17:05:30.327Z
i guess i do not understand what you're saying. i thought that the problem is: if $M$ contains for all $v$ and for all paths for which $v$ is an endpoint a pair $v, S$, where $S$ is the set of edges in the path, does $M$ determine a unique graph? the answer is yes. are you concerned with $M$ which do not contain all pairs but a subset?
Sasho Nikolov
CC BY-SA 3.0
2011-06-03T18:47:44.223Z
in particular, in your example in the last edit, if $c = (A, C)$, shouldn't there be a pair $C, \{c\}$? similarly if $c = (C, B)$, there should be a pair $B, \{c\}$
Sasho Nikolov
CC BY-SA 3.0
2011-06-04T12:30:21.240Z
Yes, I am concerned with $M$ which do not necessarily contain all pairs, and I am looking for conditions on $M$ that ensure $M$ still represents a unique graph.
warakawa
CC BY-SA 3.0
2011-05-25T03:49:58.983Z
2011-05-25T04:00:35.687Z
2011-05-25T04:00:35.687Z
Sasho Nikolov
<p>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\})\}$.</p>

<p>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.</p>

<p>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)$).</p>

<p>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)$).</p>

<p>Has somebody worked on this kind of problem?</p>

CC BY-SA 3.0
2011-05-24T16:19:39.537Z
Wouldn't it be easier to take I out of the picture and just name the edges in the traditional way, i.e., (A, B) and (B, A) in your example? That way we also don't have to deal with relabeling issues for the understanding of M. We would thus be able to talk about M(G) in a clear way rather than M(G, I).
Is there an easy example of 2 non-isomorphic graphs G and G' such that M(G) = M(G')?
marshallf
CC BY-SA 3.0
2011-05-24T17:54:22.833Z
If the edges are represented directly as vertex pairs in M, then it seems to me that the problem becomes trivial: we can just take E to be the union of all edge sets in M. The difficulty lies precisely in deciding which vertex pairs should be in E and what the bijection from I to E looks like.
warakawa
<reference-request><graph-theory><co.combinatorics><graph-algorithms>
Graph representation using edge sets
warakawa
# Graph representation using edge sets

(Asked by: username_0 on 2011-05-24)

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?

**Tags:** reference-request, graph-theory, co.combinatorics, graph-algorithms
> **Comments:**
> **username_1**: Wouldn't it be easier to take I out of the picture and just name the edges in the traditional way, i.e., (A, B) and (B, A) in your example? That way we also don't have to deal with relabeling issues for the understanding of M. We would thus be able to talk about M(G) in a clear way rather than M(G, I). Is there an easy example of 2 non-isomorphic graphs G and G' such that M(G) = M(G')?  
> **username_0**: If the edges are represented directly as vertex pairs in M, then it seems to me that the problem becomes trivial: we can just take E to be the union of all edge sets in M. The difficulty lies precisely in deciding which vertex pairs should be in E and what the bijection from I to E looks like.  

---

## 1 answers

### Answer by username_2 on 2011-05-25. Score: 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](http://157.181.226.4/~lovasz/scans/line-reconstruction.pdf) beautiful half page proof by Lovasz that the edge reconstruction conjecture is true for any graph that has more edges than its compliment.

> **Comments:**
> **username_0**: Thank you for spelling out what I had in mind:) I had never heard of the [reconstruction conjecture](http://en.wikipedia.org/wiki/Reconstruction_conjecture) before, thanks for that pointer.  
> **username_0**: I just noticed that my closure property is not strong enough for the above algorithm to produce a unique graph in case we allow self-loops (that's the kind of graph I had in mind), see my edit.  
> **username_0**: Even without self-loops, it is too weak (see edit).  
> **username_2**: i guess i do not understand what you're saying. i thought that the problem is: if $M$ contains for all $v$ and for all paths for which $v$ is an endpoint a pair $v, S$, where $S$ is the set of edges in the path, does $M$ determine a unique graph? the answer is yes. are you concerned with $M$ which do not contain all pairs but a subset?  
> **username_2**: in particular, in your example in the last edit, if $c = (A, C)$, shouldn't there be a pair $C, \{c\}$? similarly if $c = (C, B)$, there should be a pair $B, \{c\}$  
> **username_0**: Yes, I am concerned with $M$ which do not necessarily contain all pairs, and I am looking for conditions on $M$ that ensure $M$ still represents a unique graph.  

---

