1
$\begingroup$

To a hypergraph, we can apply the following transformations:

  • [Vertex Removal of Type A] Remove a specified vertex from the hypergraph. As for the edges that contained this vertex, remove all of these edges completely.

  • [Vertex Removal of Type B] Remove a specified vertex from the hypergraph. As for the edges that contained this vertex, just remove the specified vertex from these edges.

(So in type B vertex removal, an edge only gets completely removed if it contained only the specified vertex and no other vertices.)

The background problem I'm working on is the following:

I start with a hypergraph $H$. Now a series of transformations A,B,A,B,... is applied until there are no more vertices. I need to search through the tree of all choices of vertices for those transformations.

So, for example, if $H$ has 3 vertices {1,2,3}, then the tree looks like the following, where each node represents a hypergraph:

Example of a search tree.

During the search I look for some things which don't matter for this post.

Now, an important observation to actually do this in practice is that we will often see the same hypergraphs (up to isomorphism). So we can prune the search space by a lot by maintaining a database (hashtable) of hypergraphs we have seen so far (and their characteristics that we are looking for). However, as the hypergraphs will be just isomorphic but have different vertex/edge labels, we need to compute a canonical representation of the hypergraph at each stage, and store/search those canonical representations in our database.

For finding canonical hypergraph representations, I use the software Traces. I convert the hypergraph to a 2-colored graph, with some vertices representing hypergraph vertices and the other vertices representing hypergraph edges. Then Traces can compute a canonical representation of this 2-colored graph.

So far so good, but it is still too slow. To further improve the runtime, we make the following observation: To find a canonical representation, Traces will compute the automorphism group. When passing down our search tree, we will basically look at (some sort of) subgraph of the previous graph, with only one vertex removed. So:

In the Nauty/Traces/Bliss/saucy/conauto/... algorithm, can one speed up the computation of a canonical label and/or automorphism group of a subgraph with one vertex removed from a supergraph, by knowing the canonical label and automorphism group of the supergraph?

Improve this question
$\endgroup$
19
  • 1
    $\begingroup$ Checking the things that I'm looking for in the search tree is negligible. It's a fast check that will sometimes lead to stopping early in a branch (i.e. not considering some branch). You can think of the thing I'm doing as literally just traversing (some subtree of) the search tree mentioned above. So the only things that can be slow are (1) the search space is too big and (2) the canonical form computation is slow, because these are the only things I'm doing. I need any possible speed-up from both of those, in particular from (2). Lastly, be sure that I implement it very efficiently in C++. $\endgroup$
    – Johann Birnick
    Commented Dec 26, 2023 at 8:26
  • 1
    $\begingroup$ The answer is "no", nobody knows how to do that efficiently. However that doesn't mean nothing can be done. Approximately how many vertices and edges do your hypergraphs have in the cases where the speed is most of a problem? $\endgroup$
    – Brendan McKay
    Commented Dec 26, 2023 at 11:47
  • 1
    $\begingroup$ Following on from my last question, I guess it generalises to: the hypergraph depends only on the vertices A has removed and the vertices B has removed, not on the order in which they were removed. I assume you are avoiding canonical labelling when that sufficient condition for isomorphism is met. (Use two bit-vectors.) Another thing you can do is lazy canonical labelling: store a cheap-but-strong invariant for each hypergraph and only canonically label it when you find another hypergraph which is not equivalent by the relation at the start of this message but has the same invariant. $\endgroup$
    – Brendan McKay
    Commented Dec 27, 2023 at 6:21
  • 1
    $\begingroup$ Providing some of the automorphism group to Traces in advance will make it faster for difficult graphs, but for easy graphs the difference will be negligible. Most of your hypergraphs will be easy by that scale. $\endgroup$
    – Brendan McKay
    Commented Dec 27, 2023 at 6:24
  • 1
    $\begingroup$ In your problem the aim is to detect most isomorphisms and it doesn't matter if you miss a few. So you can use this method: perform a partition refinement. If it is not discrete (all cells singleton), fix an arbitrary vertex in the first non-trivial cell and refine again (starting with the new partition). Keep doing this until you have a discrete partition. Use that as the "canonical" labelling. Almost always it will be unique and the rare exceptions won't matter. Try the nauty refinement routine as well as the Traces one (they use the same graph structure). $\endgroup$
    – Brendan McKay
    Commented Dec 27, 2023 at 6:32

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .