I am interested in algorithms for computing all subgraphs (not necessarily induced) of a graph $G$ up to $Aut(G)$ isomorphism. I had the idea of partitioning the edges of the graph like so $$\{F|E(G)\setminus F\}$$ where $F$ is the set of "fixed" edges. We begin with $\{|E(G)\}%$ (none fixed) and then compute the orbits of $Aut(G)$ on $E(G)$. Selecting a representative from each, we create a new partition for each representative. Each orbit representative is fixed in its partition. To eliminate some redundancy in the second (and subsequent) partitions, we remove from each partition the edges that are in the orbit of previously-used edges in the stabilizer of the new representative.
For example, let $\{1,2,...,7\}$ be our edges for $G$. Suppose that $Aut(G)$ is edge transitive, so we get one partition $\{1|2,3,...,7\}$. Then we take the orbits of $\{2,...,7\}$ under the stabilizer of $1$ and say we get orbit representatives $2,4$. Then first we get the new partition $\{1,2|3,...,7\}$, which fixes $1$ and $2$ and can take children using $3...7$. The second partition will, of course, fix $1$ and $4$, but we will remove anything in the orbit of $2$ under the stabilizer of $1,4$, since it is redundant. Thus, if $\{2,6\}$ is an orbit in the stabilizer of $1,4$, the second partition will be $\{1,4|3,5,7\}$. We repeat the process—a branch ends when a partition has nothing on the right, no possible seeds for children. Thus the tree will grow until the last subgraph is found, with all edges fixed.
Here is the problem—this algorithm still has many redundancies. In the last example, say there is a symmetry $\sigma$ that maps $1 \mapsto 3$ and $2 \mapsto 4$. Both $\{1,2,3|\}$ and $\{1,4,3|\}$ are legitimate children from the two nodes we found above, but they are clearly identical under $\sigma$. This undermines the efficiency of the algorithm.
The only way I can see to fix the problem is to compute the orbit under $Aut(G)$ of a possible partition every time a new one is found and ensure that it is not already found. If one such isomorphic subgraph is made canonical, then new candidates must still be checked to see if they are identical by running through the group elements. This got me thinking: what if there were some magical way to label the graph such that a calculation could be made for any subgraph that would be invariant under $Aut(G)$? That is, the calculation would be identical for $A,B \le G$ if and only if $A \cong_G B$. I know it wouldn't be simple — I would consider this condition met if calculating this value were faster than just finding the orbit of $A$ and seeing if it included $B$.
So, here are my questions:
- Does any practical subgraph invariant to test for equivalence exist, and if not, can we prove that it doesn't?
- Could you suggest any resources to me on algorithms to find isomorph-free subgraphs? All I have been able to find are papers on the subgraph isomorphism problem, which is a different problem than mine.
Thank you.
