Testing $C_k$-Freeness in Bounded Admissibility Graphs

Finding a $k$-cycle ($C_k$) as a subgraph is a fundamental problem in graph theory with applications in network analysis, bioinformatics, and theoretical computer science. Given a graph $G=(V,E)$, the goal is to detect cycles of exactly $k$ vertices. Various algorithmic approaches have been proposed, including combinatorial search techniques [9], matrix-based methods using spectral graph theory [2], and more recent advancements leveraging graph sparsification and algebraic techniques [12, 5].

In this paper, the focus is on a variation of this problem, where access to the input algorithm is through an oracle that answers queries of the sort: “What is the degree of vertex $v$?”, “What is the $i$-th neighbour of the vertex $v$?”, and “are the vertices $u$ and $v$ neighbours?”. The goal in this variation is to determine whether a graph is $C_k$-free (it does not have a subgraph isomorphic to $C_k$), given the size of the input graph and oracle access to the graph, using the minimal possible number of queries.

A deterministic algorithm of this type, for determining whether a graph is $C_k$-free, may require a number of queries that is at least linear in the size of the graph. Therefore, to reduce the number of queries, an alternative approach is to require the algorithm only to distinguish between graphs that are $C_k$-free and those that are far from being $C_k$-free, which means that they require the removal of many edges to become $C_k$-free. The algorithm is also allowed to be probabilistic and is only required to produce the correct answer with high probability. Observe that if the algorithm is required to be error-free when the input graph is $C_k$-free (as is the case with the algorithm presented here), it must explicitly identify a $C_k$ subgraph to conclude that the graph is not $C_k$-free, essentially solving the $C_k$ detection problem for inputs that are far from being $C_k$-free.

This relaxation of requirements is captured by the framework of property testing. In this framework, the problem described above is referred to as testing $C_k$-freeness. A central goal is to show that the number of queries required for testing $C_k$-freeness, when the input is restricted to graphs from a specific family, is independent of the size of the input graph, yet may depend on the parameters of the class and the distance parameter (which is a fixed parameter provided with the input) that governs the ‘farness‘ of the input from $C_k$-freeness. If such an algorithm exists for some family of graphs, then we say that $C_k$-freeness is testable for this family.

The results in this work focus on testing $C_k$-freeness for sparse graph families, specifically those with a bounded average degree. This line of research was initiated in the seminal work of Goldriech and Ron [8] who showed that the query complexity of testing $C_k$-freeness in graphs with maximum degree $d$ is $O(d^k)$. Although that result was promising, Alon et al. [1] later showed that the query complexity testing triangle-freeness ($C_3$-freeness) in graphs with constant average degree is $\mathrm{\Theta }(\sqrt{n})$, where $n$ is the number of vertices in the input graph.

This raised the question of whether $C_k$-freeness has a better query complexity in families of graphs that are strict subsets of graphs with a bounded average degree. Czumaj et al. [4] showed that the more general property of $H$-freeness (i.e. graphs that don’t have a subgraph isomorphic to $H$) is testable in planar graphs, which implies that $C_k$-freeness is also testable in this setting. Subsequently, Levi [10] showed that the special case of triangle-freeness is testable for graphs with bounded arboricity, a superset of planar graphs. However, Eden et al. [7] recently showed that this does not extend to larger cycles: testing $C_4$-freeness and $C_5$-freeness has query complexity $\mathrm{\Omega }(n^{1/4})$ in graphs of bounded arboricity, and testing $C_k$-freeness for $k\ge 6$ has query complexity $\mathrm{\Omega }(n^{1/3})$. This left open the question of which (strict) subsets of classes with bounded arboricity still allow testing of $C_k$-freeness.

Awofeso et al. [3] recently presented results in this direction. They considered a hierarchy of sparse graph classes defined by the $r$-admissibility measure, which was first introduced by Dvořák [6] and plays an important role in the study of sparse classes [11, 14]. We postpone the rather technical definition to the next section; for now let us note that graphs of bounded $1$-admissibility are equivalent to graphs of bounded arboricity, and graphs whose $r$-admissibility is bounded for any integer $r$ include many well-known sparse classes such as planar graphs, graphs with bounded genus, graphs of bounded degree and graphs excluding a (topological) minor. Consequently, if we define ${𝒜}_r$ as the family of all graph classes whose $r$-admissibility is bounded by some constant, then we have an infinite hierarchy of classes ${𝒜}_1\supset {𝒜}_2\supset \mathrm{\dots }\supset {𝒜}_{\mathrm{\infty }}$ between graphs of bounded arboricity (${𝒜}_1$) and classes whose $r$-admissibility is bounded for any value of $r$ (${𝒜}_{\mathrm{\infty }}$, also known as bounded expansion classes [11]). Note that all these inclusions are proper, for example, the class ${𝒦}^{(r)}$ consisting of all cliques with every edge is replaced with a length $r$ path, is contained in ${𝒜}_r$ but not in ${𝒜}_{r+1}$.

In this hierarchy, Awofeso et al. [3] showed that testing $C_4$- and $C_5$-freeness is possible in ${𝒜}_2$, the graphs with bounded $2$-admissibility. They supplement this with a lower bound, which shows that for all $r\ge 4$ the number of queries required for $C_{2r+1}$-freeness testing and $C_{2r}$-freeness testing of classes in ${𝒜}_{r-1}$ is polynomial in the size of the input graph. The two results lead them to conjecture that $C_{2r}$- and $C_{2r+1}$-freeness should be testable for classes in ${𝒜}_r$, i.e. classes with bounded $r$-admissibility.

In this work, we complete the picture and prove the following.

We prove the theorem for $C_{2r+1}$-freeness, but a minor (and slightly simpler) version of our proof implies the same result $C_{2r}$-freeness. We also provide the lower bounds that do not appear in [3]. Specifically, that for every $r\ge 2$, $C_{2r}$-freeness and $C_{2r+1}$-freeness are not testable in bounded $(r-1)$-admissible graphs.

We use $\mathbb{N}$ for the set of integer numbers, $ℝ$ for the set of real numbers, ${ℝ}^{+}$ for the set of positive reals. For an integer $k$, we use $[k]$ as a shorthand for the set $\{1,2,\mathrm{\dots },k\}$. For integers $k_1$ and $k_2$ such that we use $[k_1,k_2]$ as a shorthand for the set $\{k_1,k_1+1\mathrm{\dots },k\}$ and $(k_1,k_2]$ as a shorthand for the set $\{k_1+1,k_1+2,\mathrm{\dots },k\}$. For a graph $G$, we use $V(G)$ and $E(G)$ to refer to its vertex and edge set, respectively. All graphs considered in this work are simple undirected graphs. The degree of a vertex $v\in V(G)$, denoted ${\mathrm{deg}}_G(v)$, is the number of edges incident on $v$. $N(v)$ is the set of neighbours of the vertex $v$. The distance between two vertices $u,v\in V(G)$ is denoted ${\text{dist}}_G(u,v)$. The distance between a vertex $u\in V(G)$ and a subset $V^{\prime }\subseteq V(G)$, is the minimum of ${\text{dist}}_G(u,v)$ over every $v\in V^{\prime }$.

For sequences of vertices $x_1{x}_2\mathrm{\dots }{x}_{\mathrm{\ell }}$ (and in particular, paths), we use the shorthand $x_{1}P{x}_{\mathrm{\ell }}$ to represent the sequence, and use $\text{length}(x_{1}P{x}_{\mathrm{\ell }})$ to denote the length of the corresponding path. In addition, we use $P{x}_{\mathrm{\ell }}$ (or $x_{1}P$) to refer to a subsequence of $x_{1}P{x}_{\mathrm{\ell }}$. All paths considered in this work are simple paths. Though paths here are undirected, we often treat them as directed by specifying a start and end vertex.

We start this section by presenting the definitions required for defining when a graph is $(p,r)$-admissible. Afterwards, we provide the actual definition and a structural lemma for $(p,r)$-admissible graphs. Then, we explain why this lemma is critical and provide an extra definition and two more structural claims.

An ordered graph is a pair $𝔾=(G,\le )$ where $G$ is a graph and $\le$ is a total order relation on $V(G)$. We write ${\le }_{𝔾}$ to denote the ordering of $𝔾$ and extend this notation to derive the relations , ${>}_{𝔾}$, ${\ge }_{𝔾}$.

To define $r$-admissibility we need the following ideas and notations.

Examples of $2$- and $3$-admissible path packings are depicted in Figure 1.

If $𝔾$ is an ordering of $G$ such that ${\mathrm{adm}}_r(𝔾)={\mathrm{adm}}_r(G)$, then we call $𝔾$ an admissibility ordering of $G$. The $1$-admissibility of a graph coincides with its degeneracy, and therefore such orderings are easily computable in linear time. For $r\ge 2$, an optimal ordering can also be computed in linear time in $n$ if the class has bounded expansion, i.e. if the graph class has bounded admissibility for every $r$ (see [6]).

Now we are ready to define the set of graphs we consider for testing $C_{2r+1}$-freeness.

We state the following fact regarding $(p,r)$-admissible graphs.

The next lemma is a well-known structural result for admissible graphs. This lemma is the critical component of the result of this paper.

We refer the reader to [3] (Proposition 3) for a proof.

Lemma 8, is the structural property of bounded admissibility graphs that enables the result in this paper. To understand the importance of the above lemma, fix $ϵ>0$ and suppose that we have a $(2,2)$ admissible graph $G$ with ordering $𝔾=(G,\le )$. Suppose also that $G$ is $ϵ$-far from being $C_4$-free and all the $C_4$-subgraphs in it have exactly two vertices of degree $2$ and $2$ vertices of degree $16n^{1/2}/ϵ$. Let $Q$ be the set of degree $16n^{1/2}/ϵ$ vertices and let $W$ be the set of degree $2$ vertices. Consider any ordering $\le$ placing the vertices in $Q$ before the vertices in $W$. For an example of such a graph see Section 7. Note that that graph is not $(2,2)$-admissible, however, a $(2,2)$-admissible graph with such attribute exists. Suppose that we create a new graph $\widehat{G}$ from $G$ by doing the following: (i) for every $u\in Q$ and $v\in N(u)$ we remove $uv$ if $u{\ge }_{𝔾}v$, and (ii) for every $u\in Q$ and $v$, such that $u{\ge }_{𝔾}v$, if there exists a maximum set of less than $n^{1/2}/(16ϵ)$ edge disjoint paths $uwv$ in $\widehat{G}$, then we remove all the edges in these paths from $\widehat{G}$.

It is easy to see that in (i) at most two edges are removed for every vertex in $Q$. So, after the removal of all these edges $\widehat{G}$ is still far from $C_4$-freeness. Regarding (ii) it can be shown, using Lemma 8, that after (i), for every $u\in Q$ there are at most $4$ vertices in $v\in V(G)$ such that $u{\ge }_{𝔾}v$ and $u$ and $v$ are connected by a path of length $2$. This, along with some accounting, implies that after (ii), far fewer than $ϵ|E(G)|$ edges were removed from $G$ to obtain $\widehat{G}$. Thus, $\widehat{G}$ is $ϵ/2$-far from being $C_4$-free.

Now, since $\widehat{G}$ is $ϵ/2$-far from being $C_4$-free, because of the type of $C_4$s it has, a constant portion of the vertices of $W$ are in such $C_4$. So, an algorithm that randomly selects a few vertices from the graph, with high probability, will pick one of these vertices. Suppose that this was the algorithm described in the introduction. Once a vertex from $W$ in a $C_4$-subgraph of $\widehat{G}$ is selected, its neighbours $x,y\in Q$ are discovered. Now, since in $\widehat{G}$, $x$ and $y$ are connected by a path of length $2$, $x$ and $y$ have many common vertices (at least $n^{1/2}/(16ϵ)$) and hence the algorithm will discover one of them with high probability. This will lead to the discovery of a $C_4$-subgraph in $G$.

This technique cannot be generalized beyond $k=7$, since for $k>7$ the $C_k$-subgraphs may include more complicated subpaths. To deal with this issue, we need the following definition.

We use a tilde on an upper case letter to denote a braid, for example $\tilde{B}$. In addition, we use the following notations for paths $L$ and braids $\tilde{B}$:

• $\mathrm{■}$

  $|\tilde{B}|$ is the number of paths in $\tilde{B}$.

• $\mathrm{■}$

  $\text{length}(\tilde{B})$ is the length of the paths in $\tilde{B}$.

• $\mathrm{■}$

  $\text{ends}(\tilde{B})$, is an order pair $(v,u)$ where $v$ is the start vertex of every path in $\tilde{B}$, and $u$ is the end vertices of every path in $\tilde{B}$ and otherwise it is undefined.

In this section, we present the procedure that we refer to as trimming. It is important to note that the trimming procedure is used only for the analysis of the algorithm we present. This is the reason that trimming can read the entire input graph.

Trimming receives as input a graph $G$ that is $(p,r)$-admissible, an ordering $𝔾$ and the parameters $p,r\in \mathbb{N}$ and $\gamma ,\delta \in {ℝ}^{+}$. From now on, in this section, assume that these parameters are fixed. Trimming creates a subgraph $\widehat{G}$ of $G$ that has a number of properties that are essential for the analysis of our algorithm. For example, with the right choice of parameters, if $G$ is $ϵ$-far from $C_{2r+1}$-freeness, then $\widehat{G}$ is $ϵ/2$-far from $C_{2r+1}$-freeness; for every $v,u\in V(G)$, if there exists an full-braid $\tilde{B}$ in $\widehat{G}$ such that $\text{ends}(\tilde{B})=(v,u)$ and $\text{length}(\tilde{B})\le r$, then $|\tilde{B}|\ge {\mathrm{deg}}_G(v)/\gamma$. Note that the choice of ${\mathrm{deg}}_{𝐆}(v)$ and not ${\mathrm{deg}}_{\widehat{𝐆}}(v)$, in the last inequality, is crucial for our proof to work and that $\widehat{G}$ is $(p,r)$-admissible since it is a subgraph of $G$.

We refer to the loop on line 3 of Algorithm 1, as Selection Loop, to the loop on line 5 of Algorithm 1, as Outer Loop, to the loop on line 7 as middle loop  and to the loop on line 12 as Inner Loop. In all of this section, $G$ is a $(p,r)$-admissible graph $G$ with $n$ vertices, $𝔾$ is an ordering of $G$, $\widehat{G}$ is a subgraph of $G$ obtained by trimming with the parameters $r,p\in \mathbb{N}$, $\gamma ,\delta \in {ℝ}^{+}$ and when we use the parameter ${\xi }_3$ we assume that it is a multiple of $2r$. Note that by Fact 3, Algorithm 1 receives a bound on the number of edges implicitly, since the value of $p$ is part of its input.

The following lemma follows directly from Algorithm 1.

In this section, we use the term knowledge-graph to refer to the subgraph of $G$ that is discovered by queries of Algorithm 1.