5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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')? $\endgroup$ – marshallf May 24 '11 at 16:19
  • $\begingroup$ 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. $\endgroup$ – warakawa May 24 '11 at 17:54
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for spelling out what I had in mind:) I had never heard of the reconstruction conjecture before, thanks for that pointer. $\endgroup$ – warakawa Jun 1 '11 at 13:41
  • $\begingroup$ 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. $\endgroup$ – warakawa Jun 3 '11 at 14:16
  • $\begingroup$ Even without self-loops, it is too weak (see edit). $\endgroup$ – warakawa Jun 3 '11 at 14:32
  • $\begingroup$ 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? $\endgroup$ – Sasho Nikolov Jun 3 '11 at 17:05
  • $\begingroup$ 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\}$ $\endgroup$ – Sasho Nikolov Jun 3 '11 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.