Counting butterfly quartets in a single tree
Reusing the idea of precomputing certain sums enables us to calculate the number of butterfly quartets in a single tree T in time O(|V|). Since the number of butterfly quartets in a single tree is the number of butterfly quartets shared between the tree and itself, we will use shared(T, T) to denote the number of butterfly quartet in T. This notation also emphasizes that computing the number is essentially a comparison of the tree against itself. Given a node v in T we can express the number of quartets it claims in the following way:
∑ i  ( F i     2     )  ( ( F ¯  i     2     )  − ∑ j ≠ i   ( F j     2     )     )    ,       ( 13  )    MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaadaaeqbqaamaabmGabaqbaeqabiqaaaqaaiabdAeagnaaBaaaleaacqWGPbqAaeqaaaGcbaGaeGOmaidaaaGaayjkaiaawMcaamaabmGabaWaaeWaceaafaqabeGabaaabaGafmOrayKbaebadaWgaaWcbaGaemyAaKgabeaaaOqaaiabikdaYaaaaiaawIcacaGLPaaacqGHsisldaaeqbqaamaabmGabaqbaeqabiqaaaqaaiabdAeagnaaBaaaleaacqWGQbGAaeqaaaGcbaGaeGOmaidaaaGaayjkaiaawMcaaaWcbaGaemOAaOMaeyiyIKRaemyAaKgabeqdcqGHris5aaGccaGLOaGaayzkaaaaleaacqWGPbqAaeqaniabggHiLdGccqGGSaalcaWLjaGaaCzcamaabmGabaGaeGymaeJaeG4mamdacaGLOaGaayzkaaaaaa@4E95@
where the Fi's are the subtrees of v. Now let
S = ∑ j  ( F j     2     )    ,   MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqWGtbWucqGH9aqpdaaeqbqaamaabmGabaqbaeqabiqaaaqaaiabdAeagnaaBaaaleaacqWGQbGAaeqaaaGcbaGaeGOmaidaaaGaayjkaiaawMcaaaWcbaGaemOAaOgabeqdcqGHris5aOGaeiilaWcaaa@387D@
we can now express (13) as
∑ i  ( F i     2     )  ( ( F ¯  i     2     )  − S + ( F i     2     )   )    ⋅       ( 14  )    MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaadaaeqbqaamaabmGabaqbaeqabiqaaaqaaiabdAeagnaaBaaaleaacqWGPbqAaeqaaaGcbaGaeGOmaidaaaGaayjkaiaawMcaamaabmGabaWaaeWaceaafaqabeGabaaabaGafmOrayKbaebadaWgaaWcbaGaemyAaKgabeaaaOqaaiabikdaYaaaaiaawIcacaGLPaaacqGHsislcqWGtbWucqGHRaWkdaqadiqaauaabeqaceaaaeaacqWGgbGrdaWgaaWcbaGaemyAaKgabeaaaOqaaiabikdaYaaaaiaawIcacaGLPaaaaiaawIcacaGLPaaaaSqaaiabdMgaPbqab0GaeyyeIuoakiabgwSixlaaxMaacaWLjaWaaeWaceaacqaIXaqmcqaI0aanaiaawIcacaGLPaaaaaa@4B64@
S can be calculated in time O(idv)and using the precomputed S, (14) can be also calculated in time O(idv). Summing the results of (14) for all nodes in T gives the number of quartets in the tree, shared(T, T). The total time usage is
∑ v ∈ T   i d v    = O ( | V |  )  .   MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaadaaeqbqaaiabdMgaPjabdsgaKnaaBaaaleaacqWG2bGDaeqaaaqaaiabdAha2jabgIGiolabdsfaubqab0GaeyyeIuoakiabg2da9iabd+eapnaabmGabaGaeiiFaWNaemOvayLaeiiFaWhacaGLOaGaayzkaaGaeiOla4caaa@4016@