Two-Party Model

Deterministic Two-party Bounds

We claim that $\mathsf{TRAV}_2$ is at least as hard as two-player equality:

Claim. Recall that equality $\mathsf{EQ}$ has inputs $x,y \in \{0,1\}^n$, and $\mathsf{EQ}(x,y)=1$ iff $x=y$. Then $D(\mathsf{TRAV}_2)\geq D(\mathsf{EQ})$, and more generally $\mathsf{TRAV}_2$ is at least as hard as $\mathsf{EQ}$.

The high-level idea of the following proof is to construct an equality gadget that lets us embed $\mathsf{EQ}$ into $\mathsf{TRAV}_2$. That is, given $x$ and $y$ as inputs of $\mathsf{EQ}$, we can convert these into subgraphs $G_1$ and $G_2$, inputs of $\mathsf{TRAV}_2$. We convert this in such a way that $\mathsf{TRAV}_2(G_1, G_2)=1$ if and only if $\mathsf{EQ}(x,y)=1$. Then $\mathsf{TRAV}_2$ cannot use less communication than the optimal $\mathsf{EQ}$ protocol, else we get a contradiction.

Proof. Equality gadget. We construct a gadget that enforces equality at a single bit position at index $i$ of $x$ and $y$, for $i \in [n]$. The gadget is shown below and consists of two parallel branches:

• The top branch corresponds to the assignment $x_i=y_i=1$.
• The bottom branch corresponds to the assignment $x_i=y_i=0$.

Add $L_i$ and $R_i$ into $G_A$ and $G_B$. Then, add ownership of $x_i = 1$ to $G_A$ if $x_i = 1$ is true, else add $x_i = 0$. Do the same for Bob and $y_i$. Then a path from $L_i$ to $R_i$ exists if and only if Alice and Bob have vertices on the same branch, which holds exactly when $x_i = y_i$.

Embedding $\mathsf{EQ}$ into $\mathsf{TRAV}_2$. Construct a graph of $n$ equality gadgets in a chain. We do this by setting $R_l=L_{l+1}$ for $l \in [n-1]$. Construct subgraph $G_A$ as follows: include all vertices $L_i$ and $R_i$ for $i \in [n]$. Also, for every $i \in [n]$, give $G_A$ ownership of the vertex labeled $x_i=1$ if this is true, else $x_i=0$. Repeat for $G_B$ and $y$.

In the resulting graph, set $v = L_1$ as the start vertex $v$, and $w = R_n$ as the end vertex. Then there exists a path from $v$ to $w$ if and only if all gadgets are traversable, which occurs if and only if $x_i = y_i$ for all $i \in [n]$, and therefore if and only if $x = y$.

We conclude by noting that the resulting graph $G$ has $\Theta(n)$ vertices and $\Theta(n)$ edges. As $|x|=|y|=\Theta(n)$, this completes the reduction and $\mathsf{TRAV}_2$ is at least as hard as $\mathsf{EQ}$.

The trivial protocol where Alice sends all of $G_A$ to Bob has communication complexity $\Theta(n)$. Therefore, $D(\mathsf{TRAV}_2)=O(n)$. Together with the Equality Claim, this gives $D(\mathsf{TRAV}_2)=\Theta(n)$. Thus $\mathsf{TRAV}_2$ is deterministically maximally hard.

Randomized Two-Party Bounds

Above, we note that the problem is deterministically maximally hard. In many cases, allowing for some error may allow us to produce a randomized algorithm with lower communication complexity.

Consider the public coin randomness model. In this model, both parties have access to the same random bit-string in addition to the problem description and input. This random bit string can be as long as we want. We also allow our output to error, that is, be incorrect, some bounded constant percent of the time, and strictly less than half the time. It can be shown that using the public coin randomness model, equality, which is deterministically maximally hard, can be reduced to being $O(1)$. We can denote the randomized communication complexity of equality by $R(\mathsf{EQ})=O(1)$.

Unfortunately, for $\mathsf{TRAV}_2$ we find that such a bound is unattainable. To prove this, we introduce the disjointness problem $\mathsf{DISJ}$, which has public coin randomized communication complexity $R(\mathsf{DISJ})=\Theta(n)$. As we show, $\mathsf{DISJ}$ can be embedded into $\mathsf{TRAV}_2$.

Definition. Define the disjointness problem as follows: let $x,y \in \{0,1\}^n$ be $n$-bit strings representing subsets of $[n]$. Then, for all $i \in [n]$, if $x_i=1$, we say $i$ is in Alice’s subset $S_A \subseteq [n]$, and if $x_i=0$ it is not. Similarly for $y$ and Bob. Then $\mathsf{DISJ}(x,y):\{0,1\}^n \times \{0,1\}^n \to \{0,1\}$, where $\mathsf{DISJ}(x,y)=1$ if $S_A \cap S_B=\emptyset$, and $\mathsf{DISJ}(x,y)=0$ if $S_A \cap S_B\neq\emptyset$. It is well-known that $D(\mathsf{DISJ})=\Theta(n)$ and $R(\mathsf{DISJ})=\Theta(n)$.

Claim. We claim $R(\mathsf{TRAV}_2)\geq R(\mathsf{DISJ})$, and more generally $\mathsf{TRAV}_2$ is at least as hard as $\mathsf{DISJ}$.

Proof. Disjointness gadget. We construct a gadget that enforces disjointness at a single entry $i \in [n]$. There, let $x_i$ and $y_i$ be indicator functions that equal 1, respectively, when $i \in S_A$ and $i \in S_B$, else equal 0. Then:

• The top branch corresponds to when $i \in S_A$ but $i \notin S_B$.
• The middle branch corresponds to when $i \notin S_A$ and $i \notin S_B$.
• The bottom branch corresponds to when $i \in S_B$ but $i \notin S_A$.

Give $L_i$ and $R_i$ to both $G_A$ and $G_B$. Then give ownership of vertices labelled $x_i = 1$ to $G_A$ if this is true, else give all vertices labelled $x_i = 0$. Do the same with $y$ and $G_B$. Therefore, there is no path $L_i$ to $R_i$ if $i \in X \cap Y$, but there is a path in all other cases.

Embedding $\mathsf{DISJ}$ into $\mathsf{TRAV}_2$. We construct a graph $G$ by chaining $n$ copies of the disjointness gadget. More precisely, set $R_l=L_{l+1}$ for $l \in [n-1]$. Then, set $v=L_1$ as the start vertex and $w=R_n$ as the end vertex. Construct $G_A$ by giving ownership of all vertices $L_i$, $R_i$ and vertices labeled $x_i=1$ if it is true, else $x_i=0$, for $i \in [n]$. Do similarly for $G_B$.

In the resulting graph, there exists a path from $v$ to $w$ if and only if all disjointness gadgets are traversable, which occurs if and only if $X \cap Y = \emptyset$.

We conclude by noting that $|V(G)|=\Theta(n)$ and $|E(G)|=\Theta(n)$. As $|x|=|y|=\Theta(n)$, this completes the reduction and $\mathsf{TRAV}_2$ is at least as hard as $\mathsf{DISJ}$.

Recall that in the equality embedding, we showed that $D(\mathsf{TRAV}_2)=\Theta(n)$. With disjointness, we show that $R(\mathsf{TRAV}_2)=\Theta(n)$ too. This is because the disjointness embedding gives $R(\mathsf{TRAV}_2)=\Omega(n)$, since $R(\mathsf{DISJ})=\Theta(n)$. Then, the trivial protocol where Alice sends her entire $G_A$ to Bob in $\Theta(n)$ bits works even in the public coin randomness model. Together this gives $R(\mathsf{TRAV}_2)=\Theta(n)$. In other words, we cannot do much better even with bounded error.

Specialized Two-Party Bounds

The previous proofs show that $\mathsf{TRAV}_2$ is maximally complicated in terms of deterministic communication complexity and public randomized communication complexity. A natural follow-up question is whether we can do better. That is, given some additional constraints, can we solve the problem with reduced communication complexity?

Definition. Define the $\mathsf{CTRAV}_2$ problem as a $\mathsf{TRAV}_2$ problem where $G_A$ and $G_B$ are guaranteed to be connected subgraphs of $G$.

Claim. $\mathsf{CTRAV}_2$ is at least as hard as $\mathsf{DISJ}$. Thus, $D(\mathsf{CTRAV}_2)=\Theta(n)$ and $R(\mathsf{CTRAV}_2)=\Theta(n)$.

Proof. Let $x,y$ be inputs of Alice and Bob to the $\mathsf{DISJ}$ problem. We construct a graph $G$ as follows: give ownership of $v$ and all vertices labeled $a_i$ and $i$ if $x_i=1$, for $i \in [n]$. Similarly for $w$, $G_B$, and $y$. Then if there is a path from $v$ to $w$, this means there exists some $i \in [n]$ such that $x_i=y_i=1$. This means that $S_A \cap S_B \neq \emptyset$. On the other hand, if there is no path from $v$ to $w$, then for all $i \in [n]$, either $x_i=0$ or $y_i=0$.

We note that $|V(G_A)|=|V(G_B)|=|x|=|y|=\Theta(n)$. Furthermore, $G_A$ and $G_B$ are connected subgraphs of $G$. This completes the reduction.

Informally, this tells us that even when $G_A$ and $G_B$ are connected subgraphs, we do not immediately get better bounds and the problem does not become significantly easier. We now consider a sparser case:

Definition. Define $\mathsf{STRAV}_2$ as a $\mathsf{TRAV}_2$ problem where $E(G)=O(n)$, $E(G_A)=O(n)$, and $E(G_B)=O(n)$. In other words, the graph $G$ is sparse and $G_A$, $G_B$ are sparse too.

Claim. $\mathsf{STRAV}_2$ is at least as hard as $\mathsf{DISJ}$. Thus, $D(\mathsf{STRAV}_2)=\Theta(n)$ and $R(\mathsf{STRAV}_2)=\Theta(n)$.

Proof. We reuse the reduction from $\mathsf{DISJ}$ to $\mathsf{TRAV}_2$ in the disjointness embedding. In that construction, $G$ is a chain of $n$ disjointness gadgets, so $|E(G)|=\Theta(n)$. Moreover, each player’s subgraph consists of the gadget boundary vertices and one branch choice per gadget, which also gives $|E(G_A)|=\Theta(n)$ and $|E(G_B)|=\Theta(n)$.

Hence every instance produced by that reduction already satisfies the sparsity constraints in the definition of $\mathsf{STRAV}_2$. The reduction still preserves correctness: $\mathsf{DISJ}(x,y)=1$ iff there is a $v$ to $w$ path in $G_A \cup G_B$. Therefore $\mathsf{STRAV}_2$ is at least as hard as $\mathsf{DISJ}$.

Informally, this tells us that weak edge sparsity of $G$, $G_A$, and $G_B$ does not add nor remove significant communication cost. Combined with the connected-subgraph claim, this suggests that the local structure of $G$, $G_A$, and $G_B$, namely how sparse or connected the edges corresponding to the owned vertices are, does not have a significant impact on the deterministic and public randomized communication complexity of $\mathsf{TRAV}_2$.