Compu ing Au o opism G oups o Pa ial La in Rec angles
REBECCA J. STONES, Nankai Uni e si y and Beijing Jiao ong Uni e si y, China
RAÚL M. FALCÓN, Uni e sidad de Se illa, Spain
DANIEL KOTLAR, Tel-Hai College, Is ael
TRENT G. MARBACH, Rye son Uni e si y, China
Compu ing he au o opism g oup o a pa ial La in ec angle (PLR) can be pe o med in mul iple ways. This
s udy has wo aims: compa ing some o hese me hods expe imen ally o iden i y hose ha a e compe i-
i e; and iden i ying design goals o de eloping p ac ical so wa e. We compa e six amilies o algo i hms
( wo back acking and ou g aph- heo e ic me hods), wi h and wi hou using en y in a ian s (EIs), in a
ange o se ings. Two EIs a e conside ed: equencies o ow, column, and symbol ep esen a i es; and 2 ×2
subma ices. The bes app oach o compu ing au o opism g oups a ies.
When PLRs ha e many au o opisms (such as ha ing e y ew en ies o being a g oup able), he McKay,
Meyne , and My old (MMM) me hod compu es gene a o s o he au o opism g oup e icien ly. (The MMM
me hod is he s anda d way o compu e au o opisms.) O he wise, PLRs o dina ily ha e i ial o small au o-
opism g oups, and he ask is o e i y his. The so-called PLR g aph me hod is sligh ly mo e e icien in his
se ing han he MMM me hod (in some ci cums ances, a ound wice as as ).
Wi h an in e media e numbe o en ies, he quick- o-compu e s ong EIs a e e ec i e a educing he need
o compu a ion wi hou in oducing signi ican o e head. Wi h a ull o almos - ull PLR, a mo e sophis ica ed
EI is needed o educe down- he-line compu a ion.
These esul s sugges a hyb id app oach o compu ing au o opism g oups: The so wa e decides on sui able
EIs based on he inpu ; and he use chooses be ween he MMM o he PLR g aph me hods, depending on
hei da ase .
This a icle expands he au ho s’ p e ious a icle Compu ing au o opism g oups o PLRs: a pilo s udy.
CCS Concep s: • Ma hema ics o compu ing →Combina o ial algo i hms;G aph colo ing;G aph
algo i hms;
Addi ional Key Wo ds and Ph ases: Au o opism, La in squa e, pa ial La in ec angle
Ma bach and S ones’s wo k is pa ially suppo ed by NSF o China (61602266, 61872201), he Science and Technology De-
elopmen Plan o Tianjin (17JCYBJC15300, 16JCYBJC41900), and he Fundamen al Resea ch Funds o he Cen al Uni e -
si ies and SAFEA: O e seas Young Talen s in Cul u al and Educa ional Sec o . S ones was suppo ed by he NSFC Resea ch
Fellowship o In e na ional Young Scien is s (g an numbe s: 11450110409, 11550110491), and he Thousand You h Talen s
Plan in Tianjin. Falcón’s wo k is pa ially suppo ed by he esea ch p ojec FQM-016 om Jun a de Andalucía and he
Depa men al Resea ch Budge o he Depa men o Applied Ma hema ics I o he Uni e si y o Se ille.
Au ho s’ add esses: R. J. S ones, College o Compu e Science, Nankai Uni e si y, Tianjin, P. R. China and Depa -
men o Ma hema ics, Beijing Jiao ong Uni e si y, Beijing, 100044 P. R. China; email: [email p o ec ed]; R. M.
Falcón, School o Building Enginee ing, Depa men o Applied Ma hema ics I, Uni e sidad de Se illa, 41012 - Se ille,
Spain; email: [email p o ec ed]; D. Ko la , Compu e Science Depa men , TelHai College, Uppe Galilee, 1220800 Is ael; email:
[email p o ec ed]; T. G. Ma bach, Depa men o Ma hema ics, Rye son Uni e si y, 350 Vic o ia S ., To on o, ON,
Canada; email: [email p o ec ed].
Pe mission o make digi al o ha d copies o all o pa o his wo k o pe sonal o class oom use is g an ed wi hou ee
p o ided ha copies a e no made o dis ibu ed o p o i o comme cial ad an age and ha copies bea his no ice and
he ull ci a ion on he i s page. Copy igh s o componen s o his wo k owned by o he s han he au ho (s) mus be
hono ed. Abs ac ing wi h c edi is pe mi ed. To copy o he wise, o epublish, o pos on se e s o o edis ibu e o lis s,
equi es p io speci ic pe mission and/o a ee. Reques pe missions om [email p o ec ed].
h ps://doi.o g/10.1145/3412324
1.12:2 R. J. S ones e al.
ACM Re e ence o ma :
Rebecca J. S ones, Raúl M. Falcón, Daniel Ko la , and T en G. Ma bach. 2020. Compu ing Au o opism G oups
o Pa ial La in Rec angles. J. Exp. Algo i hmics 25, 1, A icle 1.12 (Sep embe 2020), 39 pages.
h ps://doi.o g/10.1145/3412324
1 INTRODUCTION
Le [n]:= {1, 2,...,n}.An × s pa ial La in ec angle is an × s ma ix con aining symbols om
[n] ∪{·} such ha each ow and each column con ains a mos one copy o any symbol in [n].
This is a pa ial La in squa e i = s = n.Le PLR( , s, n) deno e he se o such ma ices. E e y
L ∈ PLR( , s, n) is uniquely de e mined by i s en y se
En (L) := {(i, j, L[i, j]) : i ∈ [ ], j ∈ [s], L[i, j] ∈ [n]}.
We call any iple (i, j, L[i, j]) ∈ En (L) an en y o L, while any pai (i, j) ∈ [ ] × [s] is called a cell.
We call a cell (i, j) emp y i L[i, j] = ·, in which case, we conside L[i, j] as being unde ined.I L ∈
PLR( , s, n) does no ha e emp y cells, hen L is a La in ec angle. The s anda d de ini ion o a La in
ec angle [84] equi es s = n, so we a e conside ing a gene aliza ion o his. Any L ∈ PLR(n, n, n)
wi h no emp y cells is a La in squa e o o de n. This cons i u es in u n he Cayley able o a
quasig oup o he same o de ; ha is, an algeb aic s uc u e endowed o le - and igh -di ision.
Pa icula ly, e e y associa i e quasig oup is indeed a g oup.
Fo a posi i e in ege m,le Sm deno e he symme ic g oup on [m]. Any iple θ := (α, β,γ ) ∈
S × Ss × Sn ac s on PLR( , s, n), wi h θ ac ing on L ∈ PLR( , s, n) by pe mu ing i s ows, columns,
and symbols by α, β,and γ , espec i ely. The iple θ is called an iso opism (an isomo phism i
α = β = γ ). Mo eo e , i is said ha Lθ ∈ PLR( , s, n) is iso opic o L (see Re e ence [36] o a ecen
su ey on he heo y o iso opisms). I L = L[i, j], hen
En (Lθ ) = {(α (i), β (j),γ (L[i, j])) : (i, j, L[i, j]) ∈ En (L)}
and we w i e (i, j, L[i, j])θ = (α (i), β (j),γ (L[i, j])). Iso opism induces an equi alence ela ion
among pa ial La in ec angles. In pa icula , e en hough he numbe and dis ibu ion o La in
squa es in o iso opism classes a e known [49, 59, 68] o o de up o 11, he numbe o pa ial
La in ec angles is only known o o de s , s, n ≤ 7, and hei dis ibu ion in o iso opism classes
is only known o o de s , s, n ≤ 6 (see Re e ences [31, 32, 35, 39, 41]). I L = Lθ , henθ is said o be
an au o opism o L.These A op(L) o au o opisms o L o ms a g oup, called he au o opism g oup
o L. F om he O bi -S abilize Theo em, he compu a ion o his g oup is c ucial o de e mining
he se o pa ial La in ec angles ha a e iso opic o L, and hence, he dis ibu ion o pa ial La in
ec angles in o iso opism classes [41].
The exponen ial g ow h o bo h he numbe o pa ial La in ec angles and he numbe o hei
possible au o opism g oups is a handicap o deal wi h hose o de s om six o ele en, e en hough
he dis ibu ion o La in squa es in o iso opism classes is known o hese o de s. In his ega d, his
a icle is a p elimina y s udy o se ing he echnical s anda ds o u he de elopmen o so -
wa e capable o compu ing au o opism g oups o pa ial La in ec angles e icien ly, which would
enable wo k on he p oblems o coun ing, enume a ing, and classi ying pa ial La in ec angles
o o de s , s, n > 6. Mo e speci ically, in his a icle, we implemen and expe imen ally compa e
six amilies o algo i hms o compu ing au o opism g oups o pa ial La in ec angles, wi h and
wi hou he use o in a ian s. Some o hese algo i hms ha e been used in p io esea ch on pa ial
La in ec angles, while o he s a e new. A b ie ske ch o his s udy has ecen ly been exposed by
he au ho s [88]. He e, we del e in o he de elopmen o e icien algo i hms o he compu a ional
Compu ing Au o opism G oups o Pa ial La in Rec angles 1.12:3
p ocesses desc ibed in ha p e ious wo k, along wi h a s udy o he easons ha gi e ise o be e
o wo se expe imen al esul s.
We no e ha i is un ealis ic o expec a succinc solu ion o he p oblems o coun ing, enume -
a ing, and classi ying pa ial La in ec angles o a bi a y o de s (and hence, o he p oblem o
compu ing hei au o opism g oups), since hey include he analogous p oblems o La in squa es,
which cons i u e long-s anding esea ch p oblems in Combina o ics. Though widely s udied in
he li e a u e, hese p oblems on La in squa es ha e been comple ely sol ed only o o de s up o
11. This ac shapes he unde lying di icul y o dealing wi h much highe o de s and mo i a es
ou expe imen s o be ocused on smalle ins ances, o o de s ,s,n≤20.
1.1 Li e a u e Re iew
Au o opisms o (pa ial) La in squa es ha e a isen in a ange o opics and a e also s udied in hei
own igh [3,10,15,16,22,26,30,37,38,50,56,57,60,72–74,86,96]. Thus, hey a e beginning o
ind applica ions in c yp og aphy [28,89,99], o g aph colo ing games [2,34], e asu e codes [87,
101], and Blackbu n pa ial La in squa es [87,94] (which ela e o pe ec hash amilies [11], pa en -
iden i ying codes [1], coded caching schemes [100], and 2-inc easing sequences [44]). Howe e ,
au o opisms o (pa ial) La in ec angles ha e only been s udied in a ew ecen pape s [31,39–41].
The s anda d way o compu ing au o opism g oups o La in squa es was gi en by McKay,
Meyne , and My old [68], who desc ibed a e ex-colo ed g aph whose au omo phism g oup is
isomo phic o he au o opism g oup o he co esponding La in squa e. As such, hey sugges ed
he use o he so wa e nau y [69], which is one o he mos widely used compu a ional ools
o deal wi h he g aph isomo phism p oblem [78] using e ex in a ian s; ha is, p ope ies o
e ices o g aphs ha a e p ese ed unde isomo phisms (as, o ins ance, he numbe o edges
inciden wi h a gi en e ex). These in a ian s make he compu a ion o au omo phism g oups
o g aphs as e , because hey pa i ion he e ices o a g aph so none o i s au omo phisms
pe mu e e ices om one pa o ano he . Ve ices o a g aph may he e o e be uniquely colo ed
acco ding o any gi en e ex in a ian wi hou changing i s au omo phism g oup.
The mo i a ion o McKay, Meyne , and My old o using colo ed g aph isomo phisms was
based on he obse ed exp essi i y o colo ed g aphs in ep esen ing combina o ial amilies (such
as pa ial La in ec angles) o symme y compu a ions. No ice in his ega d ha he use o col-
o ed g aphs ep esen ing ce ain symme ical p ope ies o (pa ial) La in ec angles had al eady
been deal in he li e a u e in he la e 1970s [19,20,43,47,48,98]. Fu he mo e, i had al eady
been es ablished by Mille [75] ha he p oblem o de e mining whe he wo La in squa es a e
iso opic when bo h a e Cayley ables is polynomial ime many-one educible o he g aph iso-
mo phism p oblem. Mo eo e , Mille himsel [76] gene alized Ta jan’s algo i hm o deciding in
O(nlog2n+O(1))s eps whe he wo La in squa es o o de na e isomo phic.
The mo e gene al p oblem o e icien ly compu ing symme ic g oups o combina o ial objec s
has been obse ed in he li e a u e o a leas 40 yea s [17,64,65]. Since hese ea ly pape s, he
pa icula use o combina o ial in a ian s o speed up such a compu a ion is s anda d p ac ice [53,
54]. Le us men ion in his ega d, o ins ance, he use o combina o ial in a ian s o compu ing
au omo phism g oups o Hadama d ma ices [62,92], e o -co ec ing codes [63,80], and g aphs,
om which we emphasize McKay’s seminal and highly in luen ial wo ks [66,69]. To educe he
un ime o he expensi e compu a ion ha would be equi ed by nau y o de e mining he au o-
opism g oup o a La in squa e using he men ioned e ex-colo ed g aph, McKay, Meyne , and
My old [68] also sugges ed he use o iso opism in a ian s based on ows, columns, and sym-
bols o he co esponding La in squa es. As an illus a i e example, hey p oposed o iden i y each
ow o he La in squa e unde conside a ion wi h i s numbe o 2 ×2 La in subsqua es (known as
in e cala es) in ol ing such a ow. P e iously, Wanless [95] had al eady indica ed he use o he
1.12:4 R. J. S ones e al.
so-called ains as iso opism in a ian s ha accele a e he compu a ion in nau y o au o opisms
and conjuga e symme ies o a omic La in squa es. Fu he mo e, he use o new iso opism in a i-
an s o compu ing au o opism g oups o La in squa es would no only complemen he combina-
o ial in a ian s ha a e al eady implemen ed in nau y, bu would also enable he imp o emen
o he design, analysis, and de elopmen o di e en s a egies ha a e ca ied ou by he so -
wa e o dealing wi h da a s uc u e and algo i hm enginee ing. Recall ha using some a ian s
o he Weis eile -Lehman indi idualiza ion- e inemen p ocedu e [97], he p ocessing o e ex in-
a ian s in nau y makes use o back acking, hashing, sea ch ees, p uning echniques based on
o bi s abilize algo i hms, a ge cell selec ions, and canonical labeling [66, 67, 69].
A gene aliza ion o he me hod by McKay, Meyne , and My old o deal wi h symme ies o
pa ial La in squa es was in oduced by S ones [85], who also used h ee basic in a ian s ( he
numbe o en ies in a ow o column, and he o al numbe o copies o a symbol) o educe he
sea ch space. Rega ded as ec o in a ian s, hey we e, espec i ely, es ablished as ow, column,
and symbol in a ian s. These ec o in a ian s a e closely ela ed o he no ion o ype in oduced
by Keedwell [55]. Since asymme y can exis e en in he case ha all hese ec o in a ian s a e
unique, S ones also es ablished a me hod o e i ying asymme y o pa ial La in squa es o o de
n in O (ncons an ) s eps. S ones implemen ed a back acking algo i hm ha p oceeded ow-by- ow
hen column-by-column o de e mining asymme ic pa ial La in squa es.
The co esponding gene aliza ion o he me hod by McKay, Meyne , and My old o × s pa -
ial La in ec angles on n symbols was deal wi h by Falcón and S ones [40]. Mo e ecen ly, he
p esen au ho s [23] ha e s udied some in a ian e inemen p ocedu es o deal wi h he compu-
a ion o he au o opism g oup o pa ial La in ec angles. They a e ela ed o some ideas p oposed
by Ko la [60, 61] conce ning he compu a ion o au o opisms o La in squa es by enume a ing
cycles belonging o ows. As such, i can be hough o as an example o wha we will call in his
a icle ow in a ian s. The e icien use o hese in a ian s in Re e ence [23] has equi ed he imple-
men a ion o a ee-based algo i hm, and he pa icula use o ed-black ees o dealing wi h he
co esponding da a s uc u e. Fu he mo e, in he li e a u e, one can also ind some in a ian s ha
a e used o compu ing au o opisms o pa ial La in ec angles sa is ying ce ain condi ions. This
is he case, o ins ance, o he ecen use o Hilbe polynomials in Re e ence [33] as in a ian s o
s ong iso opisms ( ha is, iso opisms o he o m (α, α,γ ) ∈ Sn × Sn × Sn ) o emp y-diagonal sym-
me ic pa ial La in squa es o which each one o i s ows and columns has a leas wo non-emp y
cells.
I is known [15] ha a La in squa e o o de n has a mos nO (log n) au o opisms, and hence,
he compu a ion o au o opism g oups o La in squa es akes wo s -case supe -polynomial ime.
Ne e heless, almos all La in squa es ha e i ial au o opism g oups [18, 71]. So, in almos all
cases, compu ing he se o au o opisms o a La in squa e L amoun s o elimina ing he possibili y
o a non- i ial au o opism (which is pe inen o applica ions in ol ing canonically labeling La in
squa es [42]). I seems easonable o suspec ha a ela ed “almos all” claim holds o (pa ial)
La in ec angles unde mos condi ions. Howe e , i is no s aigh o wa d o gene alize hese
p oo s o (pa ial) La in ec angles. Some obs acles a e: (a) wo emp y columns in a pa ial La in
ec angle can be swapped, gi ing ise o a la ge amily o pa ial La in ec angles wi h a non- i ial
(albei unin e es ing) au o opism; (b) 2 × n La in ec angles always ha e non- i ial symme ies;
and (c) pa ial La in ec angles wi h e y ew en ies mus ha e non- i ial symme ies [85].
In his a icle, pa ial La in ec angle g aphs a e used o compu ing au o opism g oups o pa ial
La in ec angles. These g aphs we e in oduced as a gene aliza ion o La in squa e g aphs [13]by
Falcón and S ones [40], who showed hei use ulness o p o ing symme y p ope ies o pa ial
La in ec angles. A ecen s udy [24] conside s ealizing g aphs as pa ial La in ec angle g aphs,
and e en hei gene aliza ion o pa ial La in hype cuboid g aphs. As such, i is possible o sol e
Compu ing Au o opism G oups o Pa ial La in Rec angles 1.12:5
he g aph isomo phism (GI) p oblem o g aphsGand H h ough he cons uc ion o a pa ial La in
squa e whose au o opism g oup is isomo phic o he au omo phism g oup o he g aph G∪H.As
a consequence, he compu a ion o he au o opism g oup o a pa ial La in squa e equi es a leas
polynomially equi alen ime o sol ing he GI p oblem, whose complexi y is known [6,8,9] o
be a mos exp((logn)O(1)),whe enis he numbe o e ices. No ice ha he de elopmen o new
algo i hms o deal wi h he GI p oblem is cu en ly a e y ac i e a ea o esea ch [5,7,45,46,58,
77,79]. In Sec ion 2, we see in pa icula ha he p oblem o compu ing he se o gene a o s o
he au o opism g oup o a pa ial La in ec angle is g aph-isomo phism comple e (GI-comple e).
Tha is, i is polynomial- ime equi alen o he GI p oblem.
1.2 Tes Se s
Th oughou he a icle, we compa e he un imes o he algo i hms expe imen ally on wo an-
domly gene a ed se s o pa ial La in ec angles, desc ibed below. In bo h es se s, pa ial La in
ec angles a e gene a ed non-uni o mly a andom. I should be no ed ha he p oblem o uni-
o mly gene a ing andom pa ial La in ec angles wi h a speci ied numbe o en ies is likely a
non- i ial esea chp oblem, since i con ains he sub-p oblemo gene a ing andom La in squa es
[25,51].
1.2.1 PLR Se A: Adding Random En ies. To gene a e a membe o PLR se A, we begin wi h
an emp y PLR( ,s,n)and a emp x imes o add an en y chosen uni o mly a andom om [ ]×
[s]×[n]. Th ee ypes o clashes migh a ise: (a) he cell is al eady ull, (b) adding he en y would
in oduce a epea ed symbol in a ow, o (c) adding he en y would in oduce a epea ed symbol
in a column. I a clash a ises, we do no hing.
The eason o ix he numbe o a emp s in his PLR se A and no he numbe o illed cells is
because ixing his las numbe may lead o a dead-end i no en y can be added. We a e mo i a ed
o use his es se , since S ones [85] used a ela ed andomized se . In he la e , gene a ing a
PLR es a ed om sc a ch whene e a clash a ose, so a uni o m dis ibu ion on m-en y pa ial
La in squa es was achie ed. The gene a ion me hod p esen ed he e does no gene a e PLR( ,s,n)’s
uni o mly a andom, e en i we es ic he numbe o en ies. In he case =s=n=2andx=5,
he p obabili ies o gene a ing each possible PLR(2,2,2)a e abula ed in Table 1, whe e we see ha
hese p obabili ies dis inguish PLR(2,2,2)’s up o pa a opism [35].
A andom pa ial La in ec angle gene a ed in his way could ha e anywhe e be ween 1 and
min(x, s)en ies (p o ided x≥1), wi h he expec ed numbe o en ies g owing as he numbe
o a emp s xinc eases. Howe e , wo andom pa ial La in ec angles gene a ed by his p ocess
migh no ha e he same numbe o en ies, so we also conside he ollowing PLR se .
1.2.2 PLR Se B: Dele ing Random En ies. Assume n≥max{ ,s}. He e, we gene a e a andom
La in squa e o o de n, unca e i , and hen dele e en ies o ob ain a andom PLR( ,s,n)wi h
exac ly xen ies. Mo e speci ically:
(1) We use he Ma ko chain Mon e Ca lo algo i hm desc ibed by Jacobson and Ma hews
[51] using andom pe u ba ions o gene a e andom La in squa es o o de n ha a e
app oxima ely uni o mly dis ibu ed.
(2) We hen dele e he las n− ows and he las n−scolumns, which gi es a PLR( ,s,n)
wi h s en ies.
(3) We hen dele e s −x andom en ies, which gi es a PLR( ,s,n)wi h xen ies.
Figu e 1illus a es his p ocess. Impo an ly, he numbe o en ies is he independen a iable,
whe eas o PLR se A, he numbe o a emp s a adding an en y is he independen a iable.

1.12:6 R. J. S ones e al.
Table 1. The P obabili y o Gene a ing Each Pa ial La in Squa e in PLR(2,2,2)a e x=5A emp s
a Adding Random En ies, Sepa a ed In o G oupings ha Ha e Iden ical P obabili y;
P obabili ies we e Calcula ed Using Exhaus i e Compu a ion
(Classi ying all 85Possible Sequences o A emp s).
Fig. 1. Illus a ing he p ocess o gene a ing a andom PLR( ,s,n)wi h xen ies.
This p ocess does no gene a e x-en y PLR( ,s,n)’s uni o mly a andom o wo main easons:
(a) di e en x-en y PLR( ,s,n)’s comple e o s-en y PLR( ,s,n)’s in a di e en numbe o ways,
and (b) di e en s-en y PLR( ,s,n)’s may embed in a di e en numbe o La in squa es o o de
n. In ac , no e e y x-en y PLR( ,s,n)can be gene a ed. Fo example, o =s=n=2=x, he
ollowing PLR(2,2,2)canno be gene a ed, as i does no embed in a La in squa e o o de 2:
The Jacobson and Ma hews me hod gi es an asymp o ically uni o m dis ibu ion o andom La in
squa es [4]. I is indeed he gold s anda d o gene a ing andom La in squa es, al hough DeSal o
[25] has ecen ly claimed o imp o e upon his. In any case, he me hod o andomly gene a ing
La in squa es does no play a subs an ial ole in ou expe imen al esul s.
Compu ing Au o opism G oups o Pa ial La in Rec angles 1.12:7
2 AUTOTOPISMS OF PARTIAL LATIN RECTANGLES
2.1 In oduc ion
Le us s a wi h a cha ac e iza ion o he exis ence o an au o opism o a pa ial La in ec angle
wi h an unspeci ied symbol pe mu a ion, gi en speci ied ow and column pe mu a ions, αand β,
espec i ely.
Lemma 2.1. Le L∈PLR( ,s,n).I α∈S and β∈Ss, hen he e exis s γ∈Sn o which θ=
(α,β,γ)∈A op(L)i and only i
(1) L[α(i),β(j)]is de ined o all (i,j,L[i,j])∈En (L),and
(2) L[α(i),β(j)]=L[α(i),β(j)]whene e L[i,j]=L[i,j]∈[n].
The pe mu a ions γ o which θ∈A op(L)a e hose sa is ying γ(L[i,j])=L[α(i),β(j)], o all
(i,j,L[i,j])∈En (L).
P oo . Le θ=(α,β,γ)∈A op(L). Then, Condi ion 1 holds by de ini ion. I Condi ion 2 we e
alse, hen some wo en ies
(α(i),β(j),L[α(i),β(j)])=(i,j,L[i,j])θ
and
(α(i),β(j),L[α(i),β(j)])=(i,j,L[i,j])θ
disag ee a he hi d coo dina e, con adic ing he assump ion ha L[i,j]=L[i,j].
Now, assume Condi ions 1 and 2 hold o some α∈S and β∈Ss. We choose any mapγ:[n]→
[n] such ha γ(L[i,j])=L[α(i),β(j)] o all en ies (i,j,L[i,j])∈En (L), and such ha γis a pe -
mu a ion o he symbols in [n] ha do no occu in L. Condi ions 1 and 2 ensu eγis indeed a map.
Condi ion 2 u he implies γis injec i e, and hus γis a pe mu a ion o [n]. Since γis de ined
such ha En (L(α,β,γ))=En (L), we ha e an au o opism θ∈A op(L).
Lemma 2.1 also sugges s a back acking algo i hm o simul aneously de e mining whe he o
no αand βpa icipa e in an au o opism o Las espec i e ow and column pe mu a ions, and
iden i ying which hi d coo dina es γa e possible. This p ocedu e is desc ibed in Algo i hm 1.
Speci ically, he symbols k∈[n] o which γ(k)is le unde ined in Algo i hm 1a e hose ha
do no appea in L∈PLR( ,s,n). These symbols can be a bi a ily pe mu ed among hemsel es
and hence (α,β,γ)is an au o opism o L. This is es ablished o mally (and mo e gene ally) in
Lemma 2.2 below.
Lemma 2.2. Le Lbe a pa ial La in ec angle in he se PLR( ,s,n)wi h exac ly ≤ non-emp y
ows, s≤snon-emp y columns, and n≤nused symbols. Then,
A op(L)S − ×Ss−s×Sn−n×A op(L∗),
whe e L∗∈PLR( ,s,n)is he pa ial La in ec angle ha esul s om elimina ing he emp y ows
and columns o Land elabeling he symbols used in Lby using hose in [n]. Consequen ly,
|A op(L)|=( − )!(s−s)!(n−n)!|A op(L∗)|.
Algo i hm 1iden i ies e e y au o opism wi h i s and second componen s αand β, espec i ely.
An ou pu au o opism om ou implemen a ion migh look like
[?4??6?1]; [???5?63]; [???453?]
whe e ?deno es an unused ow, column, o symbol whe e α,β,o γis le unde ined, espec i ely
(and we index om 0 using C++). This s a es ha αcan be any pe mu a ion ha maps 1 → 4, 4 → 6,
and 6 → 1, and likewise o βand γ. Lemma 2.2 implies ha all such iso opisms a e au o opisms.
1.12:8 R. J. S ones e al.
ALGORITHM 1: Ex endAlphaBe a(α,β)
Requi e: L∈PLR( ,s,n), and pe mu a ions α∈S and β∈Ss
Ensu e: an au o opism (α,β,γ)∈A op(L),o ail i no such au o opism exis s
1: Se γ[k]←unde ined and γ−1[k]←unde ined o all k∈[n]
2: o all en ies (i,j,k)∈En (L)do
3: i L[α(i),β(j)]=unde ined hen
4: e u n ail {clash:en y(i,j,k)maps o an emp y cell}
5: end i
6: Se k←L[α(i),β(j)]{γmaps k o k}
7: i γ[k]=unde ined hen
8: Se γ[k]←kand γ−1[k]←k
9: else
10: i γ[k]k hen
11: e u n ail {clash:γalso maps k o some hing else}
12: end i
13: i γ−1[k]k hen
14: e u n ail {clash:γalso maps some hing else o k}
15: end i
16: end i
17: end o
18: e u n (α,β,γ)
2.2 En y In a ian s
An en y in a ian Pis any p ope y o he en ies o pa ial La in ec angles ha is p ese ed
unde au o opisms. Tha is, i Lis a pa ial La in ec angle, hen P(e)=P(eθ), o all e∈En (L)
and θ∈A op(L).
Lemma 2.3. Le L∈PLR( ,s,n). The ollowing p ope ies a e en y in a ian s o L.Fo each
(i,j,L[i,j])∈En (L):
(1) The numbe o en ies in ow i.
(2) The numbe o en ies in column j.
(3) The numbe o imes he symbol L[i,j]appea s in L.
(4) The numbe o dis inc symbols in he union o ow iand column j.
Example 2.4. We illus a e he hi d asse ion in Lemma 2.3 wi h a simple example.
On he igh -hand side abo e, we p esen he en y in a ian ma ix, which is ob ained by e-
labeling each en y in he pa ial La in ec angle L unde s udy by a posi i e in ege so (a) he
i s occu ences o hese in ege s appea in na u al o de ow-a e - ow; and (b) i he in a i-
an s associa ed o wo en ies coincide, hen hey a e elabeled by he same posi i e in ege . F om
Lemma 2.3, i wo non-emp y cells (i, j) and (i, j) wi hin his ma ix con ain dis inc posi i e
in ege s, hen no au o opism o L maps he en y (i, j, L[i, j]) o he en y (i, j, L[i, j]).He e,
his p ocedu e pa i ions he en y se o L in wo pa s, {(1, 1, 1), (2, 2, 1)} and {(1, 2, 2), (2, 3, 3)}.
Hence, each pa is ixed se -wise unde he ac ion o any au o opism o L.
Compu ing Au o opism G oups o Pa ial La in Rec angles 1.12:9
Le us see in he ollowing esul how he en y in a ian s desc ibed in Lemma 2.3 enable us
o ensu e ha compu ing he au o opism g oup o a gi en pa ial La in ec angle is as ha d as
deciding whe he wo gi en a bi a y g aphs a e isomo phic.
P oposi ion 2.5. The p oblem o compu ing he se o gene a o s o he au o opism g oup o a
pa ial La in ec angle is GI-comple e.
P oo . We ha e om Re e ence [88] (see also Sec ion 3.2.2 in his a icle) ha e e y pa ial
La in ec angle Lis uniquely ela ed o a bipa i e g aph so he au o opism g oup o he o me is
isomo phic o a subg oup o he au omo phism g oup o he la e . Thus, o p o e he esul , le us
see ha e e y bipa i e g aph G=(V(G),E(G)) may be embedded in o a pa ial La in ec angle
L(G)so he se o gene a o s o he au omo phism g oup Au (G)o he g aph Gmay be ob ained
om he se o gene a o s o he au o opism g oup A op(L(G)). Then, he esul would ollow om
he known ac ha compu ing a se o gene a o s o he au omo phism g oup o a gi en bipa i e
g aph is GI-comple e [12].
Le ebe he numbe o edges o he bipa i e g aph Gand le us suppose ha he se o e ices
V(G)is bipa i ioned in o a se o ed e ices R(G)={ 1,..., }and a se o ccyan e ices
C(G)={w1,...,wc},soe e yedgeinE(G)is inciden o bo h a ed and a cyan e ex. Wi hou
loss o gene ali y, we can also suppose ha ≤c≤e,e>1 and ha no isola ed e ices exis in
G.Then,le usde inean( +2e)×(c+2e)pa ial La in ec angle L(G)con aining symbols om
he se [( +c−1)e]∪{·}by ollowing he nex ou s ages, whe e, om now on, d( )and N( )
deno e, espec i ely, he deg ee and he neighbo hood o a e ex ∈V(G).
(a) Each ed e ex i∈R(G)is uniquely associa ed wi h Row icon aining he se o en ies
⎧
⎪
⎨
⎪
⎩
i,
i−1

m=1
d( m)+k,
i−1

m=1
d( m)+k
:1≤k≤d( i)⎫
⎪
⎬
⎪
⎭
in En (L(G)). Each one o hese en ies is uniquely ela ed o an edge inciden wi h he
e ex i. Mo eo e , he symbol assigned o he o me may be conside ed as a label o he
la e . Hence, once his s age inishes, one can de ine a labeling
Lab : E(G)→[e]
iwj→Lab( iwj).
(b) Each cyan e ex wjis uniquely associa ed wi h Column e+jcon aining he se o en ies
⎧
⎪
⎨
⎪
⎩
 +
j−1

m=1
d(wm)+k,e+j,sk
:1≤k≤d(wj),sk∈{Lab( wj): ∈N(wj)}⎫
⎪
⎬
⎪
⎭
in En (L(G)),whe eskski kk. Then, simila ly o he p e ious s age, each one o
hese en ies is uniquely ela ed o an edge inciden wi h he e ex wj.
(c) Fo each posi i e in ege s∈{e+1,..., e}, we in oduce a se ies o ex a en ies o he
o m
(i,c+e+j,s)∈En (L(G)),
o some a bi a y posi i e in ege s i≤ and j≤e,so hei h ow o L(G)has exac ly e
en ies, o all i≤ .
(d) Fo each posi i e in ege s∈{ e +1,...,( +c−1)e)}, we in oduce a se ies o ex a en ies
o he o m
( +e+i,e+j,s)∈En (L(G)),
o some a bi a y posi i e in ege s i≤eand j≤c,so he(e+j) h column o L(G)has
exac ly een ies, o all j≤c.
1.12:16 R. J. S ones e al.
Fig. 4. The a e age un ime o he en ywise back acking me hods, wi h and wi hou he use o SEIs and/o
squa e in a ian s (sq.); pa ame e s ( ,s,n)=(5,5,5).
ALGORITHM 4: En ywiseBack acking( )
Requi e: L∈PLR( ,s,n)wi h men ies
Ensu e: au o opism g oup A op(L)
1: Se A op(L)←∅
2: Se α[i]←unde ined and α−1[i]←unde ined and αcoun [i]←0 o alli∈[ ]
3: Se β[j]←unde ined and β−1[j]←unde ined and βcoun [j]←0 o allj∈[s]
4: Se γ[k]←unde ined and γ−1[k]←unde ined and γcoun [k]←0 o allk∈[n]
5: Se i←e [1] and j←e [2] and k←e [3]
6: o all u∈[m]do
7: Se a←eu[1] and b←eu[2] and c←eu[3] {we y mapping (i,j,k) o (a,b,c)}
8: i En yChecks((i,j,k),(a,b,c)) e u ns ail hen
9: con inue {Algo i hm 5}
10: end i
11: Se α[i]←aand α−1[a]←iand αcoun [i]←αcoun [i]+1
12: Se β[j]←band β−1[b]←jand βcoun [j]←βcoun [j]+1
13: Se γ[k]←cand γ−1[c]←kand γcoun [k]←γcoun [k]+1
14: i =m hen
15: Add (α,β,γ) o A op(L)
16: else
17: En ywiseBack acking( +1)
18: end i
19: Se αcoun [i]←αcoun [i]−1andβcoun [j]←βcoun [j]−1andγcoun [k]←γcoun [k]−1
20: i αcoun [i]=0 hen
21: α[i]←unde ined and α−1[a]←unde ined
22: end i
23: i βcoun [j]=0 hen
24: β[j]←unde ined and β−1[a]←unde ined
25: end i
26: i γcoun [k]=0 hen
27: γ[k]←unde ined and γ−1[a]←unde ined
28: end i
29: end o

Compu ing Au o opism G oups o Pa ial La in Rec angles 1.12:17
ALGORITHM 5: En yChecks((i,j,k),(a,b,c))
1: i en y in a ian Pis being used and P((i,j,k)) P((a,b,c)) hen
2: e u n ail {en ies (i,j,k)and (a,b,c)ha e di e en en y in a ian s}
3: end i
4: i ow in a ian PRis being used and PR(i)PR(a) hen
5: e u n ail { ows iand aha e di e en ow in a ian s}
6: end i
7: i column in a ian PCis being used and PC(j)PC(b) hen
8: e u n ail {columns jand bha e di e en column in a ian s}
9: end i
10: i α[i]unde ined and α[i]a hen
11: e u n ail {clash:αalso maps i o some hing else}
12: end i
13: i α−1[a]unde ined and α−1[a]i hen
14: e u n ail {clash:αalso maps some hing else o a}
15: end i
16: i β[j]unde ined and β[j]b hen
17: e u n ail {clash:βalso maps j o some hing else}
18: end i
19: i β−1[b]unde ined and β−1[b]j hen
20: e u n ail {clash:βalso maps some hing else o b}
21: end i
22: i γ[k]unde ined and γ[k]c hen
23: e u n ail {clash:γalso maps k o some hing else}
24: end i
25: i γ−1[c]unde ined and γ−1[c]k hen
26: e u n ail {clash:γalso maps some hing else o c}
27: end i
As indica ed in he in oduc o y sec ion, he au o opism g oup o a pa ial La in ec angle Lmay
be compu ed ia g aph au omo phisms. This gene ally ollows a h ee-s ep p ocess:
(1) Compu e some g aph G om L.
Such a g aph has o be chosen so we ha e some mechanism o compu ing he au o opism
g oup A op(L) om he au omo phism g oup Au (G)(which is S ep 3 below). The p oce-
du e o compu ing he au o opism g oup A op(L) a ies wi h such a choice.
(2) Compu e he au omo phism g oup Au (G).
In his wo k, we pe o m his compu a ion using nau y. Fo he pu pose o his a icle,
nau y unc ions like a “black box”: We inpu a g aph and nau y ou pu s i s au omo phism
g oup.
(3) Compu e he au o opism g oup A op(L) om he au omo phism g oup Au (G).
In addi ion o being able o lis he au omo phisms o he g aph, nau y also ou pu s a unc ion
called o bi s, which gi es he ines possible e ex in a ian pa i ion ( ha is, o wo e ices u
and in he same pa , he e is an au omo phism ha maps u o ).
In he g aphs we s udy, he e ex se is o con ains he se o en ies En (L) o some pa ial
La in ec angle L∈PLR( ,s,n). In hese cases, en y in a ian s can be used o colo hese e ices.
In gene al, his colo ing does no co espond o a e ex in a ian , as i migh no be p ese ed
unde all au omo phisms o he g aph. Howe e , he au omo phisms ha ha e been des oyed by
colo ing he e ices do no co espond o au o opisms o L.
1.12:18 R. J. S ones e al.
Fig. 5. Con e ing a pa ial La in ec angle Lin o i s ela ed e ex-colo ed McKay, Meyne , and My old
g aph GL.
3.2.1 Adap ed McKay, Meyne , and My old Me hod. We adap he me hod by McKay, Meyne ,
and My old (MMM) [68] o pa ial La in ec angles. We de ine he e ex-colo ed g aph GLby
V(GL):=En (L)∪{Ri:i∈[ ] and ow io Lis non-emp y},
∪{Sj:j∈[s]andcolumnjo Lis non-emp y},
∪{Nk:k∈[n]andsymbolkoccu s in L},
and assign each o he ou e ex subse s En (L),{Ri},{Sj},and{Nk}a dis inc e ex colo . We
also de ine he edge se
E(GL):={eRi,eSj,eNL[i,j]:e:=(i,j,L[i,j])∈En (L)}.
Figu e 5gi es an example o his cons uc ion. By es ic ing Au (GL) o he e ices En (L),we
de e mine A op(L)(up o pe mu a ions o emp y ows and columns, and unused symbols).
I is easily e i ied ha he implemen a ion o he colo e inemen algo i hm (which pa i ions
he e ices o a g aph acco ding o hei i e a ed deg ee sequence) o he g aph GL o make as e
he compu a ion o hei au omo phism g oup is equi alen o he implemen a ion o he exhaus-
i e na u al e inemen (desc ibed in Sec ion 2.2.1) o he pa ial La in ec angle L o imp o ing
he compu a ion o i s au o opism g oup. Mo e speci ically, he deg ee o he e ices Ri,Sj,and
Nkcoincide, espec i ely, wi h he numbe o en ies in he i h ow o L, he numbe o en ies in
he j h column o L,and he numbe o imes he symbol kappea s in L.
3.2.2 Bipa i e G aph Me hod. Fo each L∈PLR( ,s,n),weconside he(0,1)-ma ix de ined
as M=M[i,j] ×swi h M[i,j]=1 i and only i L[i,j] is de ined. This ma ix is called he shape
[29,35]o Land can be in e p e ed as he biadjacency ma ix o a bipa i e g aph BM,whe eone
bipa i ion co esponds o he ows, and he o he o he columns. An example is d awn in Figu e 6.
The pai s o pe mu a ions (α,β)∈S ×Ssac on hese o ×s(0,1)-ma ices by pe mu ing
he ows by αand he columns by β;wede ineanau o opism o a (0,1)-ma ix as a s abilize unde
his g oup ac ion. The g oup A op(L)is isomo phic o a subg oup o he au o opism g oup o M.
This gi es ise o wo ways o compu ing A op(L):
(1) Use nau y o compu e he au omo phism g oup o BM. This de e mines he au o opism
g oup o M, om which we check each (α,β)in he au o opism g oup o M o see i i
de ines an au o opism o L h ough Lemma 2.1.
(2) Use nau y o compu e he o bi s o BM, which pa i ion [ ] and [s]. The la e a e, e-
spec i ely, p ese ed by αand βin any au o opism (α,β,γ)o L.We henapplyoneo
Compu ing Au o opism G oups o Pa ial La in Rec angles 1.12:19
Fig. 6. Con e ing a pa ial La in ec angle Lin o i s co esponding bipa i e g aph. Edge colo s a e no
included in he g aph, bu a e included in he igu e o illus a e how he cons uc ion wo ks.
he back acking me hods o Sec ion 3.1 wi h he added condi ion ha hese pa i ions a e
p ese ed.
No ice in pa icula ha he implemen a ion o he colo e inemen algo i hm in he g aph BM
de i es om he use o he SEIs (in his case, wi hou using he appea ances o symbols).
3.2.3 Pa ial La in Rec angle G aph Me hod. We de ine he edge-colo ed g aph Γcolo
Lwi h e -
ex se V(Γcolo
L):=En (L)and:
•g een edges be ween wo dis inc en ies i hey sha e a ow,
•o ange edges be ween wo dis inc en ies i hey sha e a column, and
•pu ple edges be ween wo dis inc en ies i hey sha e a symbol.
I is known [40] ha any au omo phism o Γcolo
Lis equi alen o an au o opism o L.Speci i-
cally, i he e ex (i,j,L[i,j])maps o (i,j,L[i,j])in Γcolo
L, hen he en y (i,j,L[i,j])maps o
(i,j,L[i,j])in L. Thus, we can di ec ly compu e he au o opism g oup o Lby compu ing he
au omo phism g oup o Γcolo
Lusing g aph au omo phism so wa e—no u he il e ing is needed.
Howe e , nau y does no allow i s inpu g aphs o ha e edge colo s. We conside wo ways
o o e come his. The i s one is o simply igno e he edge colo s, which we deno e ΓL, hen
check each au omo phism o ΓL e u ned by nau y o see i i co esponds o an au o opism o L.
The second me hod consis s o de ining a new non-edge-colo ed g aph ΓLwhose au omo phisms
co espond o hose o he edge-colo ed g aph Γcolo
L(see Figu e 7). I has e ex se
V(ΓL):=En (L)∪{Re:e∈En (L)}∪{Se:e∈En (L)}∪{Ne:e∈En (L)},
whe e each one o he ou e ex subse s appea ing as ope ands o he unions abo e is monoch o-
ma ic, bu any wo o hem ha e dis inc e ex colo s; and edge se
E(ΓL):={eRe,eSe,eNe:e∈En (L)}
∪{Re1Re2: dis inc en ies e1and e2belong o he same ow}
∪{Se1Se2: dis inc en ies e1and e2belong o he same column}
∪{Ne1Ne2: dis inc en ies e1and e2sha e he same symbol}.
The g aph ΓLhas mo e e ices han ΓL,sonau y akes longe o compu e i s au omo phism
g oup. Howe e , he au omo phism g oup o ΓL, when es ic ed o he e ices in he pa En (L),
gi es he au o opism g oup o Ldi ec ly (i.e., no u he il e ing is equi ed). I is also possible o
use en y in a ian s o colo he e ices in En (L)o ΓLo e ining he e ex colo ing o ΓL.
1.12:20 R. J. S ones e al.
Fig. 7. Con e ing a pa ial La in ec angle Lin o i s co esponding edge-colo ed pa ial La in ec angle
g aph Γcolo
L, and a e ex-colo ed non-edge-colo ed g aph ΓLwi h he same au omo phism g oup as he
edge-colo ed ΓL o use in nau y.
One mo e ime, and simila ly o he adap ed MMM me hod, he implemen a ion o he colo
e inemen algo i hm in bo h g aphs ΓLand ΓLis uniquely ela ed o he use o SEIs. The same
happens in he ollowing me hod.
3.2.4 Rook’s G aph Me hod. We de ine he edge-colo ed g aph Ξcolo
L om he pa ial La in
ec angle g aph Γcolo
Lby dele ing he pu ple edges; we also de ine ΞL om Ξcolo
Lby igno ing he
edge colo s. Thus, ΞL o ms an induced subg aph o he ook’s g aph ( ha is, he Ca esian p oduc
o K and Ks). Any au o opism o Lis equi alen o an au omo phism o ΞL. The con e se does
no necessa ily hold, so a e nau y has been called, we check each au omo phism o ΞL o see i
i co esponds o an au o opism o L. Di e ing om pa ial La in ec angle g aphs, we de ine ΞL
wi h
V(ΞL):=En (L)∪{Re:e∈En (L)}∪{Se:e∈En (L)}∪{k∈[n]: symbolkappea s in L},
whe e he unions abo e indica e dis inc e ex colo s, and edge se
E(ΞL):={eRe,eSe:e∈En (L)}
∪{Re1Re2: dis inc en ies e1and e2belong o he same ow}
∪{Se1Se2: dis inc en ies e1and e2belong o he same column}
∪{Rek:e∈En (L)and ehas symbol k}
∪{Sek:e∈En (L)and ehas symbol k}.
Figu e 8 illus a es his g aph. I is also possible o use en y in a ian s o colo he e ices in E(L)
in bo h ΞL and ΞL. As wi h ΓL, he au omo phism g oup o ΞL, when es ic ed o he e ices in
hepa En (L), gi es he au o opism g oup o L di ec ly.
3.2.5 Addi ional Rema ks. Fo an m-en y PLR( , s, n) wi h no unused ows, columns, no sym-
bols, Table 2 abula es he numbe o e ices and edges in he a o emen ioned g aphs.
An al e na i e way o achie ing an edge-colo ed e sion o ΓL o ΞL would be o subdi ide each
colo ed edge, colo ing he e ex used o subdi ide i acco ding o he edge colo . This is illus a ed
below Table 2 in hecaseo ΓL.
Compu ing Au o opism G oups o Pa ial La in Rec angles 1.12:21
Fig. 8. Con e ing a pa ial La in ec angle Lin o i s co esponding edge-colo ed induced subg aph o he
ook’s g aph ΞL, and a e ex-colo ed non-edge-colo ed g aph ΞLwi h he same au omo phism g oup as
he edge-colo ed ΞL o use in nau y.
Table 2. The Numbe o Ve ices and Edges in an
m-en y PLR( ,s,n)wi h no Unused Rows,
Columns, no Symbols
no. e ices no. edges
MMM g aph m+ +s+n3m
bipa i e g aph +sm
PLR g aph ΓLmp∈0,...,m
2
PLR g aph ΓL4m3m+p
ook’s g aph ΞLmq∈0,...,m
2
ook’s g aph ΞL3m+n4m+q
No e:Wemus ha eq≤p.
In his se ing, his subdi ided e sion o ΓLis simila o he McKay, Meyne , and My old
(MMM) g aph. Mo e speci ically, i is equi alen o aking he MMM g aph and eplacing each Ri
wi h deg(Ri)
2 e ices, each connec ed o a dis inc pai o neighbo s o Ri, and likewise o Sjand
Nk. I has be ween m+pand 2pedges, wi h 0 ≤p≤m
2.
The subdi ided e sion o ΞLis simila o he subdi ided e sion o ΓL, bu we dele e he e ices
Nk, so he au omo phism g oup o he g aph will also no di ec ly gi e he au o opism g oup o
he pa ial La in ec angle. I has be ween m+q e ices and 2qedges, wi h 0 ≤q≤m
2.
We choose no o include hese g aphs in ou expe imen s, as we expec hem o be in e io o
he MMM g aph, pa icula ly when mis much la ge han ,s,andn. Mo eo e , unlike he MMM
g aph, he au omo phism g oup o he subdi ided e sion o ΞLdoes no di ec ly gi e A op(L).

1.12:22 R. J. S ones e al.
We also choose no o include a ipa i e g aph e sion, wi h e ex ipa i ion {Ri}∪{Sj}∪
{Nk}and iangles RiSjNkwhene e L[i,j]=k. Fo La in squa es o o de n, his g aph would be
isomo phic o Kn,n,nand using nau y o compu e i s au omo phism g oup would no be help ul.
4 EXPERIMENTS
A se ies o expe imen s es ing he e iciency o all he algo i hms desc ibed in he p e ious sec ion
ha e been implemen ed in C++, whose sou ce codes a e a ailable in h ps://si es.google.com/si e/
ebeccajs ones/home/a op. a .gz.
4.1 Se up
In ou expe imen s, we se he goal o compu ing he au o opism g oup size. While all o he de-
sc ibed me hods a e capable o gene a ing each elemen in he au o opism g oup (and we ac ually
pe o m his ask o he co ec ness ce i ica e; see Sec ion 4.1.1), he an icipa ed use o such so -
wa e may o may no need such a lis . Howe e , some o he desc ibed me hods canno compu e he
au o opism g oup size wi hou gene a ing each elemen in he au o opism g oup, speci ically he
back acking me hods. O he me hods equi e il e ing nau y’s esul s, which we do by checking
each elemen one-by-one. The h ee me hods ha do no need o gene a e he whole au o opism
g oup a e:
•The MMM me hod.
•The e ex-colo ed pa ial La in ec angle g aph me hod.
•The e ex-colo ed ook’s g aph me hod.
In hese cases, nau y gi es gene a o s o he au omo phism g oups o he inpu g aphs, which a e
su icien o de e mine he au o opism g oup size. In all o he cases, we use nau y o gene a e he
whole au omo phism g oup, since he au o opism g oup o he inpu pa ial La in ec angle is only
isomo phic o a subg oup o he au omo phism g oup compu ed by nau y.
The six amilies o algo i hms o compu ing au o opism g oups ha ha e been discussed
h oughou he a icle ( wo back acking algo i hms in Sec ion 3.1 and ou g aph- heo e ic algo-
i hms in Sec ion 3.2), oge he wi h he di e en au o opism in a ian s ha we ha e men ioned
(column ec o s, SEIs, squa e in a ian s, and e ex in a ian s), gi e ise o 47 dis inc me hods
o compa e. We i s un some es s o e i y ha hese 47 me hods unc ion co ec ly. A e his,
we compa e he 47 me hods expe imen ally o deduce he i e bes me hods, which a e used o
u he expe imen a ion.
Unless o he wise speci ied, we calcula e he a e age un ime o e 10K andom PLR( , s, n)’s o
some ixed pa ame e s , s,and n. We do his o each alue o he independen a iable x o he
wo es se s desc ibed in Sec ion 1.2. No e ha he independen a iable x is di e en o he wo
es se s.
The expe imen al pla o m has an In el Co e i7-4700MQ, 2.40 GHz p ocesso ( ou physical
co es) wi h 7895 MiB RAM unning Linux Min 19 (64-bi ). The code was w i en in C++ (wi hou
pa allelism, using s a ic memo y alloca ion) and compiled using G++ e sion 7.3.0 wi h -O3 op i-
miza ion. Whe e possible, he same code is e-used o each me hod. Pa ial La in ec angles a e
in e nally s o ed as lis s o en ies.
4.1.1 Co ec ness. Be o e he expe imen al p og am execu es, a “co ec ness ce i ica e” is gen-
e a ed. We pe o m he compu a ion o he au o opism g oup o se en di e en inpu pa ial La in
ec angles, choosing he ollowing a ie y o inpu s:
.
Compu ing Au o opism G oups o Pa ial La in Rec angles 1.12:23
•A andom La in squa e o o de i e.
•A andom La in squa e o o de nine ha has been unca ed o ha e i e ows and se en
columns.
•A andom La in squa e o o de six ha has had ou en ies dele ed.
•A andom La in squa e o o de 20 ha has been unca ed o ha e 10 ows and 10 columns,
hen has had 10 en ies dele ed.
•A andomPLR(7,8,9)a e 100 ies a adding a andom en y.
•A andomPLR(8,8,8)a e 10K ies a adding a andom en y.
•A andomPLR(7,7,7)a e 3 ies a adding a andom en y.
Each o he 47 me hods es ed p in s ou hei compu ed au o opism g oup o he same inpu ,
which is used o e i y he compu a ions a e consis en . Mo eo e , a VERBOSE mode has been
implemen ed in he C++ code, which i se , p in s ou he 47 au o opism g oup sizes compu ed o
he i s 20 samples in each expe imen . These checks a e no pe o med du ing expe imen a ion,
since i would in e e e wi h he un ime measu emen s.
4.2 Choosing which o Compa e
We pe o m some ini ial expe imen s o e all 47 me hods and a ia ions, o
( ,s,n)∈{(5,5,5),(5,5,6),(5,6,6),(5,6,7)}.
Based on hese esul s, we elimina e six me hods ha would make subsequen expe imen s im-
p ac ical o conduc , because o being simply oo slow:
(1)α-βback acking,(4)PLR g aph (nau y,EC,SEI),
(2)en ywise back acking,(5)Rooksg aph(nau y,EC),and
(3)PLR g aph (nau y,EC),(6)Rooksg aph(nau y,EC,SEI).
Rega ding PLR se B o ( ,s,n)=(5,5,5), he e a e only wo species o La in squa e o o de
i e: one has an au o opism g oup o o de 120 ( he Cayley able o Z5) and he o he one has
an au o opism g oup o o de 12 ( o med by comple ing a 2 ×2 subsqua e o a La in squa e o
o de i e). Thus, when we gene a e a andom La in squa e o o de i e, he esul mus be an
au o opism g oup o o de ei he 120 o 12. This si ua ion is unlike andom La in squa es o la ge
o de , which ha e i ial au o opism g oups wi h high p obabili y [71]. Consequen ly, he un ime
beha io o such small ( ,s,n)may di e signi ican ly o he beha io o la ge ( ,s,n).
4.3 Expe imen al Resul s
4.3.1 Run- ime Expe imen s. Figu e 9plo s he bes and a e age un imes o he 41 emaining
me hods o ( ,s,n)=(7,7,7). No ice ha no single me hod is consis en ly bes o e all inpu s.
Indeed, simple back acking me hods a e as e in many ins ances: O he me hods a e delayed
by he ime spen compu ing in a ian s and con e ing g aphs o nau y’s in e nal g aph o ma .
Fu he , Figu e 9also shows a signi ican di e ence in un imes be ween “spa se” and “dense”
pa ial La in ec angles. This gi es he mo i a ion o in es iga e hese wo si ua ions sepa a ely.
4.3.2 Ins abili y. Figu e 10 illus a es some me hods showing ins abili y on PLR Se A. We ex-
pec his ins abili y a ises because dense PLRs (pa icula ly La in ec angles and La in squa es)
incu signi ican ly highe un imes han spa se PLRs. The me hod used o gene a e andom PLRs
in PLR Se A (which adds non-clashing en ies andomly) spo adically gene a es dense PLRs and
hence spo adically leads o signi ican ly highe un imes. This ins abili y is an impo an design
1.12:24 R. J. S ones e al.
Fig. 9. The bes and a e age un imes o ( ,s,n)=(7,7,7) o he 41 me hods (excluding 6 me hods ha
a e oo slow o pe o m, as desc ibed in he main ex ). We ma k which amily o me hods achie es he bes
un ime.
Fig. 10. The un imes o ( , s, n) = (7, 7, 7) o me hods ha indica e some ins abili y.
conside a ion o a use s udying PLRs gene a ed ia a me hod akin o he me hod o PLR Se A
(like S ones [85]). This issue does no a ise in PLR Se B.
No ice ha Figu e 10 shows some “spikes” in un imes common o se e al me hods, while o he
“spikes” a e no common. We a ibu e his p ope y o spo adically encoun e ing andom PLRs
ha happen o ha e many au o opisms.
The α-β and en ywise bipa i e g aph me hods (which only u ilize nau y’s o bi s) incu a sig-
ni ican un ime o e head when he pa i ions de e mined by nau y’s o bi s con ain la ge pa s.
This is unlike he plain bipa i e g aph me hod (which uses nau y’s in e nal unc ions o i e a ing
h ough au omo phisms o he bipa i e g aph).
4.3.3 En y In a ian s. When using en y in a ian s, we o en deduce ha he au o opism
g oup is i ial (up o he au o opisms coun ed in Lemma 2.2). In hese cases, u he compu a-
ion is no equi ed. Figu e 11 plo s he p opo ion o pa ial La in ec angles ha equi e u he
compu a ion when ( , s, n) ∈{(7, 7, 7), (7, 7, 8), (7, 8, 8), (7, 8, 9)}.
We ind ha en y in a ian s a e ine ec i e when a PLR has e y ew en ies (likely because he
PLR has non- i ial au o opisms). Fu he , while SEIs a e mo e e icien o compu e han squa e
in a ian s, Figu e 11 indica es ha squa e in a ian s a e mo e use ul a educing subsequen
.
Compu ing Au o opism G oups o Pa ial La in Rec angles 1.12:25
Fig. 11. The p opo ion o pa ial La in ec angles o which u he compu a ion is equi ed, i.e., en y in-
a ian s alone canno p o e a i ial au o opism g oup.
Fig. 12. The a e age un ime o he α-βback acking me hod wi h SEIs (le ) and he p opo ion o pa ial
La in ec angles o which u he compu a ion is equi ed when using SEIs ( igh ).
compu a ion when he e a e many en ies. Ne e heless, squa e in a ian s also become less use ul
as he densi y o he pa ial La in ec angle inc eases.
We conclude ha some imes i is wo hwhile spending addi ional ime in compu ing sophis i-
ca ed en y in a ian s (such as o dense pa ial La in ec angles), and some imes i is no wo h-
while (e.g., when he quickly compu ed SEI su ices o deduce a i ial au o opism g oup).
4.3.4 Spa se PLRs. We de ine an ×spa ial La in ec angle as spa se i i s numbe o en ies
is a mos 0.9 s. The mo i a ion behind his 0.9 ac o h eshold is expe imen al.
The i s conclusion o ou expe imen s is ha he p ecise alues o ,s,andndo no ha e
a majo e ec on he a e age un imes o spa se pa ial La in ec angles. In con as , o dense
pa ial La in ec angles, he e is a signi ican di e ence be ween he s=nand s=n−1cases.
Figu e 12 (le ) plo s he a e age un ime o he α-βback acking me hod (using SEIs) o a -
ious ( ,s,n) iples. This me hod consis en ly encoun e s huge un imes wi h especially spa se
pa ial La in ec angles. Some e sions o he bipa i e g aph me hod also ha e he p oblem wi h
especially spa se pa ial La in ec angles.
Figu e 13 plo s he a e age un ime o he en ywise back acking me hod using SEIs o squa e
in a ian s o a ious ( ,s,n) iples. We see ha his me hod is easonably s able and does no en-
coun e he same p oblem as he α-βback acking me hod as in Figu e 12.WealsoseeinFigu e13
ha he squa e-in a ian un ime inc eases almos linea ly wi h densi y o equi alen ly wi h he
numbe o en ies (wi h he g adien de e mined by s).
1.12:32 R. J. S ones e al.
Example 5.1. Le us conside he ollowing pa ial La in squa e o o de six.
L≡
1· · 2· ·
·3· · 4·
· · 5· · 6
2· · 1· ·
·4· · 3·
· · 6· · 5
The o de ed se E={(1,1,1),(2,2,3),(3,3,5)}cons i u es a base o he au o opism g oup
A op(L).Top o ei ,le θ=(α,β,γ)∈A op(L)be a poin wise s abilize o he se E. Sinceδ(i)=i,
o all δ∈{α,β}and i∈{1,2,3},i mus beδ(j)=j, o all j∈{4,5,6}. As a consequence, he au-
o opism θis indeed he i ial pe mu a ion in he symme ic g oup S6.
The implemen a ion o ou heo e ical g aph me hods in nau y (wi h he ex a colo ing o hose
e ices ela ed o he co esponding poin wise s abilize ) enables us o ensu e ha
A op(L)(2)=((2356),(2356),(35)(46)),((2653),(2356),(36)(45)),((36),(36),Id),((36),Id,(56)) 
and
A op(L)(3)=((36),(36),Id),((36),Id,(56)) .
In pa icula ,
•|A op(L)(3):A op(L)(4)|=4, because
A op(L)(3)((3,3,5)) ={(3,3,5)(3,6,6),(6,3,6),(6,6,5)};and
•|A op(L)(2):A op(L)(3)|=8, because
A op(L)(2)((2,2,3)) =En (L) {(1,1,1),(1,4,2),(4,1,2),(4,4,1)}.
Fu he mo e, we ha e ha he i e au o opisms
((Id,(14),(12)),((14),Id,(12)),((14),(14),Id),
((12)(45),(12)(45),(13)(24)) and ((13)(46),(13)(46),(15)(26))
o he pa ial La in squa e L map, espec i ely, he en y (1, 1, 1) o he en ies (1, 4, 2), (4, 1, 2),
(4, 4, 1), (2, 2, 3), and (3, 3, 5). This ac , oge he wi h he al eady desc ibed se s A op(L)(3) ((3, 3, 5))
and A op(L)(2) ((2, 2, 3)), enables us o ensu e ha he o bi o he en y (1, 1, 1) unde he ac ion o
he au o opism g oup A op(L) is he whole en y se En (L). In ac , he au o opism g oup A op(L)
ac s ansi i ely on he en y se En (L). Hence, om Equa ion (1), we ha e ha |A op(L)| =
12 · 8 · 4 = 384.
Ou side o cases wi h ew en ies, when wo king wi h andomly gene a ed PLRs, compu a ion
mos ly e i ies ha a PLR has a i ial au o opism g oup, unless some speci ic s uc u e is imposed
on he da ase . In hese cases, in a ian s usually play a undamen al ole. Ne e heless, as we a e
going o show now, one can ind pa ial La in ec angles o which hese in a ian s a e no use ul.
Choice o in a ian s. En y in a ian s show a ying use ulness as he expe imen al pa ame e s
change. This is mainly due o he exis ence o pa ial La in ec angles o which he p oposed en y
in a ian s (mo e speci ically, SEIs and squa e in a ian s) do no gi e any ex a in o ma ion abou
hei au o opism g oups. Thus, o ins ance, i is eadily e i ied ha SEIs a e no use ul o dealing
wi h La in squa es. In any case, ullness is no a manda o y condi ion o inding his ype o ha d
case. Thus, o ins ance, nei he SEIs no squa e in a ian s a e use ul o deal wi h he pa ial La in

Compu ing Au o opism G oups o Pa ial La in Rec angles 1.12:33
squa e desc ibed in Example 5.1. The same happens, o example, wi h he ollowing pa ial La in
ec angles.
1 2 ·
2·1
·1 2
1· · 2· ·
·3· · 2·
· · 1· · 3
Fu he mo e, he e a e pa ial La in ec angles wi h non- i ial au o opism g oups o which
none o he p oposed en y in a ian s gi es he ines pa i ion o ows and columns o de e mine
hei au o opism g oups explici ly. The al eady-men ioned app oach conce ning bases o au o-
opism g oups may also be use ul o dealing wi h hese kinds o pa ial La in ec angles. This
occu s in he ollowing example, which has also been conside ed by he au ho s in a ecen pape
[23].
Example 5.2. Le us conside he ollowing pa ial La in squa e o o de nine:
L≡
·94287·5 1
· · · 3· · 6· ·
8 5 7 4 1 · · 9 2
5·1 8 7 9 ·2 4
9 2 5 7 4 1 ·8·
4 7 2 1 9 8 · · 5
1 4 ·9 2 5 ·7 8
· · · 6· · 3· ·
7 1 8 5 ·2·4 9
The e inemen me hods desc ibed in Re e ence [23], which include in pa icula bo h SEIs and
squa e in a ian s, es ablish 512,096,256,000 possible candida es o he au o opism g oup A op(L),
whose size is, howe e , 14. Mo e speci ically, all o hese candida es p ese e he ollowing se s o
ows, columns, and symbols, whe e ows and columns a e labeled in na u al o de .
•The wo se s o ows {1,3,4,5,6,7,9}and {2,8}.
•The h ee se s o columns {1,2,3,5,6,8,9},{4},and {7}.
•The wo se s o symbols {1,2,4,5,7,8,9}and {3,6}.
To obse e he e iciency o dealing wi h a base o he au o opism g oup A op(L), le us conside ,
o ins ance, he o de ed se {(1,9,1),(2,4,3)}⊂En (L). I cons i u es a base o A op(L),because
he only non- i ial au o opism o Lp ese ing he en y (1,9,1)is ((28),Id,(36)) ∈A op(L).This
ac also enables us o ensu e ha |A op(L)(2):A op(L)(3)|=2.
F om Equa ion (1), he size o he au o opism g oup is uniquely de e mined by he o bi o he
en y (1,9,1)unde he ac ion o A op(L). To compu e such an o bi , we ha e made a epe i i e
use o he PLR me hod. Mo e speci ically, besides he usual desc ip ion o ha me hod, we ha e
colo ed in an exclusi e and equal way bo h he e ex co esponding o he en y (1,9,1)and a
di e en e ex co esponding o any o he o he en ies. In his way, hose e ex-colo ed g aphs
o which a non- i ial au omo phism exis s de e mine he o bi o he en y (1,9,1). Acco ding
o nau y, hey co espond o he six e ices
(3,8,9),(4,5,7),(5,2,2),(6,1,4),(7,6,5),and (9,3,8).
Toge he wi h he i ial au o opism, i enables us o ensu e ha |A op(L)(1):A op(L)(2)|=7, and
hence, om Equa ion (1), ha he size o he au o opism g oup A op(L)is 14.
1.12:34 R. J. S ones e al.
Fu he , we eel ha so wa e o compu ing au o opism g oups would bene i om dynamically
choosing which en y in a ian o use.
(1) In e media e numbe o en ies. A cheap- o-compu e en y in a ian (such as he SEI) is
usually su icien o p o e a i ial au o opism g oup in his se ing, and hus compu ing
mo e sophis ica ed en y in a ian s would be was e ul.
(2) La ge numbe o en ies. In his se ing, he SEI is no longe e ec i e, and we should
use mo e sophis ica ed en y in a ian s. Mo eo e , we obse ed a “ ap” in Sec ion 4.3.6,
whe e so ing a la ge numbe o simila en y in a ian s pe o ms slowly, which is im-
po an o a oid.
(3) La in squa es. Figu e 16 indica es ha me hods o compu ing au o opism g oups o PLRs
will likely no wo k o La in squa es. The un imes a e wildly di e en o La in squa es
and pa ial La in ec angles in gene al, so we hink o his as a sepa a e p oblem.
O he en y in a ian s may be mo e use ul han he simple ones we p opose he e. Fo example, i
may be possible o adap he “ ain” en y in a ian by Wanless [95] ( o La in squa es) o pa ial
La in ec angles.
I would also be in e es ing o explo e a quad angle-based en y in a ian . A quad angle o
a La in squa e L=(L[i,j])is a 4- uple (L[i,j],L[i,j],L[i,j],L[i,j]) o dis inc ows iand i,
and columns jand j.Then,Lis said o sa is y he quad angle c i e ion i no wo quad angles
ag ee a exac ly h ee coo dina es. I Lsa is ies he quad angle c i e ion, hen Lis iso opic o a
g oup able. Thus, compu ing a quad angle-based en y in a ian will also acili a e dis inguishing
g oup- able La in squa es om non-g oup- able La in squa es.No ice in his ega d ha he o me
end o ha e la ge au o opism g oups, al hough g oup ables do no always achie e he maximum
au o opism g oup sizes [21, P ob. 509]. Simila ly o he jus -men ioned quad angle c i e ion, he e
exis some o he me hods o dis inguishing g oup- able La in squa es om non-g oup- able La in
squa es (see Re e ence [27]) ha could also be implemen ed in o he desc ip ion o new en y
in a ian s. A pai o hese me hods a e:
•The Thomsen condi ion [91]: A La in squa e L=(L[i,j])is he Cayley able o an abelian
g oup i and only i , o all h ee owsi,j,kand h ee columns i,j,k, one has ha L[i,j]=
L[j,i], oge he wi h L[i,k]=L[k,i], implies ha L[j,k]=L[k,j].
•The ec angle ule [14]: Le L=(L[i,j])be a educed La in squa e ( ha is, he e exis s a ow
and a column esuch ha L[e,i]=L[i,e]=i, o all i). Mo eo e , o each ow i,le i∗be
such ha L[i,i∗]=e.Then,Lis he Caley able o a g oup i and only i L[L[i,j∗],L[j,k∗]] =
L[i,k∗], o all i,j,k.
In his a icle, we ha e aimed o compa e a ious algo i hms o compu a ion, so we ha e ex-
pe imen ed using wo basic en y in a ian s. The au ho s in end o s udy en y in a ian s, bo h
heo e ically and compu a ionally, in u u e wo k.
La ge au o opism g oups. In his wo k, we mainly expe imen using andomized PLRs, whe e
mos ha e a i ial au o opism g oup (excep when we ha e e y ew en ies). We en isage his
simula ing a use ’s a e age case, simila o how S ones [85] s udied pa ial La in ec angles. I is
possible ha a use ins ead wan s o pe o m he compu a ion o a se o pa ial La in ec angles
ha likely includes symme ies. O a use may be s udying PLRs wi h la ge (o e en ansi i e)
au o opism g oups. In his si ua ion, en y in a ian s a e less e ec i e, o possibly e en useless
(such as o ansi i e au o opism g oups).
I is unlikely we can sol e hese challenge cases e icien ly wi hou , say, p o ing G aph Isomo -
phism is in P. Indeed, S ones [85] showed ha any ini e g oup is he au o opism g oup o a pa ial
Compu ing Au o opism G oups o Pa ial La in Rec angles 1.12:35
La in squa e. In hese se ings, i may be bene icial o o load hese p oblema ic cases on o, e.g., a
g aphics p ocessing uni (GPU) o sepa a e compu a ion. To achie e his, we need a me hod o
ecognize such cases.
5.2 Fu u e Implemen a ion Ideas
In his a icle’s expe imen s, we obse e ha he MMM g aph and PLR g aph me hods o e eason-
able and s able pe o mance unde mos condi ions. Pe haps su p isingly, he PLR g aph me hod is
o dina ily as e han he s anda d MMM me hod. We a ibu e his o he PLR g aph being smalle
han he MMM g aph.
Howe e , he MMM me hod is much as e han he PLR g aph me hod when he La in squa es
ha e many au o opisms, which we a ibu e o he il e ing s age (needed in he PLR g aph me hod,
bu no he MMM me hod).
The PLR g aph me hod could be imp o ed by
(1) inding ma hema ical condi ions on when au omo phisms o non-edge-colo ed pa ial
La in ec angle g aphs a e au o opisms o he co esponding pa ial La in ec angle,
(2) de eloping so wa e o edge-colo ed g aph au omo phism,1o
(3) de eloping pu pose-buil so wa e ha adap s he indi idualiza ion/ e inemen app oach
o nau y and Bliss o he p oblem o compu ing au o opisms o pa ial La in ec angles.
In addi ion o elimina ing he con e sion o e head, his would allow us o di ec ly use he
inhe en na u e o au o opisms, a he han encode hese as a g aph.
Fu he mo e, le us ema k ha one o he aims o de eloping he expe imen s o his s udy was
o compa e he e iciency o he p oposed me hods wi h hose exis ing in he ecen li e a u e ha
make use o au o opism g oups o sol ing he p oblems o coun ing, enume a ing, and classi ying
PLRs [31,32,35,39,41]. Since all o hem make use o non-pa allel compu ing, his has also been
ou i s choice. Ne e heless, o ad ance ou long- e m aim o de eloping e icien so wa e o
compu ing au o opism g oups o PLRs, a much deepe heo e ical and compu a ional wo k has o
be done o deal wi h he pa allel p ocessing app oach o he p oblem. I is also es ablished as u -
he wo k. No ice in his ega d ha his pa allel compu ing is pa icula ly in e es ing o dealing
wi h he al eady-men ioned PLRs wi h la ge (o e en ansi i e) au o opism g oups, whe e en y
in a ian s do no aid subsequen compu a ion. I migh be possible o o load hese p oblema ic
cases on o, o example, a GPU o sepa a e compu a ion.
Finally, a much deepe s udy o bases and s ong gene a ing se s o au o opism g oups o pa ial
La in ec angles, which ha e been b ie ly desc ibed in Sec ion 5.1, is also es ablished as u he
wo k. In compu a ional g oup heo y, such a s udy cons i u es an e icien way o sea ching ele-
men s sa is ying ce ain gi en p ope ies wi hin he g oup unde conside a ion. Mo e speci ically,
bases and s ong gene a ing se s a e used o p une e icien ly sea ch ees ha ing he g oup as
oo and i s elemen s as lea es. In his ega d, i is in e es ing o del e in o he s udy abou how
known s ong gene a o s o he au o opism g oup o a gi en pa ial La in ec angle can be used
o p uning he sea ch space in ou back acking me hods o ge mo e e icien algo i hms.
5.3 Tes Sui es
Gene a ing sui able es sui es also seems o be a di icul ask. To iden i y he so wa e design
goals, we wan a es sui e ha
1Bliss [52], a ailable om h p://www. cs.hu . i/So wa e/bliss/, also does no inco po a e edge colo s.
1.12:36 R. J. S ones e al.
•is compa able o one a use may ealis ically be in e es ed in s udying,
• es s he e ec i eness o bo h en y in a ian s and he subsequen compu a ion,
•is no o e ly di icul o pe o m expe imen s on (gi en he ins abili y o some o he me h-
ods), and
•is pa ame e ized, so we can compa e how he me hods scale as he pa ame e s change.
Ins ead o mos ly e i ying a pa ial La in ec angle has a i ial au o opism g oup, a use may
ins ead be esea ching pa ial La in ec angles (o e en La in squa es) wi h en o ced symme ies,
in which case he subsequen compu a ion would be mo e signi ican . Designing an expe imen al
es sui e wi h en o ced symme ies whe e he pa ame e s can change is challenging, pa icula ly
when we wan o a y he numbe o en ies m.
ACKNOWLEDGMENTS
The au ho s wan o exp ess hei g a i ude o he anonymous e e ees o he comp ehensi e
eading o he a icle and hei pe inen commen s and sugges ions, which helped imp o e he
manusc ip . In pa icula , we a e e y g a e ul o he anonymous e iewe who no iced he ac
ha he p oblem o compu ing he se o gene a o s o he au o opism g oup o a pa ial La in
ec angle is in ac g aph-isomo phism comple e (GI-comple e) and who also sugges ed he use o
bases and s ong gene a ing se s o deal wi h such a p oblem.
The au ho s hank Zhuanhao Wu o assis ance coding.
REFERENCES
[1] Nogan Alon, Elda Fische , and Ma io Szegedy. 2001. Pa en -iden i ying codes. J. Comb. Theo y Se ies A 95, 2 (2001),
349–359.
[2] S ephan D. And es and Raúl M. Falcón. 2019. Colou ing games based on au o opisms o La in hype - ec angles.
Quaes . Ma h. 42 (2019), 953–975.
[3] Raphael A zy. 1954. A no e on he au omo phisms o special loops. Ri eon Lema . 8 (1954), 81. In Heb ew.
[4] Masood A yapoo and Ebadollah S. Mahmoodian. 2011. On uni o mly gene a ing La in squa es. Bull. Ins . Comb.
Appl. 62 (2011), 48–58.
[5] Pawan Au o a and Shashank K. Meh a. 2018. The QAP-poly ope and he g aph isomo phism p oblem. J. Comb.
Op im. 36, 3 (2018), 965–1006.
[6] László Babai. 2016. G aph isomo phism in quasipolynomial ime. In P oceedings o he 48 h ACM Symposium on
Theo y o Compu ing. ACM, New Yo k, 684–697.
[7] László Babai. 2018. G oup, g aphs, algo i hms: he g aph isomo phism p oblem. In P oceedings o he In e na ional
Cong ess o Ma hema icians. Wo ld Sci. Publ., Hackensack, NJ, 3319–3336.
[8] László Babai. 2019. Canonical o m o g aphs in quasipolynomial ime: P elimina y epo . In P oceedings o he
51s ACM Symposium on Theo y o Compu ing. ACM, New Yo k, 1237–1246.
[9] László Babai, William M. Kan o , and Eugene M. Luks. 1983. Compu a ional complexi y and he classi ica ion o
ini e simple g oups. In P oceedings o he 24 h IEEE Symposium on Founda ions o Compu e Science. IEEE, 162–171.
[10] Rosema y A. Bailey. 1982. La in squa es wi h highly ansi i e au omo phism g oups. J. Aus . Ma h. Soc. 33 (1982),
18–22.
[11] Simon R. Blackbu n. 2000. Pe ec hash amilies: P obabilis ic me hods and explici cons uc ions. J. Comb. Theo y
Se . A 92 (2000), 54–60.
[12] S. Boo h and Cha les J. Colbou n. 1979. P oblems Polynomially Equi alen o G aph Isomo phism. Technical Repo
CS-77-04, Compu e Science Depa men , Uni e si y o Wa e loo.
[13] Raj C. Bose. 1963. S ongly egula g aphs, pa ial geome ies and pa ially balanced designs. Paci . J. Ma h. 13 (1963),
389–419.
[14] Hein ich B and . 1927. Übe eine e allgemeine ung des g uppenbeg i es. Ma h. Ann. 96, 1 (1927), 360–366.
[15] Joshua B owning, Douglas S. S ones, and Ian M. Wanless. 2013. Bounds on he numbe o au o opisms and sub-
squa es o a La in squa e. Combina o ica 33 (2013), 11–22.
[16] Da yn B yan , Melinda Buchanan, and Ian M. Wanless. 2009. The spec um o quasig oups wi h cyclic au omo -
phisms and addi ional symme ies. Disc. Ma h. 304, 4 (2009), 821–833.
[17] G ego y Bu le and Clemen W. H. Lam. 1985. A gene al back ack algo i hm o he isomo phism p oblem o
combina o ial objec s. J. Symb. Compu . 1, 4 (1985), 363–381.
Compu ing Au o opism G oups o Pa ial La in Rec angles 1.12:37
[18] Pe e C. Came on. 2015. Asymme ic La in squa es, S eine iple sys ems, and edge-pa allelisms. (2015). Re ie ed
om a Xi :1507.02190 [ma h.CO].
[19] Pe e J. Came on. 1975. Minimal edge-colou ings o comple e g aphs. J. London Ma h. Soc. (2) 11, 3 (1975), 337–346.
[20] Pe e J. Came on. 1976. Pa allelisms o Comple e Designs. Camb idge Uni e si y P ess, Camb idge-New Yo k-
Melbou ne. 144 pages.
[21] Pe e J. Came on. 2011. Resea ch p oblems om he BCC22. Disc. Ma h. 311 (2011), 1074–1083.
[22] Nicholas J. Ca enagh and Douglas S. S ones. 2011. Nea -au omo phisms o La in squa es. J. Combi. Des. 19 (2011),
365–377.
[23] Ei an Danan, Raúl M. Falcón, Dani Ko la , T en G. Ma bach, and Rebecca J. S ones. 2020. Re ining in a ian s o
compu ing au o opism g oups o pa ial la in ec angles. Disc. Ma h. 343, 5 (2020), 111812, 21.
[24] Fa ih Demi kale, Aki a Kamibeppu, T en G. Ma bach, Ok ay Olmez, and Rebecca J. S ones. 2019. G aph La ini y.
(2019). In p epa a ion.
[25] S ephen DeSal o. 2016. Exac sampling algo i hms o La in squa es and sudoku ma ices ia p obabilis ic di ide-
and-conque . Algo i hmica 79, 3 (2016), 1–21.
[26] A hu A. D isko. 1997. Loops o o de pn+1 wi h ansi i e au omo phism g oups. Ad . Ma h. 128 (1997), 36–39.
[27] An hony B. E ans. 2018. When Is a La in Squa e Based on a G oup? Sp inge In e na ional Publishing, Cham, 41–63.
[28] Raúl M. Falcón. 2006. La in squa es associa ed o p incipal au o opisms o long cycles. Applica ion in c yp og aphy.
In P oceedings o T ansg essi e Compu ing 2006: A Con e ence in Hono o Jean Della Do a. TC2006, 213–230.
[29] Raúl M. Falcón. 2012. The comp essed shape o a pa ial La in ec angle. In P oceedings o he Spanish Mee ing on
Compu e Algeb a and Applica ions. 95–98.
[30] Raúl M. Falcón. 2012. Cycle s uc u es o au o opisms o he La in squa es o o de up o 11. A s Combin. 103 (2012),
239–256.
[31] Raúl M. Falcón. 2013. The se o au o opisms o pa ial La in squa es. Disc. Ma h. 313, 11 (2013), 1150–1161.
[32] Raúl M. Falcón. 2015. Enume a ion and classi ica ion o sel -o hogonal pa ial La in ec angles by using he poly-
nomial me hod. Eu . J. Comb. 48 (2015), 215–223.
[33] Raúl M. Falcón. 2020. Using a CAS/DGS o analyze compu a ionally he con igu a ion o plana ba linkage mecha-
nisms based on pa ial La in squa es. Ma h. Compu . Sci. 14 (2020), 375–389.
[34] Raúl M. Falcón and S ephan D. And es. 2019. Au o opism s abilized colou ing games on ook’s g aphs. Disc. Appl.
Ma h. 266 (2019), 200–212.
[35] Raúl M. Falcón, Ósca J. Falcón, and Juan Núñez. 2018. Coun ing and enume a ing pa ial La in ec angles by means
o compu e algeb a sys ems and CSP sol e s. Ma h. Me h. Appl. Sci. 41 (2018), 7236–7262.
[36] Raúl M. Falcón, Ósca J. Falcón, and Juan Núñez. 2018. A his o ical pe spec i e o he heo y o iso opisms. Symme y
10 (2018), 1–21.
[37] Raúl M. Falcón and Jo ge Ma ín-Mo ales. 2007. G öbne bases and he numbe o La in squa es ela ed o au o-
opisms o O de ≤7. J. Symb. Compu . 42, 11–12 (2007), 1142–1154.
[38] Raúl M. Falcón and Juan Núñez. 2007. Pa ial La in squa es ha ing a San illi’s au o opism in hei au o opism g oups.
J. Dyn. Sys . Geom. Theo . 5 (2007), 19–32.
[39] Raúl M. Falcón and Rebecca J. S ones. 2015. Classi ying pa ial La in ec angles. Elec on. No es Disc. Ma h. 49 (2015),
765–771.
[40] Raúl M. Falcón and Rebecca J. S ones. 2017. Pa ial La in ec angle g aphs and au opa a opism g oups o pa ial
La in ec angles wi h i ial au o opism g oups. Disc. Ma h. 340, 6 (2017), 1242–1260.
[41] Raúl M. Falcón and Rebecca J. S ones. 2020. Enume a ing pa ial La in ec angles. Elec on. J. Comb. 27, 2 (2020),
#P2.47.
[42] Wang Fang, Rebecca J. S ones, T en G. Ma bach, Gang Wang, and Xiaoguang Liu. 2019. Towa ds a La in-
squa e sea ch engine. In P oceedings o he IEEE In e na ional Con e ence on Pa allel Dis ibu ed P ocessing wi h
Applica ions, Big Da a Cloud Compu ing, Sus ainable Compu ing Communica ions, Social Compu ing Ne wo king
(ISPA/BDCloud/SocialCom/Sus ainCom’19). IEEE, 727–735.
[43] S anley Fio ini and Robin J. Wilson. 1976. Edge-colou ings o g aphs-Some applica ions. In P oceedings o he 5 h
B i ish Combina o ial Con e ence. 193–202.
[44] Timo hy Gowe s and Jason Long. 2016. The leng h o an s-inc easing sequence o - uples. Re ie ed om
a Xi :1609.08688 [ma h.CO].
[45] Ma in G ohe, Daniel Neuen, and Pascal Schwei ze . 2018. A as e isomo phism es o g aphs o small deg ee.
In P oceedings o he 59 h Annual IEEE Symposium on Founda ions o Compu e Science (FOCS’18). IEEE Compu e
Socie y, Los Alami os, CA, 89–100. DOI:h ps://doi.o g/10.1109/FOCS.2018.00018
[46] Ma in G ohe, Daniel Neuen, Pascal Schwei ze , and Daniel Wiebking. 2018. An imp o ed isomo phism es o
bounded- ee-wid h g aphs. In P oceedings o he 45 h In e na ional Colloquium on Au oma a, Languages, and P o-
g amming (LIPIcs), Vol. 107. Schloss Dags uhl. Leibniz-Zen . In o m., Wade n, 14.

1.12:38 R. J. S ones e al.
[47] Ram P. Gup a. 1978. On he ch oma ic index and he co e index o a mul ig aph. In P oceedings o he Theo y and
Applica ions o G aphs (Lec u e No es in Ma h.), Vol. 642. 204–215.
[48] A. J. W. Hil on. 1977. Embedding incomple e La in ec angles and ex ending he edge colou ings o g aphs. Nan a
Ma h. 10, 2 (1977), 201–206.
[49] Alexande Hulpke, Pe e i Kaski, and Pa ic R. J. Ös e gå d. 2011. The numbe o La in squa es o o de 11. Ma h.
Comp. 80 (2011), 1197–1219.
[50] Edwin C. Ih ig and Benjamin M. Ih ig. 2008. The ecogni ion o symme ic La in squa es. J. Comb. Des. 16, 4 (2008),
291–300.
[51] Ma k Jacobson and Pe e Ma hews. 1996. Gene a ing uni o mly dis ibu ed La in squa es. J. Comb. Des. 4, 6 (1996),
405–437.
[52] Tommi Jun ila and Pe e i Kaski. 2007. Enginee ing an e icien canonical labeling ool o la ge and spa se g aphs.
In P oceedings o he SIAM Wo kshop on Algo i hm Enginee ing and Expe imen s. SIAM, 135–149.
[53] Pe e i Kaski. 2005. Algo i hms o Classi ica ion o Combina o ial Objec s. Ph.D Thesis. Teknillinen Ko keakoulu,
Helsinki, Finland.
[54] Pe e i Kaski and Pa ic R. J. Ös e gå d. 2006. Classi ica ion Algo i hms o Codes and Designs (Algo i hms and Com-
pu a ion in Ma hema ics), Vol. 15. Sp inge -Ve lag, Be lin.
[55] A. D. Keedwell. 1994. C i ical se s and c i ical pa ial La in squa es. In P oceedings o he Combina o ics, G aph Theo y,
Algo i hms and Applica ions Con e ence. Wo ld Science Publishing, Ri e Edge, NJ, 111–123.
[56] B en Ke by and Jona han D. H. Smi h. 2010. Quasig oup au omo phisms and symme ic g oup cha ac e s. Commen .
Ma h. Uni . Ca ol. 51, 2 (2010), 279–286.
[57] B en Ke by and Jona han D. H. Smi h. 2010. Quasig oup au omo phisms and he No on-S ein complex. P oc. Ame .
Ma h. Soc. 138 (2010), 3079–3088.
[58] S e an Klus and Tuhin Sahai. 2018. A spec al assignmen app oach o he g aph isomo phism p oblem. In . In e ence
7, 4 (2018), 689–706.
[59] G. Koleso a, C. W. H. Lam, and L. Thiel. 1990. On he numbe o 8 ×8 La in squa es. J. Comb. Theo y Se . A 54, 1
(1990), 143–148.
[60] Daniel Ko la . 2012. Pa i y ypes, cycle s uc u es and au o opisms o La in squa es. Elec on. J. Comb. 19, 3 (2012).
[61] Daniel Ko la . 2014. Compu ing he au o opy g oup o a La in squa e by cycle s uc u e. Disc. Ma h. 331 (2014),
74–82.
[62] Je ey S. Leon. 1979. An algo i hm o compu ing he au omo phism g oup o a Hadama d ma ix. J. Comb. Theo y
Se . A 27, 3 (1979), 289–306.
[63] Je ey S. Leon. 1982. Compu ing au omo phism g oups o e o -co ec ing codes. IEEE T ans. In . Theo y 28, 3 (1982),
496–511.
[64] Je ey S. Leon. 1984. Compu ing au omo phism g oups o combina o ial objec s. In P oceedings o he Con e ence on
Compu a ional G oup Theo y. Academic P ess, London, 321–335.
[65] B endan D. McKay. 1978. Compu ing au omo phisms and canonical labellings o g aphs. In P oceedings o he In e -
na ional Con e ence on Combina o ial Ma hema ics (Lec u e No es in Ma h.), Vol. 686. Sp inge , Be lin, 223–232.
[66] B endan D. McKay. 1981. P ac ical g aph isomo phism. Cong . Nume . 30 (1981), 45–87.
[67] B endan D. McKay. 1998. Isomo ph- ee exhaus i e gene a ion. J. Algo . 26, 2 (1998), 306–324.
[68] B endan D. McKay, Alison Meyne , and Wendy My old. 2007. Small La in squa es, quasig oups, and loops. J.
Comb. Des. 15 (2007), 98–119.
[69] B endan D. McKay and Adol o Pipe no. 2014. P ac ical g aph isomo phism, II. J. Symb. Compu . 60 (2014), 94–112.
[70] B endan D. McKay and Ian M. Wanless. 1999. Mos La in squa es ha e many subsqua es. J. Comb. Theo y Se . A 86
(1999), 323–347.
[71] B endan D. McKay and Ian M. Wanless. 2005. On he numbe o La in squa es. Ann. Comb. 9 (2005), 335–344.
[72] B endan D. McKay, Ian M. Wanless, and Xiande Zhang. 2015. The o de o au omo phisms o quasig oups. J. Comb.
Des. 23 (2015), 275–288.
[73] Mahamendige J. L. Mendis and Ian M. Wanless. 2017. Au opa a opisms o quasig oups and la in squa es. J. Comb.
Des. 25 (2017), 51–74.
[74] Hui Meng, Yumin Zheng, and Yuge Zheng. 2008. The classi ica ion cons uc ion and he non-isomo phism coun ing
o symme ic La in squa e. Ad . S ud. Con emp. Ma h. (Kyungshang) 17, 2 (2008), 169–179.
[75] Ga y L. Mille . 1977. G aph isomo phism, gene al ema ks. In P oceedings o he 9 h ACM Symposium on Theo y o
Compu ing. ACM, New Yo k, 143–150.
[76] Ga y L. Mille . 1978. On he nlog nisomo phism echnique: A p elimina y epo . In P oceedings o he 10 h ACM
Symposium on Theo y o Compu ing. Sp inge , Be lin, 51–58.
[77] Elchanan Mossel and Jiaming Xu. 2019. Seeded g aph ma ching ia la ge neighbo hood s a is ics. In P oceedings o
he 13 h ACM-SIAM SDA. SIAM, 1005–1014.
Compu ing Au o opism G oups o Pa ial La in Rec angles 1.12:39
[78] Ronald C. Read and De ek G. Co neil. 1977. The g aph isomo phism disease. J. G aph Theo y 1, 4 (1977), 339–363.
[79] Pascal Schwei ze and Daniel Wiebking. 2019. A uni ying me hod o he design o algo i hms canonizing combina-
o ial objec s. In P oceedings o he 51s Annual ACM SIGACT Symposium on Theo y o Compu ing (STOC’19).ACM,
New Yo k, 1247–1258.
[80] Nicolas Send ie . 2000. Finding he pe mu a ion be ween equi alen linea codes: The suppo spli ing algo i hm.
IEEE T ans. In o m. Theo y 46, 4 (2000), 1193–1203.
[81] Ákos Se ess. 2003. Pe mu a ion G oup Algo i hms (Camb idge T ac s in Ma hema ics), Vol. 152. Camb idge Uni e si y
P ess, Camb idge, UK.
[82] Cha les C. Sims. 1970. Compu a ional me hods in he s udy o pe mu a ion g oups. In P oceedings o he Con e ence
on Compu a ional P oblems in Abs ac Algeb a. 169–183.
[83] Cha les C. Sims. 1971. De e mining he conjugacy classes o a pe mu a ion g oup. In Compu e s in Algeb a and
Numbe Theo y (P oceedings o he SIAM-AMS Symposium on Applied Ma hema ics, New Yo k, 1970),Vol.IV.Ame .
Ma h. Soc., P o idence, RI, 191–195.
[84] Douglas S. S ones. 2010. The many o mulae o he numbe o La in ec angles. Elec on. J. Comb. 17 (2010), A1.
[85] Douglas S. S ones. 2013. Symme ies o pa ial La in squa es. Eu . J. Comb. 34, 7 (2013), 1092–1107.
[86] Douglas S. S ones, Pe Voj ěcho ský, and Ian M. Wanless. 2012. Cycle s uc u e o au o opisms o quasig oups and
La in squa es. J. Comb. Des. 20 (2012), 227–263.
[87] Rebecca J. S ones. 2020. K-plex 2-E asu e codes and Blackbu n pa ial La in squa es. IEEE T ans. In . Theo y 66, 6
(2020), 3704–3713.
[88] Rebecca J. S ones, Raúl M. Falcón, Daniel Ko la , and T en G. Ma bach. 2020. Compu ing au o opism g oups o
pa ial La in ec angles: A pilo s udy. Compu . Ma h. Me hod. Ea ly iew (2020), e1094. DOI:h ps://doi.o g/10.1002/
cmm4.1094
[89] Rebecca J. S ones, Ming Su, Xiaoguang Liu, Gang Wang, and Sheng Lin. 2015. A La in squa e au o opism sec e
sha ing scheme. Des. Codes C yp og . 35 (2015), 1–16.
[90] The GAP G oup. 2018. GAP—G oups, Algo i hms, P og amming—A sys em o compu a ional disc e e algeb a. Re-
ie ed om h p://www.gap-sys em.o g/.
[91] Ge ha d Thomsen. 1929. Topologische agen de di e en ialgeome ie XII. schni punk ssä ze in ebenen geweben.
Abh. Ma h. Sem. Uni . Hambu g 7, 1 (1929), 99–106.
[92] S e lana Topalo a. 2003. Classi ica ion o Hadama d ma ices o o de 44 wi h au omo phisms o o de 7. Disc. Ma h.
260, 1–3 (2003), 275–283.
[93] Ian M. Wanless. 2002. A gene alisa ion o ans e sals o La in squa es. Elec on. J. Comb. 9, 1 (2002).
[94] Ian M. Wanless. 2004. A pa ial La in squa es p oblem posed by Blackbu n. Bull. Ins . Comb. Appl. 42 (2004), 76–80.
[95] Ian M. Wanless. 2005. A omic La in squa es based on cyclo omic o homo phisms. Elec on. J. Comb. 12 (2005).
[96] Ian M. Wanless and Edwin C. Ih ig. 2005. Symme ies ha La in squa es inhe i om 1- ac o iza ions. J. Comb. Des.
13 (2005), 157–172.
[97] B. Weis eile . 1976. On Cons uc ion and Iden i ica ion o G aphs. Sp inge -Ve lag, Be lin-New Yo k.
[98] Da id E. Woolb igh . 1978. An n×nla in squa e has a ans e sal wi h a leas n−√ndis inc symbols. J. Comb.
Theo y Se . A 24, 2 (1978), 235–237. DOI:h ps://doi.o g/10.1016/0097-3165(78)90009-2
[99] Meng Yan, Jiaqi Feng, T en G. Ma bach, Rebecca J. S ones, Gang Wang, and Xiaoguang Liu. 2019. Gecko: A esilien
dispe sal scheme o mul i-cloud s o age. IEEE Access 7 (2019), 77387–77397. DOI:h ps://doi.o g/10.1109/ACCESS.
2019.2920405
[100] Qi a Yan, Minquan Cheng, Xiaohu Tang, and Qingchun Chen. 2017. On he placemen deli e y a ay design o
cen alized coded caching scheme. IEEE T ans. In . Theo y 63, 9 (2017), 5821–5833.
[101] Liping Yi, Rebecca J. S ones, and Gang Wang. 2019. Two-e asu e codes om 3-plexes. In Ne wo k and Pa allel Com-
pu ing, Xiaoxin Tang, Quan Chen, P adip Bose, Weiming Zheng, and Jean-Luc Gaudio (Eds.). Sp inge In e na ional
Publishing, Cham, 264–276.