We introduce a new equivalence on graphs, defined by its symmetry-breaking capability. We first present a framework for various backtracking search algorithms, in which the equivalence is used to prune the search tree. Subsequently, we define the equivalence and an optimization problem with the goal of finding an equivalence partition with the highest pruning potential. We also position the optimization problem into the computational-complexity hierarchy. In particular, we show that the verifier lies between $\mathcal{P}$ and $\mathcal{NP}$ -complete problems. Striving for a practical usability of the approach, we devise a heuristic method for general graphs and optimal algorithms for trees and cycles.

Detecting automorphisms is a natural way to identify redundant information presented in structured data. When such redundancies are detected they can be used for data compression. In this paper we explore two different classes of graphs to capture this intuitive property of automorphisms. Symmetry-compressible graphs are the first class which introduces the basic concepts but use only global symmetries for the compression. In order for this concept to be more practical, we need to use local symmetries. Thus, we extend the basic graph class with Near Symmetry compressible graphs. Furthermore, we develop two algorithms that can be used to compress practical instances and empirically evaluate them on a set of realistic graphs.

An exploratory equivalent partition (EE partition) of a graph G with nontrivial automorphisms is a partition of its vertex set that can be directly translated into a set of constraints to speed up the search for occurrences of G in an arbitrary host graph. The maximum EE partition problem is to find an EE partition leading to the greatest speedup. However, this problem is NP-hard and the naïve algorithm is only practicable for small symmetry-rich graphs. In this paper, we propose a series of improvements based on computational group theory that vastly increase the algorithm’s range of practicability. For example, the improved algorithm spends less time on the 10-hypercube graph (1024 vertices, 5120 edges, ≈3.7 × 10⁹ automorphisms) than the naïve algorithm does on the 4-hypercube graph (16 vertices, 32 edges, 384 automorphisms). We prove that all improvements maintain the algorithm’s correctness and confirm their contribution to the speed of execution through extensive experimentation.

In this paper, we study a well-known computationally hard problem, called the subgraph isomorphism problem where the goal is for a given pattern and target graphs to determine whether the pattern is a subgraph of the target graph. Numerous algorithms for solving the problem exist in the literature and most of them are based on the backtracking approach. Since straightforward backtracking is usually slow, many algorithmic refinement techniques are used in practical algorithms. The main goal of this paper is to study such refinement techniques and to determine their ability to speed up backtracking algorithms. To do this we use a methodology of experimental algorithmics. We perform an experimental evaluation of the techniques and their combinations and, hence, demonstrate their usefulness in practice.