{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:47:55Z","timestamp":1760240875197,"version":"build-2065373602"},"reference-count":49,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2019,10,15]],"date-time":"2019-10-15T00:00:00Z","timestamp":1571097600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>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    P    and    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.<\/jats:p>","DOI":"10.3390\/sym11101300","type":"journal-article","created":{"date-parts":[[2019,10,16]],"date-time":"2019-10-16T03:32:54Z","timestamp":1571196774000},"page":"1300","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A Symmetry-Breaking Node Equivalence for Pruning the Search Space in Backtracking Algorithms"],"prefix":"10.3390","volume":"11","author":[{"given":"Uro\u0161","family":"\u010cibej","sequence":"first","affiliation":[{"name":"Faculty of Computer and Information Science, University of Ljubljana, Ve\u010dna pot 113, 1000 Ljubljana, Slovenia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luka","family":"F\u00fcrst","sequence":"additional","affiliation":[{"name":"Faculty of Computer and Information Science, University of Ljubljana, Ve\u010dna pot 113, 1000 Ljubljana, Slovenia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jurij","family":"Miheli\u010d","sequence":"additional","affiliation":[{"name":"Faculty of Computer and Information Science, University of Ljubljana, Ve\u010dna pot 113, 1000 Ljubljana, Slovenia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,10,15]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Leach, A.R., and Gillet, V.J. (2007). An Introduction to Chemoinformatics, Springer.","DOI":"10.1007\/978-1-4020-6291-9"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1006\/jvlc.1996.0027","article-title":"Defining and Parsing Visual Languages with Layered Graph Grammars","volume":"8","author":"Rekers","year":"1997","journal-title":"J. Vis. Lang. Comput."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1049\/iet-sen.2010.0081","article-title":"Improving the graph grammar parser of Rekers and Sch\u00fcrr","volume":"5","author":"Mernik","year":"2011","journal-title":"IET Softw."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Cook, S.A. (1971, January 3\u20135). The complexity of theorem-proving procedures. Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (STOC), Shaker Heights, OH, USA.","DOI":"10.1145\/800157.805047"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Arora, S., and Barak, B. (2009). Computational Complexity: A Modern Approach, Cambridge University Press.","DOI":"10.1017\/CBO9780511804090"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., and Kratsch, D. (2011). Exact Exponential Algorithms, Springer.","DOI":"10.1007\/978-3-642-16533-7"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/321921.321925","article-title":"An Algorithm for Subgraph Isomorphism","volume":"23","author":"Ullmann","year":"1976","journal-title":"J. Assoc. Comput. Mach."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1367","DOI":"10.1109\/TPAMI.2004.75","article-title":"A (sub)graph isomorphism algorithm for matching large graphs","volume":"26","author":"Cordella","year":"2004","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1550025","DOI":"10.1142\/S0218001415500251","article-title":"Improvements to Ullmann\u2019s Algorithm for the Subgraph Isomorphism Problem","volume":"29","year":"2015","journal-title":"Int. J. Pattern Recognit. Artif. Intell."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Bonnici, V., Giugno, R., Pulvirenti, A., Shasha, D., and Ferro, A. (2013). A subgraph isomorphism algorithm and its application to biochemical data. BMC Bioinform., 14.","DOI":"10.1186\/1471-2105-14-S7-S13"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Festa, P., Sellmann, M., and Vanschoren, J. (2016). Portfolios of Subgraph Isomorphism Algorithms. Learning and Intelligent Optimization, Springer International Publishing.","DOI":"10.1007\/978-3-319-50349-3"},{"key":"ref_12","unstructured":"Foggia, P., Liu, C.L., and Vento, M. (2017). Introducing VF3: A New Algorithm for Subgraph Isomorphism. Graph-Based Representations in Pattern Recognition, Springer International Publishing."},{"key":"ref_13","first-page":"45","article-title":"Practical Graph Isomorphism","volume":"30","author":"McKay","year":"1981","journal-title":"Congr. Numer."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Babai, L. (2015, January 14\u201317). Graph Isomorphism in Quasipolynomial Time. Proceedings of the forty-eighth annual ACM Symposium on Theory of Computing, Portland, OR, USA.","DOI":"10.1145\/2897518.2897542"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"R18","DOI":"10.37236\/1242","article-title":"Symmetry breaking in graphs","volume":"3","author":"Albertson","year":"1996","journal-title":"Electron. J. Combin."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"R11","DOI":"10.37236\/1037","article-title":"On computing the distinguishing numbers of trees and forests","volume":"13","author":"Cheng","year":"2006","journal-title":"Electron. J. Combin."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1002\/jgt.20190","article-title":"Distinguishing Cartesian powers of graphs","volume":"53","author":"Imrich","year":"2006","journal-title":"J. Graph Theory"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"R23","DOI":"10.37236\/1361","article-title":"A note on the asymptotics and computational complexity of graph distinguishability","volume":"5","author":"Russell","year":"1998","journal-title":"Electron. J. Combin."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1297","DOI":"10.1137\/07068686X","article-title":"On computing the distinguishing numbers of planar graphs and beyond: A counting approach","volume":"22","author":"Arvind","year":"2008","journal-title":"SIAM J. Discret. Math."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1080\/0022250X.1994.9990134","article-title":"Regular equivalence: General theory","volume":"19","author":"Everett","year":"1994","journal-title":"J. Math. Sociol."},{"key":"ref_21","first-page":"31","article-title":"Computing Regular Equivalence: Practical and Theoretical Issues","volume":"17","author":"Everett","year":"2002","journal-title":"Metodolo\u0161ki Zvezki"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0378-8733(78)90014-X","article-title":"Structural Equivalence: Meaning and Definition, Computation and Application","volume":"1","author":"Sailer","year":"1978","journal-title":"Soc. Netw."},{"key":"ref_23","unstructured":"Knuth, D.E. (2016). The Art of Computer Programming. Volume 4B. Combinatorial Algorithms: Part 2, Addison-Wesley Professional. The Art of Computer Programming."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Gaspers, S., and Walsh, T. (2017). An Adaptive Prefix-Assignment Technique for Symmetry Reduction. Theory and Applications of Satisfiability Testing\u2014SAT 2017, Springer International Publishing.","DOI":"10.1007\/978-3-319-66263-3"},{"key":"ref_25","unstructured":"Crawford, J., Ginsberg, M., Luks, E., and Roy, A. (1996, January 5\u20138). Symmetry-Breaking Predicates for Search Problems. Proceedings of the Fifth International Conference Principles of Knowledge Representation and Reasoning, (KR \u201996), Cambridge, MA, USA."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"J\u00fcnger, M., Liebling, M.T., Naddef, D., Nemhauser, L.G., Pulleyblank, R.W., Reinelt, G., Rinaldi, G., and Wolsey, A.L. (2010). Symmetry in Integer Linear Programming. 50 Years of Integer Programming 1958\u20132008: From the Early Years to the State-of-the-Art, Springer.","DOI":"10.1007\/978-3-540-68279-0"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Gent, I.P., Petrie, K.E., and Puget, J.F. (2006). Symmetry in constraint programming. Handbook of Constraint Programming, Elsevier Science.","DOI":"10.1016\/S1574-6526(06)80014-3"},{"key":"ref_28","unstructured":"Petrie, K.E., and Smith, B.M. (2005). Comparison of symmetry breaking methods in constraint programming. Proc. SymCon05."},{"key":"ref_29","unstructured":"The GAP Group (2016). GAP\u2014Groups, Algorithms, and Programming, Version 4.8.3, The GAP Group."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Gent, I.P., Harvey, W., and Kelsey, T. (2002). Groups and constraints: Symmetry breaking during search. Principles and Practice of Constraint Programming\u2014CP 2002, Springer.","DOI":"10.1007\/3-540-46135-3_28"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Mora, T. (1989). Backtrack searching in the presence of symmetry. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Proceedings of the 6th International Conference, AAECC-6, Rome, Italy, 4\u20138 July 1988, Springer.","DOI":"10.1007\/3-540-51083-4"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Hentenryck, P. (2002). Symmetry Breaking Revisited. Principles and Practice of Constraint Programming\u2014CP 2002, Proceedings of the 8th International Conference, CP 2002, Ithaca, NY, USA, 9\u201313 September 2002, Springer.","DOI":"10.1007\/3-540-46135-3"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Walsh, T. (2001). Symmetry Breaking. Principles and Practice of Constraint Programming\u2014CP 2001, Proceedings of the 7th International Conference, CP 2001, Paphos, Cyprus, 26 November\u20131 December 2001, Springer.","DOI":"10.1007\/3-540-45578-7"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s10107-003-0394-6","article-title":"Exploiting orbits in symmetric ILP","volume":"98","author":"Margot","year":"2003","journal-title":"Math. Program."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1007\/s00224-011-9312-0","article-title":"A Note on Exact Algorithms for Vertex Ordering Problems on Graphs","volume":"50","author":"Bodlaender","year":"2011","journal-title":"Theory Comput. Syst."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1137\/0134037","article-title":"Complexity results for bandwidth minimization","volume":"34","author":"Garey","year":"1978","journal-title":"SIAM J. Appl. Math."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"12:1","DOI":"10.1145\/2390176.2390188","article-title":"On Exact Algorithms for Treewidth","volume":"9","author":"Bodlaender","year":"2012","journal-title":"ACM Trans. Algorithms"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1090\/dimacs\/011\/11","article-title":"Permutation groups and polynomial-time computation","volume":"Volume 11","author":"Luks","year":"1993","journal-title":"Groups and Computation: Workshop on Groups and Computation, October 7\u201310, 1991"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Seress, \u00c1. (2003). Permutation Group Algorithms, Cambridge University Press. Cambridge Tracts in Mathematics.","DOI":"10.1017\/CBO9780511546549"},{"key":"ref_40","first-page":"66","article-title":"Isomorphism Testing: Perspective and Open Problems","volume":"86","author":"Arvind","year":"2005","journal-title":"Bull. EATCS"},{"key":"ref_41","unstructured":"Knuth, D.E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms, Addison-Wesley Professional. [3rd ed.]."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1137\/0210015","article-title":"Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs","volume":"10","author":"Colbourn","year":"1981","journal-title":"SIAM J. Comput."},{"key":"ref_43","first-page":"162","article-title":"Iskanje vzor\u010dnih grafov s pomo\u010djo iskalnega na\u010drta ob prisotnosti avtomorfizmov [Searching for pattern graphs using a search plan in the presence of automorphisms]","volume":"85","year":"2018","journal-title":"Elektrotehni\u0161ki Vestnik"},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Kunegis, J. (2013, January 13\u201317). KONECT: The Koblenz network collection. Proceedings of the International Conference on World Wide Web Companion, Rio de Janeiro, Brazil.","DOI":"10.1145\/2487788.2488173"},{"key":"ref_45","unstructured":"Leskovec, J., and Krevl, A. (2019, October 05). SNAP Datasets: Stanford Large Network Dataset Collection. Available online: http:\/\/snap.stanford.edu\/data."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1016\/j.jsc.2013.09.003","article-title":"Practical graph isomorphism, II","volume":"60","author":"McKay","year":"2014","journal-title":"J. Symb. Comput."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"1372","DOI":"10.1093\/bioinformatics\/btx758","article-title":"Efficiently counting all orbits of graphlets of any order in a graph using autogenerated equations","volume":"34","author":"Melckenbeeck","year":"2017","journal-title":"Bioinformatics"},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"723","DOI":"10.1613\/jair.5768","article-title":"When subgraph isomorphism is really hard, and why this matters for graph databases","volume":"61","author":"McCreesh","year":"2018","journal-title":"J. Artif. Intell. Res."},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Ball, F., and Geyer-Schulz, A. (2018). How Symmetric Are Real-World Graphs? A Large-Scale Study. Symmetry, 10.","DOI":"10.3390\/sym10010029"}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/11\/10\/1300\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:26:32Z","timestamp":1760189192000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/11\/10\/1300"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,15]]},"references-count":49,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2019,10]]}},"alternative-id":["sym11101300"],"URL":"https:\/\/doi.org\/10.3390\/sym11101300","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2019,10,15]]}}}