<p>A classic textbook example for communication complexity is when A and B both receive a subtree of a an <span class="math-container">$n$</span>-node tree (that they both know), and they need to output whether their subtrees are disjoint or not. The textbook solution usually gives an algorithm with <span class="math-container">$2\log_2 n$</span> bits of communication. In <a href="https://www.computer.org/csdl/proceedings/focs/1988/0877/00/021924.pdf" rel="nofollow noreferrer">Lovasz-Saks</a>, however, there is a better algorithm, with <span class="math-container">$\log_2 n+\log_2 \log_2 n$</span> bits of communication. Where is the truth between this and the trivial <span class="math-container">$\log_2 n$</span> lower bound?</p>

<p>A natural idea is to consider the rank of the communication matrix, but this is <span class="math-container">$2n-1$</span> for any tree; the vertices and edges generate every subtree.</p>

CC BY-SA 4.0
2018-09-11T12:12:38.027Z
Do you mean *non-deterministic* comm. complexity of subtree disjointness? In R.L. Graham, Handbook of Combinatorics, 1995; after describing the protocol ("A sends any node x of her tree to B; if y is the node in B's tree that is closest to x, B responds by sending y to A; then A checks if y in TA") they say: *"... this (non-deterministic) protocol uses $2 \log n$ bits. Lovasz and Saks (1993) showed that it can be modified to use only $\log n + \log \log n$ bits..."*. What is the trivial protocol for $\log_2 n$ LB?
Marzio De Biasi
CC BY-SA 4.0
2018-09-11T18:38:01.267Z
No, I mean deterministic; non-deterministic bounds are trivially $\log n$, as either you can output a common vertex, or a separating vertex. The LB follows by noticing that the communication matrix is triangular if the tree is a path which assuredly A holds the left, and B the right end-vertex of.
domotorp
CC BY-SA 4.0
2018-09-12T07:10:48.827Z
Thanks for the clarification (I misinterpreted it)! So, when you say "Where is the truth ...?" you mean "Has the known bounds $\log n \leq \kappa( C_T) \leq \log n + \log \log n$ been improved (or solved)?"
Marzio De Biasi
CC BY-SA 4.0
2018-09-12T07:45:33.077Z
Yes.$\;\;\!\!\!$
domotorp
<communication-complexity><tree>
What is the exact communication complexity of subtree disjointness?
domotorp
# What is the exact communication complexity of subtree disjointness?

(Asked by: username_0 on 2018-09-10)

A classic textbook example for communication complexity is when A and B both receive a subtree of a an $n$-node tree (that they both know), and they need to output whether their subtrees are disjoint or not. The textbook solution usually gives an algorithm with $2\log\_2 n$ bits of communication. In [Lovasz-Saks](https://www.computer.org/csdl/proceedings/focs/1988/0877/00/021924.pdf), however, there is a better algorithm, with $\log\_2 n+\log\_2 \log\_2 n$ bits of communication. Where is the truth between this and the trivial $\log\_2 n$ lower bound?

A natural idea is to consider the rank of the communication matrix, but this is $2n-1$ for any tree; the vertices and edges generate every subtree.

**Tags:** communication-complexity, tree

> **Comments:**
> **username_1**: Do you mean *non-deterministic* comm. complexity of subtree disjointness? In R.L. Graham, Handbook of Combinatorics, 1995; after describing the protocol ("A sends any node x of her tree to B; if y is the node in B's tree that is closest to x, B responds by sending y to A; then A checks if y in TA") they say: *"... this (non-deterministic) protocol uses $2 \log n$ bits. Lovasz and Saks (1993) showed that it can be modified to use only $\log n + \log \log n$ bits..."*. What is the trivial protocol for $\log_2 n$ LB?  
> **username_0**: No, I mean deterministic; non-deterministic bounds are trivially $\log n$, as either you can output a common vertex, or a separating vertex. The LB follows by noticing that the communication matrix is triangular if the tree is a path which assuredly A holds the left, and B the right end-vertex of.  
> **username_1**: Thanks for the clarification (I misinterpreted it)! So, when you say "Where is the truth ...?" you mean "Has the known bounds $\log n \leq \kappa( C_T) \leq \log n + \log \log n$ been improved (or solved)?"  
> **username_0**: Yes.$\;\;\!\!\!$  

---

## 0 answers

