Counting shared butterfly quartets
For each pair of internal nodes v, v' from T, T' we want to count the number of shared butterfly quartets claimed by both internal nodes, shared(v, v'). Assume that F1, ..., Fdv MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqWGgbGrdaWgaaWcbaGaemizaq2aaSbaaWqaaiabdAha2bqabaaaleqaaaaa@30EB@ are subtrees of v and G1, ..., Gdv′ MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqWGhbWrdaWgaaWcbaGaemizaq2aaSbaaWqaaiqbdAha2zaafaaabeaaaSqabaaaaa@30F9@ are subtrees of v'. We wish to count all quartets on the form ab|cd where a, b ∈ Fi ∩ Gj, c ∈ Fk ∩ Gl and d ∈ Fm ∩ Gn, i ≠ k ≠ m, j ≠ l ≠ n (see Fig. 7). Counting the possible combinations of a and b is expressed by the following double sum, which sums over all pairs of subtrees of v and v':
∑ i  ∑ j  ( | F i  ∩ G j  |    2     )        MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaadaaeqbqaamaaqafabaWaaeWaceaafaqabeGabaaabaGaeiiFaWNaemOray0aaSbaaSqaaiabdMgaPbqabaGccqGHPiYXcqWGhbWrdaWgaaWcbaGaemOAaOgabeaakiabcYha8bqaaiabikdaYaaaaiaawIcacaGLPaaaaSqaaiabdQgaQbqab0GaeyyeIuoaaSqaaiabdMgaPbqab0GaeyyeIuoaaaa@4022@
Given that a and b are in Fi ∩ Gj, we need to find c and d in F¯ MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacuWGgbGrgaqeaaaa@2DD9@i ∩ G¯ MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacuWGhbWrgaqeaaaa@2DDB@j. The number of possible choices of c and d is expressed by:
( | F ¯  i  ∩ G ¯  j  |    2     )    MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaadaqadiqaauaabeqaceaaaeaacqGG8baFcuWGgbGrgaqeamaaBaaaleaacqWGPbqAaeqaaOGaeyykICSafm4raCKbaebadaWgaaWcbaGaemOAaOgabeaakiabcYha8bqaaiabikdaYaaaaiaawIcacaGLPaaaaaa@3954@
However when finding c and d in F¯ MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacuWGgbGrgaqeaaaa@2DD9@i ∩ G¯ MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacuWGhbWrgaqeaaaa@2DDB@j, the condition that c and d must be in different subtrees is not satisfied. Therefore we subtract the number of times c and d are in the same subtree of v and v':
∑ k ≠ i   ( | F k  ∩ G ¯  j  |    2     )  + ∑ l ≠ j   ( | F ¯  i  ∩ G l  |    2     )      − ∑ k ≠ i   ∑ l ≠ j   ( | F k  ∩ G l  |    2     )        MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaadaaeqbqaamaabmGabaqbaeqabiqaaaqaaiabcYha8jabdAeagnaaBaaaleaacqWGRbWAaeqaaOGaeyykICSafm4raCKbaebadaWgaaWcbaGaemOAaOgabeaakiabcYha8bqaaiabikdaYaaaaiaawIcacaGLPaaacqGHRaWkdaaeqbqaamaabmGabaqbaeqabiqaaaqaaiabcYha8jqbdAeagzaaraWaaSbaaSqaaiabdMgaPbqabaGccqGHPiYXcqWGhbWrdaWgaaWcbaGaemiBaWgabeaakiabcYha8bqaaiabikdaYaaaaiaawIcacaGLPaaaaSqaaiabdYgaSjabgcMi5kabdQgaQbqab0GaeyyeIuoaaSqaaiabdUgaRjabgcMi5kabdMgaPbqab0GaeyyeIuoakiabgkHiTmaaqafabaWaaabuaeaadaqadiqaauaabeqaceaaaeaacqGG8baFcqWGgbGrdaWgaaWcbaGaem4AaSgabeaakiabgMIihlabdEeahnaaBaaaleaacqWGSbaBaeqaaOGaeiiFaWhabaGaeGOmaidaaaGaayjkaiaawMcaaaWcbaGaemiBaWMaeyiyIKRaemOAaOgabeqdcqGHris5aaWcbaGaem4AaSMaeyiyIKRaemyAaKgabeqdcqGHris5aaaa@6EC5@
Any pair in Fk ∩ Gl is counted twice, once in |Fk ∩ G¯ MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacuWGhbWrgaqeaaaa@2DDB@j| and once in |F¯ MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacuWGgbGrgaqeaaaa@2DD9@i ∩ Gl|, therefore these pairs are subtracted once using the double sum above. (2) expresses the number of ways c and d can be found in different subtrees, given that a and b are found in Fi ∩ Gj:
( | F ¯  i  ∩ G ¯  j  |    2     )  − ∑ k ≠ i   ( | F k  ∩ G ¯  j  |    2     )    − ∑ l ≠ j   ( | F ¯  i  ∩ G l  |    2     )    + ∑ k ≠ i   ∑ l ≠ j   ( | F k  ∩ G l  |    2     )            ( 2 )    MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaadaqadiqaauaabeqaceaaaeaacqGG8baFcuWGgbGrgaqeamaaBaaaleaacqWGPbqAaeqaaOGaeyykICSafm4raCKbaebadaWgaaWcbaGaemOAaOgabeaakiabcYha8bqaaiabikdaYaaaaiaawIcacaGLPaaacqGHsisldaaeqbqaamaabmGabaqbaeqabiqaaaqaaiabcYha8jabdAeagnaaBaaaleaacqWGRbWAaeqaaOGaeyykICSafm4raCKbaebadaWgaaWcbaGaemOAaOgabeaakiabcYha8bqaaiabikdaYaaaaiaawIcacaGLPaaaaSqaaiabdUgaRjabgcMi5kabdMgaPbqab0GaeyyeIuoakiabgkHiTmaaqafabaWaaeWaceaafaqabeGabaaabaGaeiiFaWNafmOrayKbaebadaWgaaWcbaGaemyAaKgabeaakiabgMIihlabdEeahnaaBaaaleaacqWGSbaBaeqaaOGaeiiFaWhabaGaeGOmaidaaaGaayjkaiaawMcaaaWcbaGaemiBaWMaeyiyIKRaemOAaOgabeqdcqGHris5aOGaey4kaSYaaabuaeaadaaeqbqaamaabmGabaqbaeqabiqaaaqaaiabcYha8jabdAeagnaaBaaaleaacqWGRbWAaeqaaOGaeyykICSaem4raC0aaSbaaSqaaiabdYgaSbqabaGccqGG8baFaeaacqaIYaGmaaaacaGLOaGaayzkaaaaleaacqWGSbaBcqGHGjsUcqWGQbGAaeqaniabggHiLdaaleaacqWGRbWAcqGHGjsUcqWGPbqAaeqaniabggHiLdGccaWLjaGaaCzcamaabmGabaGaeGOmaidacaGLOaGaayzkaaaaaa@802F@
We can now compute the number of shared butterfly quartets between two internal nodes, ie. the number of butterfly quartets claimed by both internal nodes with the same topology:
shared ( v , v ′   )  = ∑ i  ∑ j  ( | F i  ∩ G j  |    2     )      ( ( | F ¯  i  ∩ G ¯  j  |    2     )  − ∑ k ≠ i   ( | F k  ∩ G ¯  j  |    2     )         − ∑ l ≠ j   ( | F ¯  i  ∩ G l  |    2     )  + ∑ k ≠ i   ∑ l ≠ j   ( | F k  ∩ G l  |    2     )         )            ( 3 )    MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaafaqaceGabaaabaGaee4CamNaeeiAaGMaeeyyaeMaeeOCaiNaeeyzauMaeeizaq2aaeWaceaacqWG2bGDcqGGSaalcuWG2bGDgaqbaaGaayjkaiaawMcaaiabg2da9maaqafabaWaaabuaeaadaqadiqaauaabeqaceaaaeaacqGG8baFcqWGgbGrdaWgaaWcbaGaemyAaKgabeaakiabgMIihlabdEeahnaaBaaaleaacqWGQbGAaeqaaOGaeiiFaWhabaGaeGOmaidaaaGaayjkaiaawMcaaaWcbaGaemOAaOgabeqdcqGHris5aaWcbaGaemyAaKgabeqdcqGHris5aOWaaeqaceaadaqadiqaauaabeqaceaaaeaacqGG8baFcuWGgbGrgaqeamaaBaaaleaacqWGPbqAaeqaaOGaeyykICSafm4raCKbaebadaWgaaWcbaGaemOAaOgabeaakiabcYha8bqaaiabikdaYaaaaiaawIcacaGLPaaacqGHsisldaaeqbqaamaabmGabaqbaeqabiqaaaqaaiabcYha8jabdAeagnaaBaaaleaacqWGRbWAaeqaaOGaeyykICSafm4raCKbaebadaWgaaWcbaGaemOAaOgabeaakiabcYha8bqaaiabikdaYaaaaiaawIcacaGLPaaaaSqaaiabdUgaRjabgcMi5kabdMgaPbqab0GaeyyeIuoaaOGaayjkaaaabaWaaeGaceaacqGHsisldaaeqbqaamaabmGabaqbaeqabiqaaaqaaiabcYha8jqbdAeagzaaraWaaSbaaSqaaiabdMgaPbqabaGccqGHPiYXcqWGhbWrdaWgaaWcbaGaemiBaWgabeaakiabcYha8bqaaiabikdaYaaaaiaawIcacaGLPaaacqGHRaWkdaaeqbqaamaaqafabaWaaeWaceaafaqabeGabaaabaGaeiiFaWNaemOray0aaSbaaSqaaiabdUgaRbqabaGccqGHPiYXcqWGhbWrdaWgaaWcbaGaemiBaWgabeaakiabcYha8bqaaiabikdaYaaaaiaawIcacaGLPaaaaSqaaiabdYgaSjabgcMi5kabdQgaQbqab0GaeyyeIuoaaSqaaiabdUgaRjabgcMi5kabdMgaPbqab0GaeyyeIuoaaSqaaiabdYgaSjabgcMi5kabdQgaQbqab0GaeyyeIuoaaOGaayzkaaaaaiaaxMaacaWLjaWaaeWaceaacqaIZaWmaiaawIcacaGLPaaaaaa@A3C6@
If the trees, T and T', have a shared quartet ab|cd, then there are two internal nodes in each tree that claims this quartet: vab|c|d and vcd|a|b in T and v′ab|c|d MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacuWG2bGDgaqbamaaBaaaleaacqWGHbqycqWGIbGycqGG8baFcqWGJbWycqGG8baFcqWGKbazaeqaaaaa@3691@ and v′cd|a|b MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacuWG2bGDgaqbamaaBaaaleaacqWGJbWycqWGKbazcqGG8baFcqWGHbqycqGG8baFcqWGIbGyaeqaaaaa@3691@ in T'. Since both shared(vab|c|d, v′ab|c|d MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacuWG2bGDgaqbamaaBaaaleaacqWGHbqycqWGIbGycqGG8baFcqWGJbWycqGG8baFcqWGKbazaeqaaaaa@3691@) and shared(vcd|a|b, v′cd|a|b MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacuWG2bGDgaqbamaaBaaaleaacqWGJbWycqWGKbazcqGG8baFcqWGHbqycqGG8baFcqWGIbGyaeqaaaaa@3691@) will count the quartet, the total number of shared quartets between the two trees is:
shared ( T , T ′  ) = 1 2  ∑ v ∈ T   ∑ v ′  ∈ T ′    shared ( v , v ′  )       MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqqGZbWCcqqGObaAcqqGHbqycqqGYbGCcqqGLbqzcqqGKbazcqGGOaakcqWGubavcqGGSaalcuWGubavgaqbaiabcMcaPiabg2da9maalaaabaGaeGymaedabaGaeGOmaidaamaaqafabaWaaabuaeaacqqGZbWCcqqGObaAcqqGHbqycqqGYbGCcqqGLbqzcqqGKbazcqGGOaakcqWG2bGDcqGGSaalcuWG2bGDgaqbaiabcMcaPaWcbaGafmODayNbauaacqGHiiIZcuWGubavgaqbaaqab0GaeyyeIuoaaSqaaiabdAha2jabgIGiolabdsfaubqab0GaeyyeIuoaaaa@570E@
It is straightforward to observe that calculating shared(v, v') using a direct computation of (3) takes time O(dv2dv′2 MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqWGKbazdaqhaaWcbaGaemODayhabaGaeGOmaidaaOGaemizaq2aa0baaSqaaiqbdAha2zaafaaabaGaeGOmaidaaaaa@348C@). It is however not necessary for shared(v, v') to sum over all subtrees of v and v'. Since each term in the sums involves taking a 2-subset from a shared leaf set, we need only to consider subtrees that are not leaves. This reduces the running time to O(idv2idv′2 MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqWGPbqAcqWGKbazdaqhaaWcbaGaemODayhabaGaeGOmaidaaOGaemyAaKMaemizaq2aa0baaSqaaiqbdAha2zaafaaabaGaeGOmaidaaaaa@3742@). This running time can be improved even more, we start by expressing (2) in a different way:
( | F ¯  i  ∩ G ¯  j  |    2     )   ︸  I  − ∑ k ≠ i   ( | F k  ∩ G ¯  j  |    2     )     ︸  I I   − ∑ l ≠ j   ( | F ¯  i  ∩ G l  |    2     )     ︸  I I I   + ∑ k ≠ i   ∑ l ≠ j   ( | F k  ∩ G l  |    2     )       ︸  I V   =    ( | F ¯  i  ∩ G ¯  j  |    2     )   ︸  I  − ∑ k  ( | F k  ∩ G ¯  j  |    2     )  + ( | F i  ∩ G ¯  j  |    2     )     ︸  I I   − ∑ l  ( | F ¯  i  ∩ G l  |    2     )  + ( | F ¯  i  ∩ G j  |    2     )     ︸  I I I      + ∑ k  ∑ l  ( | F k  ∩ G l  |    2     )  −     ∑ k  ( | F k  ∩ G j  |    2     )  −   ∑ l  ( | F i  ∩ G l  |    2     )  + ( | F i  ∩ G j  |    2     )     ︸  I V             ( 4 )    MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaafaqabeWabaaabaWaaGbaaeaadaqadiqaauaabeqaceaaaeaacqGG8baFcuWGgbGrgaqeamaaBaaaleaacqWGPbqAaeqaaOGaeyykICSafm4raCKbaebadaWgaaWcbaGaemOAaOgabeaakiabcYha8bqaaiabikdaYaaaaiaawIcacaGLPaaaaSqaaiabdMeajbGccaGL44pacqGHsisldaagaaqaamaaqafabaWaaeWaceaafaqabeGabaaabaGaeiiFaWNaemOray0aaSbaaSqaaiabdUgaRbqabaGccqGHPiYXcuWGhbWrgaqeamaaBaaaleaacqWGQbGAaeqaaOGaeiiFaWhabaGaeGOmaidaaaGaayjkaiaawMcaaaWcbaGaem4AaSMaeyiyIKRaemyAaKgabeqdcqGHris5aaWcbaGaemysaKKaemysaKeakiaawIJ=aiabgkHiTmaayaaabaWaaabuaeaadaqadiqaauaabeqaceaaaeaacqGG8baFcuWGgbGrgaqeamaaBaaaleaacqWGPbqAaeqaaOGaeyykICSaem4raC0aaSbaaSqaaiabdYgaSbqabaGccqGG8baFaeaacqaIYaGmaaaacaGLOaGaayzkaaaaleaacqWGSbaBcqGHGjsUcqWGQbGAaeqaniabggHiLdaaleaacqWGjbqscqWGjbqscqWGjbqsaOGaayjo+dGaey4kaSYaaGbaaeaadaaeqbqaamaaqafabaWaaeWaceaafaqabeGabaaabaGaeiiFaWNaemOray0aaSbaaSqaaiabdUgaRbqabaGccqGHPiYXcqWGhbWrdaWgaaWcbaGaemiBaWgabeaakiabcYha8bqaaiabikdaYaaaaiaawIcacaGLPaaaaSqaaiabdYgaSjabgcMi5kabdQgaQbqab0GaeyyeIuoaaSqaaiabdUgaRjabgcMi5kabdMgaPbqab0GaeyyeIuoaaSqaaiabdMeajjabdAfawbGccaGL44pacqGH9aqpaeaadaagaaqaamaabmGabaqbaeqabiqaaaqaaiabcYha8jqbdAeagzaaraWaaSbaaSqaaiabdMgaPbqabaGccqGHPiYXcuWGhbWrgaqeamaaBaaaleaacqWGQbGAaeqaaOGaeiiFaWhabaGaeGOmaidaaaGaayjkaiaawMcaaaWcbaGaemysaKeakiaawIJ=aiabgkHiTmaayaaabaWaaabuaeaadaqadiqaauaabeqaceaaaeaacqGG8baFcqWGgbGrdaWgaaWcbaGaem4AaSgabeaakiabgMIihlqbdEeahzaaraWaaSbaaSqaaiabdQgaQbqabaGccqGG8baFaeaacqaIYaGmaaaacaGLOaGaayzkaaGaey4kaSYaaeWaceaafaqabeGabaaabaGaeiiFaWNaemOray0aaSbaaSqaaiabdMgaPbqabaGccqGHPiYXcuWGhbWrgaqeamaaBaaaleaacqWGQbGAaeqaaOGaeiiFaWhabaGaeGOmaidaaaGaayjkaiaawMcaaaWcbaGaem4AaSgabeqdcqGHris5aaWcbaGaemysaKKaemysaKeakiaawIJ=aiabgkHiTmaayaaabaWaaabuaeaadaqadiqaauaabeqaceaaaeaacqGG8baFcuWGgbGrgaqeamaaBaaaleaacqWGPbqAaeqaaOGaeyykICSaem4raC0aaSbaaSqaaiabdYgaSbqabaGccqGG8baFaeaacqaIYaGmaaaacaGLOaGaayzkaaGaey4kaSYaaeWaceaafaqabeGabaaabaGaeiiFaWNafmOrayKbaebadaWgaaWcbaGaemyAaKgabeaakiabgMIihlabdEeahnaaBaaaleaacqWGQbGAaeqaaOGaeiiFaWhabaGaeGOmaidaaaGaayjkaiaawMcaaaWcbaGaemiBaWgabeqdcqGHris5aaWcbaGaemysaKKaemysaKKaemysaKeakiaawIJ=aaqaaiabgUcaRmaayaaabaWaaabuaeaadaaeqbqaamaabmGabaqbaeqabiqaaaqaaiabcYha8jabdAeagnaaBaaaleaacqWGRbWAaeqaaOGaeyykICSaem4raC0aaSbaaSqaaiabdYgaSbqabaGccqGG8baFaeaacqaIYaGmaaaacaGLOaGaayzkaaGaeyOeI0caleaacqWGSbaBaeqaniabggHiLdaaleaacqWGRbWAaeqaniabggHiLdGcdaaeqbqaamaabmGabaqbaeqabiqaaaqaaiabcYha8jabdAeagnaaBaaaleaacqWGRbWAaeqaaOGaeyykICSaem4raC0aaSbaaSqaaiabdQgaQbqabaGccqGG8baFaeaacqaIYaGmaaaacaGLOaGaayzkaaGaeyOeI0caleaacqWGRbWAaeqaniabggHiLdGcdaaeqbqaamaabmGabaqbaeqabiqaaaqaaiabcYha8jabdAeagnaaBaaaleaacqWGPbqAaeqaaOGaeyykICSaem4raC0aaSbaaSqaaiabdYgaSbqabaGccqGG8baFaeaacqaIYaGmaaaacaGLOaGaayzkaaGaey4kaSYaaeWaceaafaqabeGabaaabaGaeiiFaWNaemOray0aaSbaaSqaaiabdMgaPbqabaGccqGHPiYXcqWGhbWrdaWgaaWcbaGaemOAaOgabeaakiabcYha8bqaaiabikdaYaaaaiaawIcacaGLPaaaaSqaaiabdYgaSbqab0GaeyyeIuoaaSqaaiabdMeajjabdAfawbGccaGL44paaaGaaCzcaiaaxMaadaqadiqaaiabisda0aGaayjkaiaawMcaaaaa@3050@
Let
S j  = ∑ k  ( | F k  ∩ G j  |    2     )       S ′  i  = ∑ l  ( | F i  ∩ G l  |    2     )       S ¯  j  = ∑ k  ( | F k  ∩ G ¯  j  |    2     )       S ¯  ′  i  = ∑ l  ( | F ¯  i  ∩ G l  |    2     )       S = ∑ k  ∑ l  ( | F k  ∩ G l  |    2     )                ( 5 )    MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaafaqadeqbbaaaaeaacqWGtbWudaWgaaWcbaGaemOAaOgabeaakiabg2da9maaqafabaWaaeWaceaafaqabeGabaaabaGaeiiFaWNaemOray0aaSbaaSqaaiabdUgaRbqabaGccqGHPiYXcqWGhbWrdaWgaaWcbaGaemOAaOgabeaakiabcYha8bqaaiabikdaYaaaaiaawIcacaGLPaaaaSqaaiabdUgaRbqab0GaeyyeIuoaaOqaaiqbdofatzaafaWaaSbaaSqaaiabdMgaPbqabaGccqGH9aqpdaaeqbqaamaabmGabaqbaeqabiqaaaqaaiabcYha8jabdAeagnaaBaaaleaacqWGPbqAaeqaaOGaeyykICSaem4raC0aaSbaaSqaaiabdYgaSbqabaGccqGG8baFaeaacqaIYaGmaaaacaGLOaGaayzkaaaaleaacqWGSbaBaeqaniabggHiLdaakeaacuWGtbWugaqeamaaBaaaleaacqWGQbGAaeqaaOGaeyypa0ZaaabuaeaadaqadiqaauaabeqaceaaaeaacqGG8baFcqWGgbGrdaWgaaWcbaGaem4AaSgabeaakiabgMIihlqbdEeahzaaraWaaSbaaSqaaiabdQgaQbqabaGccqGG8baFaeaacqaIYaGmaaaacaGLOaGaayzkaaaaleaacqWGRbWAaeqaniabggHiLdaakeaacuWGtbWugaqegaqbamaaBaaaleaacqWGPbqAaeqaaOGaeyypa0ZaaabuaeaadaqadiqaauaabeqaceaaaeaacqGG8baFcuWGgbGrgaqeamaaBaaaleaacqWGPbqAaeqaaOGaeyykICSaem4raC0aaSbaaSqaaiabdYgaSbqabaGccqGG8baFaeaacqaIYaGmaaaacaGLOaGaayzkaaaaleaacqWGSbaBaeqaniabggHiLdaakeaacqWGtbWucqGH9aqpdaaeqbqaamaaqafabaWaaeWaceaafaqabeGabaaabaGaeiiFaWNaemOray0aaSbaaSqaaiabdUgaRbqabaGccqGHPiYXcqWGhbWrdaWgaaWcbaGaemiBaWgabeaakiabcYha8bqaaiabikdaYaaaaiaawIcacaGLPaaaaSqaaiabdYgaSbqab0GaeyyeIuoaaSqaaiabdUgaRbqab0GaeyyeIuoaaaGccaWLjaGaaCzcamaabmGabaGaeGynaudacaGLOaGaayzkaaaaaa@9604@
We can ignore leaf subtrees, so we need to compute idv' different S¯ MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacuWGtbWugaqeaaaa@2DF3@j's and Sj's which can each be computed in O(idv) time. Symmetrically each of the idv S¯′i MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacuWGtbWugaqegaqbamaaBaaaleaacqWGPbqAaeqaaaaa@2F85@'s and S′i MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacuWGtbWugaqbamaaBaaaleaacqWGPbqAaeqaaaaa@2F6E@'s takes time O(id′v MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqWGPbqAcuWGKbazgaqbamaaBaaaleaacqWG2bGDaeqaaaaa@3105@) to compute, and the total time of computing S is O(idvidv'). The total time of computing all sums mentioned is thus O(idvidv') and this is the key to reducing the time usage of shared(v,v'). Using the sums we can express (4) as:
( | F ¯  i  ∩ G ¯  j  |    2     )   ︸  I  − S ¯  j  + ( | F i  ∩ G ¯  j  |    2     )   ︸  I I   − S ¯  ′  i  + ( | F ¯  i  ∩ G j  |    2     )   ︸  I I I   + S − S j  − S ′  i  + ( | F i  ∩ G j  |    2     )   ︸  I V     MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaadaagaaqaamaabmGabaqbaeqabiqaaaqaaiabcYha8jqbdAeagzaaraWaaSbaaSqaaiabdMgaPbqabaGccqGHPiYXcuWGhbWrgaqeamaaBaaaleaacqWGQbGAaeqaaOGaeiiFaWhabaGaeGOmaidaaaGaayjkaiaawMcaaaWcbaGaemysaKeakiaawIJ=aiabgkHiTmaayaaabaGafm4uamLbaebadaWgaaWcbaGaemOAaOgabeaakiabgUcaRmaabmGabaqbaeqabiqaaaqaaiabcYha8jabdAeagnaaBaaaleaacqWGPbqAaeqaaOGaeyykICSafm4raCKbaebadaWgaaWcbaGaemOAaOgabeaakiabcYha8bqaaiabikdaYaaaaiaawIcacaGLPaaaaSqaaiabdMeajjabdMeajbGccaGL44pacqGHsisldaagaaqaaiqbdofatzaaryaafaWaaSbaaSqaaiabdMgaPbqabaGccqGHRaWkdaqadiqaauaabeqaceaaaeaacqGG8baFcuWGgbGrgaqeamaaBaaaleaacqWGPbqAaeqaaOGaeyykICSaem4raC0aaSbaaSqaaiabdQgaQbqabaGccqGG8baFaeaacqaIYaGmaaaacaGLOaGaayzkaaaaleaacqWGjbqscqWGjbqscqWGjbqsaOGaayjo+dGaey4kaSYaaGbaaeaacqWGtbWucqGHsislcqWGtbWudaWgaaWcbaGaemOAaOgabeaakiabgkHiTiqbdofatzaafaWaaSbaaSqaaiabdMgaPbqabaGccqGHRaWkdaqadiqaauaabeqaceaaaeaacqGG8baFcqWGgbGrdaWgaaWcbaGaemyAaKgabeaakiabgMIihlabdEeahnaaBaaaleaacqWGQbGAaeqaaOGaeiiFaWhabaGaeGOmaidaaaGaayjkaiaawMcaaaWcbaGaemysaKKaemOvayfakiaawIJ=aaaa@8394@
Provided that the sums S¯ MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacuWGtbWugaqeaaaa@2DF3@j, S¯′i MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacuWGtbWugaqegaqbamaaBaaaleaacqWGPbqAaeqaaaaa@2F85@, Sj, S′i MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacuWGtbWugaqbamaaBaaaleaacqWGPbqAaeqaaaaa@2F6E@ and S have been calculated, (4) can be calculated in time O(l). Since calculation of the sums is independent on the calculation of shared(v, v'), these calculations can be done serially as shown in the algorithm below, thereby reducing the time usage of shared(T, T') to:
∑ v ∈ T   ∑ v ′  ∈ T ′    i d v  i d v ′     = ∑ v ∈ T   i d v    ∑ v ′  ∈ T ′    i d v ′     = 2 ( | V | − 1  )  ⋅ 2 ( | V ′  | − 1  )  = O ( | V | | V ′  |  )      MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaadaaeqbqaamaaqafabaGaemyAaKMaemizaq2aaSbaaSqaaiabdAha2bqabaGccqWGPbqAcqWGKbazdaWgaaWcbaGafmODayNbauaaaeqaaaqaaiqbdAha2zaafaGaeyicI4SafmivaqLbauaaaeqaniabggHiLdGccqGH9aqpdaaeqbqaaiabdMgaPjabdsgaKnaaBaaaleaacqWG2bGDaeqaaaqaaiabdAha2jabgIGiolabdsfaubqab0GaeyyeIuoakmaaqafabaGaemyAaKMaemizaq2aaSbaaSqaaiqbdAha2zaafaaabeaaaeaacuWG2bGDgaqbaiabgIGiolqbdsfauzaafaaabeqdcqGHris5aOGaeyypa0JaeGOmaiZaaeWaceaacqGG8baFcqWGwbGvcqGG8baFcqGHsislcqaIXaqmaiaawIcacaGLPaaacqGHflY1cqaIYaGmdaqadiqaaiabcYha8jqbdAfawzaafaGaeiiFaWNaeyOeI0IaeGymaedacaGLOaGaayzkaaGaeyypa0Jaem4ta80aaeWaceaacqGG8baFcqWGwbGvcqGG8baFcqGG8baFcuWGwbGvgaqbaiabcYha8bGaayjkaiaawMcaaaWcbaGaemODayNaeyicI4SaemivaqfabeqdcqGHris5aaaa@7911@
ALGORITHM – CALCULATING THE NUMBER OF SHARED BUTTERFLY QUARTETS BETWEEN T AND T'
Requires: T, T' two input trees with the same leaf set.
Ensures: Res = shared(T, T')
Res ← 0
for v internal node in T do
   for v' internal node in T' do
      Calculate sums S¯ MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacuWGtbWugaqeaaaa@2DF3@j, S¯′i MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacuWGtbWugaqegaqbamaaBaaaleaacqWGPbqAaeqaaaaa@2F85@, Sj, S′i MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacuWGtbWugaqbamaaBaaaleaacqWGPbqAaeqaaaaa@2F6E@ and S
      Res ← Res + shared(v, v')
   end for
end for
Res ← Res2 MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaadaWcaaqaaGqaciab=jfasjab=vgaLjab=nhaZbqaaiabikdaYaaaaaa@319C@