2
$\begingroup$

Given a tree-graph with one of the vertices designated as the root, what is the complexity of calculating the number of vertex-pairs $\lbrace u,v \rbrace$ of which $v$ is not nearer to the root than $u$ and $u$ is not a vertex of the path from the root to $v$?

It is of course possible to determine that number in $O(n^2)$ by checking each pair's Lowest Common Ancestor, but is there a way of more directly calculating that number?

Improve this question
$\endgroup$
2
  • $\begingroup$ So pairs at the same level get counted twice? $\endgroup$
    – Aaron Meyerowitz
    Commented May 7, 2021 at 7:44
  • $\begingroup$ @AaronMeyerowitz the intention is to count them only once $\endgroup$
    – Manfred Weis
    Commented May 7, 2021 at 15:46

2 Answers 2

Reset to default
2
$\begingroup$

It takes only addition to count the distinct pairs where one is the ancestor of another. Couldn’t you just subtract that from the total number of pairs?

Improve this answer
$\endgroup$
0
1
$\begingroup$

In the article Sums of powers of the degrees of a graph one finds for the sum of squared vertex degrees the formula

$\sum_2(G)\le e\left(\frac{e}{n-1}+n-2\right);\ e:=\mathrm{card}(E),\ n := \mathrm{card}(V)$

Now in a rooted tree the number of vertex pairs we are looking for can be determined via

$\sum\limits_{v\in V}\sum\limits_{\lbrace s_{vi},\,s_{vj}\rbrace \subseteq S_v}\left|s_{vi}\right|\cdot \left|s_{vj}\right|$ where $s_{vi}$ denotes the siblings of the $i$-th child of vertex $v$ and includes that child.

which amounts to

$\sum\limits_{v\in V}\binom{\mathrm{deg}(v)-1}{2}$

multiplications.

From $$\frac{\binom{\mathrm{deg}-1}{2}}{\mathrm{deg}^2}\ =\ \frac{(\mathrm{deg}-1)(\mathrm{deg}-1)}{2\cdot\mathrm{deg}^2}\approx \frac{1}{2}$$

it follows that the number of operations is bound from above by $$\frac{e\left(\frac{e}{n-1}+n-2\right)}{2}$$ in the case of trees we have $e=n-1$ and thus $\frac{(n-1)^2}{2}$ multiplications

Edit:
while I first thought that Aaron's suggestion to subtract the number of vertex pairs $(u,v)$, with $\mathrm{LCA}(u,v)\in\lbrace u, v\rbrace$ from the number $\frac{n(n-1)}{2}$ of all vertex pairs wouldn't improve the complexity of calculating the number of vertex pairs $(u,v)$ with $\mathrm{LCA}(u,v)\notin\lbrace u, v\rbrace$, it actually is the key to an algorithm requiring only $O(n)$ additions: maintain in e.g. a depth first tree traversal a vertices' number of edges on the path to the root and add that distance to the sum of $\mathrm{LCA}(u,v)\in\lbrace u, v\rbrace$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ +1 , but the set of siblings of a child of v (including that child) is the set of children of v. I assume you meant descendants. Also I guess $s_{vi} \ne s_{vj}$ and finally if a root v has children $b,c$ and that is the whole tree, then we should get a total of two , $(u,v)=(b,c)$ and $(u,v)=(c,b).$ Granted these are minor quibbles easily fixed. $\endgroup$
    – Aaron Meyerowitz
    Commented May 8, 2021 at 3:31
  • $\begingroup$ @AaronMeyerowitz I know that my wording is strange, but not discriminating between siblings and descendants was motivated by the lack of a term for "a child and its descendants", so my apologies to all native English speakers. The scond has been addressed in an edit of the question, but there is also the question as to whether there are oriented pairs things, there is however the ambiguous meaning of the round brackets that usually denote ordered elements of tuples. $\endgroup$
    – Manfred Weis
    Commented May 8, 2021 at 7:39
  • $\begingroup$ Here are a few ways to cut down on the multiplications (if I understand correctly). One could restrict the outer sum to $V',$ the subset of vertices having at least two children. If $|s_w|$ is the number of vertices of the subtree rooted at $w$ then it seems you could compute $\frac12\sum\limits_{v\in V'}\left((\sum |s_{vi}|)^2-\sum |s_{vi}|^2 \right)$ where $vi$ ranges over the children of $v.$ This is less than $2n$ multiplications. $\endgroup$
    – Aaron Meyerowitz
    Commented May 9, 2021 at 8:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .