1
$\begingroup$

I am investigating a paper from Dominik Grezlak and and Uwe Aßmann: “A Canonical String Encoding for Pure Bigraphs.” On page 2, they define the notion of a bigraph, which is roughly a forest and hypergraph on a common set of vertices. (The terminology comes from Robin Milner and does not directly connect to bipartile graphs). Here is a more detailed definition for reference (page 16, Milner). Note that the set of controls $\mathcal{K}$ is equipped with an arity map $ar: \mathcal{K} \to \mathbb{N}.$

enter image description here

Grezlak and Aßmann provide a polynomial time algorithm for bigraph isomorphism. This notion of isomorphism is a support translation, given in Definition 2.4, page 17 of Robin Milner’s “The Space and Motion of Communicating Agents.”

enter image description here

I am trying to determine whether graph isomorphism reduces to bigraph isomorphism. I want to find a counter example, because graph isomorphism is a hard problem and is not known to be in $P.$ I understand that the definition of suppport equivalence preserves the order of two new structures: the controls and ports. However, I want to consider a case where both of these are fixed. More specifically, I am considering five restrictions:

  1. The forest is a shallow tree: there is a root that is the parent of all other nodes.
  2. The hypergraph is a simple graph (each edge corresponds to exactly two vertices),
  3. The sets of inner and outer names are empty,
  4. $ar$ is injective, and
  5. Order the ports as follows: for any vertex $v,$ rank adjacent vertices based on their degree. Port 1 of $v$ is connected to the vertex with least degree, port 2 is connected to the vertex with 2nd least degree, etc. (If there is a tie, choose one of them first randomly).

Fix bigraphs $F, G$ with restrictions 1-5, and suppose there is a support translation $\rho: F \to G.$ Here are my main questions:

  1. If the link function is preserved, does that mean that $\rho$ preserves vertex adjacency (like in a graph homomorphism)?
  2. Is the link function reflected? In other words, is it true that $\rho_E^{-1} \circ link_G = link_F \circ \rho_{P}^{-1}$? (Note that I am abusing notation here; I am ignoring both $X, Y$, as they are both empty).
  3. If 1 and 2 are true, does this mean that the corresponding function between the link graphs of $F, G,$ respectively, is a graph isomorphism?

My current approach involves finding examples of non-isomorphic graphs online, from which I can then construct into bigraphs. As far as I can tell, graphs with size 4 and below are not that helpful. In these cases, it appears that each isomorphism class has exactly one element (i.e., is uniquely determined by degree sequence). I need an example where two non-isomorphic graphs have the same degree sequence and, preferably, are both small. So far, the examples that I have tried do not work; I can post them, if requested.

Please let me know if this question is more appropriate on a different SE site. I am happy to look into any suggested reference; I have not been able to find discussions related to these questions in the literature.

Edit 1: I figured out that a bigraph isomorphism not only preserves degree sequences, but also edge enumerations. Here’s my basic reasoning: Grezlak and Aßmann’s main algorithm does a BFS traversal on the place graph and, simultaneously, numbers each edge that hasn’t yet been traversed. This encodes both the place and link graphs. (I am ignoring inner and outer names here, but the procedure is similar). Based on my restrictions, this means there will only be two phases of BFS: marking the root node, and the traversal through the root’s children. This creates a unique string, the canonical encoding of the bigraph. Two bigraphs are isomorphic if they produce the same encoding. From my experiments, maintaining this edge enumeration appears to preserve cycles, so in a counterexample, I except both link graphs need to have an equal number of cycles (of the same length).

$\endgroup$
2
  • $\begingroup$ You can try to take a look at the pairs in funkybee.narod.ru/graphs.htm $\endgroup$ Mar 9 at 5:30
  • $\begingroup$ Thank you! I need to investigate the first graph that appeared on the link; I suspect a counterexample will have some sort of “crossing” edge behavior. (My intuition says two isomorphic bigraphs could differ by a pair of “crossing” edges, visually, but they wouldn’t be graph isomorphic). $\endgroup$ Mar 12 at 21:51

1 Answer 1

0
$\begingroup$

First of all, thank you Command Master for the website! And credits to the creator of https://funkybee.narod.ru/graphs.htm. (I did not see a profile page for the creator, but I would be happy to put a link if someone can find that). After looking at Pair #30 (immediately visible on the website), I came up with a counter-example to resolve Questions 1 and 3.

Question 1: no. See the counterexample in Question 3. Note, however, that this equation does uniquely determine the edge map. In other words, to construct a support translation $\rho,$ we only need a map $\rho_V$ between vertices.

Question 2: yes. This follows from a simple calculation with composites:

  1. Left compose both sides by $\rho^{-1}_E.$
  2. Right compose both sides by $\rho^{-1}_V.$

Question 3: in general, support translations do not preserve vertex adjacency. The premise need not be true.

The first counterexample I found is Pair #30, containing two non-isomorphic graphs. Two important points here:

  • Colors represent points that can be mapped to one another. Only the pink and blue points are degree 2; all other points are degree 3. My construction preserves these colors, though this is not strictly necessary. We can interpret the colors as controls, but it is easy to apply restriction 4 and find the same results.
  • Ports are invariant under support translation, so it doesn’t matter how we place them. Grezlak and Aßmann don’t explicitly include ports in their examples and algorithm. I am not sure exactly what purpose explicit ports serve, but the algorithm works either way.

Pair 30

This graph is a bit too large to check an explicit mapping. But we can easily fix this by removing the paths at the bottom of each graph, keeping only the pink and green points. Here’s the resulting link graphs, with labels as a visual aid. (Most of the labels match with their color names, except for blue). Again, note that we could replace each other by vertex degree without changing the main results.

enter image description here

[Edit 1 (March 16, 2024): My original solution contains a small mistake. I checked my counterexample with the python module igraph, and apparently, my original example is an isomorphic pair of graphs. However, I noticed I excluded something from Pair 30: a vertex $s$ that only connects to $a_1.$ By adding this in, igraph confirms that this is a valid example. In fact, these pair are not subgraph isomorphic, so it’s impossible to find a bijective graph homomorphism between this pair. This means bigraph isomorphism doesn’t preserve edge adjacency, which completely resolves Question 1. I will recreate my diagrams in a new edit, probably using pyplot.

My justification requires two small changes:

  • $s$ is sent to itself in the support translation, and
  • Label the edge from $s$ to $a_1$ with $0.$ This will change the starting edge in our enumerations, but that’s it. ]

For the same reason as Pair #30 (there are “crossing” edges $(r_1, p_2), (r_2, p_1)$ in $G$ but not in $F$), $F, G$ are not graph isomorphic.

Now it is easier to construct a support translation. By the answer to Question 1, we primarily need the vertex map $\rho_V: F \to G.$

  • Send $r_1 \in F$ to $r_2 \in G,$

  • Send $r_2 \in F$ to $r_1 \in G,$

  • Send $b_{2i} \in F$ to $b_{2i-1} \in G $ $(i = 1, 2),$

  • Send $b_{2i-1} \in F$ to $b_{2i} \in G,$

  • Send $a_1 \in F$ to $a_2 \in G,$

  • Send $a_2 \in F$ to $a_1 \in G,$

  • Send everything else to itself.

In other words, $\rho_V$ is a permutation that switches the pair of red points, the pair of blue points, $b_1$ and $b_2$, and $b_3$ and $b_4$, fixing everything else.

We know that the edge map is uniquely determined, but here’s the important part: we need to preserve and reflect edge enumerations. That was my recent realization with Grezlak and Aßmann’s algorithm: the canonical string (via my restrictions) exactly preserves degree sequences and this enumeration. By construction, the degree sequences are the same, and all we need to do is show this property: edges preserve vertex degrees. We don’t need edges to be identical, as we are allowed to permute the vertices to find a map. Numbers 1-8 in $F$ below are arbitrary, but they do mark the edges from degree 2 vertices first. Then the remaining edges are marked. The picture in $G$ is similar. As expected, $\rho_E$ permutes the edges based on $\rho_V.$

enter image description here

To emphasize, in bigraphs with restriction 4, vertices of the same degree may be chosen in a random order. This doesn’t change the underlying edges, which is are my main focus.

I don’t know whether this is the smallest example, but I do know how to construct larger ones. This includes Pair #30, but we can go farther: in the smaller example, extend each blue point in $F, G,$ respectively, by the same number of edges in a single path. The resulting pair will still be non-isomorphic as graphs, but the above permutation shows they must be bigraph isomorphic. We can make more complicated graphs from the blue points, as long as they are bigraph isomorphic. This extension is worth noting: there are infinitely many structurally distinct counterexamples. If only one counterexample existed, it would be fairly easy to check in a graph isomorphism algorithm, but this is not the case.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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