Abstract
We define a search problem on trees that closely captures the backtracking behavior of all current practical graph isomorphism algorithms. Given two trees with colored leaves, the goal is to find two leaves of matching color, one in each of the trees. The trees are subject to an invariance property which promises that for every pair of leaves of equal color there must be a symmetry (or an isomorphism) that maps one leaf to the other.
We describe a randomized algorithm with errors for which the number of visited nodes is quasilinear in the square root of the size of the smaller of the two trees. For inputs of bounded degree, we develop a Las Vegas algorithm with a similar running time.
We prove that these results are optimal up to logarithmic factors. For this, we show a lower bound for randomized algorithms on inputs of bounded degree that is the square root of the tree sizes. For inputs of unbounded degree, we show a linear lower bound for Las Vegas algorithms. For deterministic algorithms we can prove a linear bound even for inputs of bounded degree. This shows why randomized algorithms outperform deterministic ones.
Our results explain why the randomized "breadthfirst with intermixed experimental path" search strategy of the isomorphism tool Traces (Piperno 2008) is often superior to the depthfirst search strategy of other tools such as nauty (McKay 1977) or bliss (Junttila, Kaski 2007). However, our algorithm also provides a new traversal strategy, which is theoretically near optimal and which has better worst case behavior than traversal strategies that have previously been used.
BibTeX  Entry
@InProceedings{anders_et_al:LIPIcs.ICALP.2021.16,
author = {Anders, Markus and Schweitzer, Pascal},
title = {{Search Problems in Trees with Symmetries: Near Optimal Traversal Strategies for IndividualizationRefinement Algorithms}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {16:116:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771955},
ISSN = {18688969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14085},
URN = {urn:nbn:de:0030drops140853},
doi = {10.4230/LIPIcs.ICALP.2021.16},
annote = {Keywords: Online algorithms, Graph isomorphism, Lower bounds}
}
Keywords: 

Online algorithms, Graph isomorphism, Lower bounds 
Collection: 

48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) 
Issue Date: 

2021 
Date of publication: 

02.07.2021 