Deterministic Even-Cycle Detection in Broadcast CONGEST

The CONGEST model [11] assumes $n\ge 1$ processing nodes connected by a network modeled as an arbitrary $n$-node graph $G=(V,E)$. (All graphs are supposed to be connected and simple, i.e., no multiple edges nor self-loops.) Each node $v$ in $G$ has an identifier $\mathrm{𝗂𝖽}(v)$ taken from a polynomial range of identifiers, and thus encoded on $O(\log n)$ bits. Each identifier is unique in the network. Computation proceeds as a sequence of synchronous rounds. All nodes start synchronously, at round 1. At each round, every node $v$ can (1) send an $O(\log n)$-bit message to each of its neighbors in $G$, i.e., to each node $u\in N(v)$, (2) receive the messages sent by its neighbors, and (3) perform some individual computation. No limit is placed on the amount of computation that each node performs at each round. Initially, every node $v$ knows its identifier $\mathrm{𝗂𝖽}(v)$ and the size $n$ of the graph it belongs to. No other information about the graph is provided to the nodes. All nodes perform the same algorithm, but the behavior of the nodes may vary along the course of execution of that algorithm, depending on the information acquired by them in each round (including their IDs).

The Broadcast CONGEST model is a restricted variant of the CONGEST model which requires each node to send the same $O(\log n)$ bit message to all its neighbors, at every round. (Of course, the messages sent by a same node $v$ at two different rounds may be different.)

The optimal (deterministic) algorithm for detecting 4-cycles in [4] can be artificially rewritten as Algorithm 1. Let us say that a node $v$ is light if its degree satisfies $\mathrm{deg}(v)\le \sqrt{2n}$, and is heavy otherwise.

Phase 1 in Algorithm 1 is aiming at finding light 4-cycles, i.e., 4-cycles containing only light nodes. The for-loop of Instruction 5 consumes at most $\sqrt{2n}$ rounds, as it involves light nodes only, i.e., the light node $v$ has at most $\sqrt{2n}$ neighbors, and thus at most $\sqrt{2n}$ light neighbors. If a light 4-cycle is detected at Instruction 8, then $v$ rejects appropriately.

Phase 2 is aiming at finding heavy 4-cycles, that is, 4-cycles containing at least one heavy node. The for-loop of Instruction 17 also consumes at most $\sqrt{2n}$ rounds, merely because it is performed only if $|\mathrm{𝗁𝖾𝖺𝗏𝗒}(v)|\le \sqrt{2n}$. The main observation is that it is legal for a node $v$ to reject if $|\mathrm{𝗁𝖾𝖺𝗏𝗒}(v)|>\sqrt{2n}$. This is due to the following simple fact.

For every $k\ge 2$, the detection of light $2k$-cycles, i.e. of $2k$-cycles containing only nodes of degree at most $n^{1/k}$, can be done in a straightforward manner in $O(n^{1-1/k})$ rounds. It is indeed sufficient to consider the subgraph $G_{light}$ of the input graph $G$ induced by the light nodes of $G$. The detection proceeds by looking for all $2k$-cycles $G_{light}$ passing through $v$, for all nodes $v\in V(G_{light})$ in parallel.

Specifically, the algorithm proceeds by flooding, during $k$ phases. At the first phase (which lasts one round), every $v\in V(G_{light})$ forms the path $P=(v)$ consisting of the single node $v$, and sends it to all its neighbors in $G_{light}$. At every phase $p\ge 2$, for every node $v\in V(G_{light})$, and for every simple path $P=(u_1,\mathrm{\dots },u_{p-1})$ received by $v$ during phase $p-1$, if $v\notin \{u_1,\mathrm{\dots },u_{p-1}\}$, then $v$ appends its identifier to $P$ for forming the path $P^{\prime }=(u_1,\mathrm{\dots },u_{p-1},v)$, which is forwarded to all of $v$’s neighbors in $G_{light}$.

After $k$ phases, if a node $v$ has received a simple path $P=(u_1,\mathrm{\dots },u_k)$ from a neighbor $u_k$, and a simple path $P^{\prime }=(u_1^{\prime },\mathrm{\dots },u_k^{\prime })$ from a neighbor $u_k^{\prime }$, with $u_1=u_1^{\prime }$, $P\cap P^{\prime }=\{u_1\}$, and $v\notin P\cup P^{\prime }$, then $v$ rejects. Otherwise $v$ accepts. We show that this simple flooding algorithm detects light $2k$-cycles in $O(n^{1-1/k})$ rounds.

Algorithm 2 solves the detection of $2k$-cycles. As Algorithm 1, it is split into two phases, one aiming at detecting light $2k$-cycles, and one aiming at detecting heavy $2k$-cycles, where a $2k$-cycle is light if it contains only nodes of degree smaller than $n^{1/k}$, and it is heavy otherwise. The second phase, that is, the detection of heavy cycles, uses the filtering techniques (see Instruction 29) based on Lemma 6, and detailed in Section 2.4.2. The detection of light cycles has already been described and analyzed in Section 2.3, and this section focuses on Phase 2, i.e., the detection of heavy cycles, starting at Instruction 18.

In Algorithm 2, every node $v$ of a graph $G=(V,E)$ maintains a collection of local variables. The set $\mathrm{𝗁𝖾𝖺𝗏𝗒}(v)$ contains all heavy neighbors of $v$ in $G$, thanks to Instruction 1. For every $w\in V$, the set $𝒬(w,v)$ contains a collection of simple paths with endpoints $v$ and $w$. At the beginning of $\mathrm{\ell }$-th iteration of the for-loop of Instruction 23, $𝒬(w,v)$ contains paths of length exactly $\mathrm{\ell }$, which are eventually updated at the end of the $\mathrm{\ell }$-th iteration (cf. Instruction 35) to paths of length $\mathrm{\ell }+1$. At each iteration, the set $W(v)$ is the set of nodes $w$ such that there is at least one path from $w$ to $v$ in $𝒬(w,v)$, i.e., $𝒬(w,v)$ is not empty.

The main point in Algorithm 2 is the test performed at Instruction 25, which stipulates that if $W(v)$ is too big, i.e., if $v$ is connected to too many (heavy) nodes $w$ by a path of length $\mathrm{\ell }$ at iteration $\mathrm{\ell }$, then $v$ rejects. If $v$ does not reject, then it carries on the flooding of path-prefixes, by applying filtering for preserving the fact that, for each $w\in W(v)$, $|𝒫(w,v)|\le \left(\genfrac{}{}{0pt}{}{2k}{\mathrm{\ell }+1}\right)$ at every iteration (cf. Fact 2). At the end of each iteration $\mathrm{\ell }$ of the for-loop of Instruction 23, node $v$ appends $\mathrm{𝗂𝖽}(v)$ to each path received during that iteration (see Instruction 35). That is, node $v$ appends $\mathrm{𝗂𝖽}(v)$ to each path $P\in 𝒫(w,u)$ not containing $v$, for all neighbors $u\in N(v)$, and it resets $𝒬(w,v)$ accordingly.

Finally, if node $v$ has received two paths $P$ and $P^{\prime }$ of length $k$, both in $𝒬(w,v)$ for some $w\in V$, i.e., both with endpoints $v$ and $w$, such that the concatenation of $P$ and $P^{\prime }$ forms a $2k$-cycle, then $v$ rejects.

In absence of the threshold condition at Instruction 25, Algorithm 2 merely consists of building longer and longer paths between $v$ and some nodes $w\in V$, such that if there exists $v$ and $w$ for which there exists two paths $P$ and $P^{\prime }$ of length $k$ between $v$ and $w$ that are internally disjoint, that is if $P\cup P^{\prime }$ form a $2k$-cycle, $v$ will detect that fact, and reject accordingly. As already discussed before, the filtering of Instruction 29 does not prevent the algorithm from finding such paths, if any. The main issue is that Algorithm 2 stops at iteration $\mathrm{\ell }$ whenever $|W(v)|>6\cdot {(2k)}^{\mathrm{\ell }}\cdot n^{1-1/k}$. Let us show that stopping under this condition is fine, as it implies the existence of a $2k$-cycle.

Let us assume that there exists a node $v$ such that, at iteration $\mathrm{\ell }\in \{1,\mathrm{\dots },k-1\}$ of the for-loop of Instruction 23, $|W(v)|>6\cdot {(2k)}^{\mathrm{\ell }}\cdot n^{1-1/k}$. At iteration $\mathrm{\ell }$, $W(v)$ is the set of heavy nodes $w$ such that there is a simple path of length exactly $\mathrm{\ell }$ starting at $w$ and ending at $v$. Using the notation of Theorem 2, let $R_{\mathrm{\ell }}(v)\subseteq V$ be the set of nodes that are reachable from $v$ by a simple path of length exactly $\mathrm{\ell }$. We have $W(v)\subseteq R_{\mathrm{\ell }}(v)$. It follows that

By Theorem 2, $G$ contains a $2k$-cycle, and thus node $v$ rejects rightfully.

It remains to show that the round complexity of Algorithm 2 is $O(n^{1-1/k})$. Phase 1, dedicated to the search of light $2k$-cycles, takes this many rounds, as established in Lemma 4. Let us show that Phase 2, dedicated to the search of heavy $2k$-cycles, has the same complexity. By Fact 3, for every node $v$ and every heavy node $w$, the final set $𝒬(w,v)$ at iteration $\mathrm{\ell }=k-1$ at Instruction 35 is built after at most $k\cdot 2^{2k}$ rounds. By the threshold condition of Instruction 25, the number of families $𝒫(w,v)$ to be transmitted by $v$ is at most $6\cdot {(2k)}^{\mathrm{\ell }}\cdot n^{1-1/k}$. So, in total, Phase 2 of Algorithm 2 performs in at most $k\cdot 2^{2k}\cdot 6\cdot {(2k)}^{\mathrm{\ell }}\cdot n^{1-1/k}$ rounds, that is $O(n^{1-1/k})$ rounds for a fixed $k$. This completes the proof of Theorem 1 (under the assumption that Theorem 2 holds). ∎

This section is dedicated to the proof of Theorem 2. Let $G=(V,E)$ be an $n$-node graph. Let $k\ge 2$, $\mathrm{\ell }\in \{1,\mathrm{\dots },k-1\}$, and $v\in V$. Let $R(v)$ be the set of nodes of $G$ that are reachable from $v$ by a simple path of length exactly $\mathrm{\ell }$, and let us assume that

Our goal is to show that there is a $2k$-cycle in $G$. In the following, we fix

Let $F$ be the set of edges incident to at least one node in $R(v)$. Let $F_{int}\subseteq F$ be the set of edges whose both endpoints are in $R(v)$, and let $F_{ext}=F\setminus F_{int}$.

Thanks to Lemma 7, there exists a bipartite subgraph of the graph $G[F_{int}]$ induced by $F_{int}$ with at least $|F_{int}|/2$ edges. Let $F_{int}^{\prime }\subseteq F_{int}$ be the set of edges of this bipartite graph, hence $|F_{int}^{\prime }|\ge |F_{int}|/2$.

Furthermore, $F_{ext}$ also induces a bipartite subgraph as all of its edges have exactly one end in $R(v)$.

Let $H$ be the bipartite graph defined as the subgraph of $G$ induced by $F_{int}^{\prime }$ if $|F_{int}^{\prime }|\ge |F_{ext}|$, or as the subgraph of $G$ induced by $F_{ext}$ otherwise. That is,

Let $(X,Y)$ be a partition of the vertices of $H$, such that

Note that some nodes in $Y$ may also belong to $R(v)$. $H$ satisfies the following.

For every $u\in V$, and every $i\in \{0,\mathrm{\dots },\mathrm{\ell }\}$, let us denote by ${𝒬}_i(u)$ the set of simple paths of length exactly $i$ with one endpoint equal to $u$, and the other endpoint equal to some node in $X$.

For every $u\in V$, and $i\in \{0,\mathrm{\dots },\mathrm{\ell }\}$, we define the two sets ${\mathrm{𝗂𝗇}}_i(u)$ and ${\mathrm{𝗈𝗎𝗍}}_i(u)$ as subsets of edges from $H$. Intuitively, the set ${\mathrm{𝗈𝗎𝗍}}_i(u)$ can be viewed as a set of edges that $u$ sends to its neighbors at round $i$ in a (virtual) distributed protocol that broadcasts sets of edges of $H$ throughout the network $G$, and ${\mathrm{𝗂𝗇}}_i(u)$ can be viewed as a set of edges that $u$ receives from its neighbors at round $i$ of this protocol. Let $E_H(u)$ denote the set of edges incident to $u$ in $H$. For every $u\in V$, let

That is, ${\mathrm{𝗈𝗎𝗍}}_0(u)$ can be viewed as the initialization of the aforementioned (virtual) broadcast protocol, i.e., initially, every node in $X$ sends its incident edges in $H$ to its neighbors in $G$. Now, let us define the sets ${\mathrm{𝗂𝗇}}_i(u)$ and ${\mathrm{𝗈𝗎𝗍}}_i(u)$ for every $u\in V$ and $i\ge 1$, where, again, ${\mathrm{𝗂𝗇}}_i(u)$ can be viewed as the set of edges received by $u$ at round $i$ (which were sent by $u$’s neighbors at round $i-1$), and ${\mathrm{𝗈𝗎𝗍}}_i(u)$ can be viewed as the set of edges forwarded by $u$ at round $i$. A key point is that $u$ does not forward all the received edges, but a carefully chosen subset of these edges.

Formally, for every $u\in V$ and every $i\in \{1,\mathrm{\dots },\mathrm{\ell }\}$, let

That is, ${\mathrm{𝗂𝗇}}_i(u)$ merges all edges from sets ${\mathrm{𝗈𝗎𝗍}}_{i-1}(w)$ for all neighbors $w$ of $u$ such that at least one path in ${𝒬}_{i-1}(w)$ can be extended into a path in ${𝒬}_i(u)$ (see Figure 1).

To define ${\mathrm{𝗈𝗎𝗍}}_i(u)$, we first define the sets ${\mathrm{𝗂𝗇}}_i(w,u)$ and ${\mathrm{𝗈𝗎𝗍}}_i(w,u)$, the subsets of edges respectively in ${\mathrm{𝗂𝗇}}_i(u)$ and ${\mathrm{𝗈𝗎𝗍}}_i(u)$ incident to node $w\in X\cup Y$ (see Figure 2). For every $i\in \{1,\mathrm{\dots },\mathrm{\ell }\}$, for every node $w$ of $H$, i.e., for every $w\in X\cup Y$, and every $u\in V$, let

For every vertex $u\in V$, and every $i\in \{1,\mathrm{\dots },\mathrm{\ell }\}$, we construct the edge-set ${\mathrm{𝗈𝗎𝗍}}_i(u)$ by defining, for each $y\in Y$, a subset ${\mathrm{𝗈𝗎𝗍}}_i(y,u)$ of ${\mathrm{𝗈𝗎𝗍}}_i(u)$ containing edges of ${\mathrm{𝗈𝗎𝗍}}_i(u)$ incident to $y$. First, for every $y\in Y$ and $u\in V$, we set

For every $u\in V$ and $i\in \{1,\mathrm{\dots },\mathrm{\ell }\}$, and for every $y\in Y$, we set

The definition of ${\mathrm{𝗈𝗎𝗍}}_i(y,u)$ when $|{\mathrm{𝗂𝗇}}_i(y,u)|\ge {(2k)}^i$ requires more care. Let $H_i^{(u)}$ be the subgraph of $H$ induced by all edges in ${\cup }_{y\in Y}{\mathrm{𝗂𝗇}}_i(y,u)$ where one keeps only the large sets ${\mathrm{𝗂𝗇}}_i(y,u)$, that is,

Note that, by construction, every edge $e\in {\mathrm{𝗂𝗇}}_i(u)={\cup }_{y\in Y}{\mathrm{𝗂𝗇}}_i(y,u)$ is either in $H_i^{(u)}$, or in the set ${\mathrm{𝗈𝗎𝗍}}_i(y,u)$ where $y\in Y$ is incident to $e$.

We are now going to update $H_i^{(u)}$ iteratively, by repeating the following sequence of “peeling” operations as long as they can be applied, i.e., as long as vertices can be removed. This sequence of operations bears similarities with the computation of the $k$-core of a graph, but the vertices of the partitions $X$ and $Y$ of $H$ are here treated separately.

For any triple $i\ge 1$, $u\in V$, and $y\in Y$ satisfying $|{\mathrm{𝗂𝗇}}_i(y,u)|\ge {(2k)}^i$, if the value of ${\mathrm{𝗈𝗎𝗍}}_i(y,u)$ has not been set in the above process, then it is set to ${\mathrm{𝗈𝗎𝗍}}_i(y,u)=\mathrm{\varnothing }$. That is, for every $y\in Y$,

Finally, we set

Note that, for every $i\ge 1$, $u\in V$, and $y\in Y$, we have

This equality is extended to define, for every triple $i\ge 1$, $u\in V$, and $x\in X$,

The graph resulting from the above iterated process of edge- and vertex-removal from $H_i^{(u)}$ is denoted by ${\mathrm{𝖢𝗈𝗋𝖾}}_i(u)$. The core graphs play an important role in our proof. Indeed, we will show (see Lemma 9) that if ${\mathrm{𝖢𝗈𝗋𝖾}}_i(u)$ is non-empty for some $i\ge 1$ and $u\in V$, then $G$ contains a $2k$-cycle. The density theorem will then follow from the fact (established in Lemma 10) that there exists $i$ and $u$ such that ${\mathrm{𝖢𝗈𝗋𝖾}}_i(u)$ is non-empty.

Before proving Lemmas 9 and 10, let us establish a collection of statements for helping understanding the construction above. The fact below illustrates why one can view the sets ${\mathrm{𝗈𝗎𝗍}}_i(u)$ and ${\mathrm{𝗂𝗇}}_i(u)$ as produced by a (virtual) protocol broadcasting edges of $H$ throughout the network $G$.