Zarankiewicz/main.tex

\documentclass[12pt,a4paper]{article}
\usepackage{chao}
\usepackage{algo}

\title{Zarankiewicz problem / Finding colored $K_{2,\ell}$}
\author{congyu}
\date{\today}

\begin{document}
\maketitle

\begin{problem}[Zarankiewicz problem, algorithmic version...]\label{prob1}
Given a groundset $U$ and a collection $\mathcal S=\{S_1,\dots,S_n\}$ of $n$ subsets of $U$. Let $m=\sum_{i\in [n]} |S_i|$. Check if there exist $k$ subsets which have exactly $\ell$ elements in common.
\end{problem}

$\alpha(G)$ is the arboricity of $G$. $\deg(v)$ is the degree of vertex $v$. $N=|U|$.

An equivalent formulation of \autoref{prob1} on graph is the following,
\begin{problem}[colored $K_{k,\ell}$]
    Given a bipartite graph $G=(V_1\sqcup V_2,E)$ where $V_1,V_2$ and $E$ represent elements in $U$, sets in $\mathcal S$ and element membership respectively. Color vertices in $V_1$ red and vertices in $V_2$ blue. Check if there is an induced $K_{k,\ell}$ with $k$ blue vertices and $\ell$ red vertices.
\end{problem}

\section{Existing algorithms}

% not bipartite!
% \subsection{subcubic combinatorial alg for detecting induced $C_4$}
% A recent paper \url{https://arxiv.org/pdf/2507.18845v1}.


\section{Finding $K_{2,\ell}$}
This has already been described in \url{https://chaoxu.prof/posts/2019-01-21-high-degree-low-degree-technique.html}.
\begin{theorem}[\cite{chiba_arboricity_1985} section 4]\label{alg:malpha}
    There exists an algorithm which finds all $K_{2,\ell}$ in $G$ with time complexity $O(m\alpha(G))$.
\end{theorem}
\begin{proof}
    The algorithm is described in \autoref{figalg:malpha},
\begin{figure}[!ht]
\begin{algo}
    sort vertices in $G$ in such that $\deg(v_1)\geq \dots \geq \deg(v_n)$\\
    for $i\in[n]$:\\ 
    \quad for each vertex $u\in N(v_i)$:\\
    \quad \quad let $U[v]=\emptyset$ for all $v$.\\
    \quad \quad for each vertex $w\in N(u)$ that is not $v_i$:\\
    \quad \quad \quad add $u$ to $U[w]$.\\
    \quad for all vertex $w\in V$ that is not $v_i$:\\
    \quad \quad if $|U[w]|= \ell$:\\ \quad 
    \quad \quad {output} tuple $(v_i,w,U[w])$\\
    \quad $G=G-v_i$
\end{algo}
\caption{An $O(m\alpha(G))$ algorithm for finding all colored $K_{2,\ell}$}
\label{figalg:malpha}
\end{figure}
This algorithm outputs all possible pairs $(v,w)$ such that $v$ and $w$ have exactly $\ell$ common neighbors. The total number of vertices this algorithm visits is $\sum_v [\deg(v)+\sum_{u\in N(v)} (\deg(u)-1)]=2\sum_{(u,v)\in E} \min\{\deg(u),\deg(v)\}\leq 4\alpha(G)m$. Thus this algorithm has running time $O(m\alpha(G))$.
\end{proof}

\begin{theorem}\label{alg:n2l}
    There exists an algorithm which solves \autoref{prob1} and has complexity in $O(n^2\ell)$ when $k=2$.
\end{theorem}
\begin{proof}
    There is an algorithm for finding axis-parallel rectangles in $O(m^{3/2})$ described in \cite{van_kreveld_finding_1990}. Now we show that this algorithm also finds colored $K_{2,\ell}$ in bipartite graphs and has complexity $O(m+n^2)$ with better analysis.
\begin{figure}[!ht]
\begin{algo}
    for $i\in [n]$:\\
    \quad for $S_k\in \mathcal S$:\\
    \quad \quad $C[S_k]\gets 0$\\
    \quad for $u\in S_i$:\\
    \quad \quad for all $S_j$ s.t. $j<i$ and $u\in S_j$:\\
    \quad \quad \quad $C[S_j]\gets C[S_j]+1$\\
    \quad \quad \quad if $C[S_j]\geq \ell$:\\
    \quad \quad \quad \quad {output} exist $K_{2,\ell}$\\
    {output} no $K_{2,\ell}$
\end{algo}
\caption{An $O(n^2\ell)$ algorithm for checking existence of a $K_{2,\ell}$}
\label{figalg:n2l}
\end{figure}
    We need to construct a data structure for the algorithm in \autoref{figalg:n2l}. We use a linked list to stored all elements in each $S_i$. This takes $O(M)$ times. For finding all $S_j$ such that $j<i$ and $u\in S_j$, we store a linked list starting from each $u$ and link $u$ with the element representing $u$ in $S_k$'s linked list, where $k$ is the largest value smaller than $i$ that $S_k$ contains $u$. These links can be built using bucket sort in $O(M)$ time.

    For the complexity we notice that for each $S_i$ we visit at most $O(n\ell)$ times since each counter $C[S_i]$ is at most $\ell$. Thus the total running time is $O(M+n^2\ell)=O(n^2\ell)$.
\end{proof}

There is actually a much simpler algorithm for the more general problem...

\begin{theorem}\label{alg:nkl}
    There exist an algorithm which solves \autoref{prob1} in $O(\ell n^k)$.
\end{theorem}
\begin{proof}
    Create a array $A$ of length $\binom{n}{k}$, originally all zero. Note that the length of the array is $O(n^k)$. Each element in the array corresponds to a combination of $k$ sets out of $\mathcal S$. We iterate over all elements in $U$ and find for each element $e$ the set of positions in $A$ for which the corresponding set contains $e$. We add 1 to these positions. The process stops when there is some $A[i]\geq \ell$. We visit every position in $A$ at most $\ell$ times. Thus the running time is $O(\ell n^k)$.
\end{proof}

\begin{theorem}[\cite{furedi_new_1996}]
    There exist a constant $c$ such that each $n$ vertex graph with more than $c\ell^{1/2}n^{3/2}$ must contain $K_{2,\ell}$.
\end{theorem}

Now we compose these algorithms to get a better running time for testing if a given bipartite graph contains a colored $K_{2,\ell}$.

\begin{lemma}\label{lem:densesubgraph}
    If $\alpha(G)> t$, then there is a subgraph $H\subset G$ such that $\min\{\deg(v): v\in V(H)\}\geq t$.
\end{lemma}
\begin{proof}
    $H$ can be found through repeatedly removing the vertex with minimum degree in $G$. Once the minimum degree is at least $t$, the subgraph induced by the remaining vertices has the minimum degree at least $t$. Now we need to show that $H$ is nonempty given that $\alpha(G)>t$. First observe that for any vertex $v\in G$ if $\alpha(G-v)>\deg_G(v)$, then $\alpha(G)=\alpha(G-v)$. Thus if $H$ is empty we would have $\alpha(G)\leq \min \deg(v)\leq t$, a contradiction.
\end{proof}

\begin{theorem}\label{thm:k2l}
    There is an algorithm which finds $K_{2,\ell}$ in time $O(l^{1/3}m^{4/3})$.
\end{theorem}

\begin{proof}
We compose previous algorithm using low-degree high-degree technique.

% If $\alpha(G)\leq t$, use the $O(mt)$ algorithm \autoref{figalg:malpha}. If $\alpha(G)>t$, then by \autoref{lem:densesubgraph}, we can find a subgraph $H\subset G$ with minimum degree at least $t$.
\begin{figure}[h!]
\begin{algo}
\textsc{CheckExistance$K_{2,\ell}(G)$}\\
if $t\geq \alpha(G)$\\
\quad use Algorithm\ref{figalg:malpha}\\
else\\
\quad find a subgraph $H\subset G$ with min degree at least $t$\\
\quad if $c|V(H)|^{3/2}\leq |E[H]|$\\
\quad \quad there exists $K_{2,\ell}\in H$, return True\\
\quad else\\
\quad \quad run Algorithm\ref{alg:n2l} on $H$
\end{algo}
\caption{An $O(l^{1/3}m^{4/3})$ algorithm for checking existence of a $K_{2,\ell}$}
\label{figalg:k2lfinal}
\end{figure}
Note that while finding $H$ we repeatedly delete the vertex with min degree. Meanwhile we can check the existence of $K_{2,\ell}$ which is not contained in $H$.
\end{proof}

\bibliographystyle{plain}
\bibliography{ref}
\end{document}