Finding K neighbours in an implicitly defined bipartite graph

Outline

Problem
Solution
- Requirements
- Algorithm
- Complexity Analysis
Example Problems
- CF-1957F2

I thought of this idea while solving 1957F2. It is extremely easy, cute (at least compared to the official solution), and can be generalized, so I'll share it here.

Problem

Given two sets of vertices $X$ and $Y$ and a boolean function $f : X \times Y \to {0, 1}$ , we define a bipartite graph $G = (V = (X \cup Y), E = ((u, v) ∣ u \in X, v \in Y, f (u, v) = 1))$

We need to find $k$ adjacent vertices in $G$ for every node $u \in X$ .

Solution

Requirements

We can compute $f (u, v)$ in $O (x)$ time.
We can construct a data structure $D (Z)$ from some subset $Z \subseteq Y$ in $O (p (| Z |))$ time, such that we can query if there exists some $v \in Z$ such that $f (u, v) = 1$ in $O (q (| Z |))$ time.

Algorithm

Definitions

$n = | X |$
$m = | Y |$
Let $Q (u, D (Z))$ be the query function which checks if there exists some $v \in Z$ such that $f (u, v) = 1$ .

We will use block decomposition with $B$ as the block size. The algorithm works in the following way:

Divide $Y$ into $⌈ m / B ⌉$ disjoint subsets of size $B$ . Let the $i$ 'th subset be $S_{i}$
Iterate over the subsets, while maintaining a list $L$ of all $u \in X$ for which we have found $< k$ neighbors till that point of time ( $L = X$ initially).
At subset $S_{i}$ , we will do the following:
1. Construct $D (S_{i})$ .
2. Create an empty list $H_{i}$ , and add $u$ to $H_{i}$ (also delete it from $L$ ) for all $u \in L$ such that $Q (u, D (S_{i})) = 1$ .
3. Compute $f (u, v) \forall u \in H_{i}, v \in S_{i}$ , and mark $v$ as a neighbor of $u$ if $f (u, v) = 1$ .
4. For every $u \in H_{i}$ for which we haven't found $k$ neighbors yet, add $u$ back to $L$ .

Note

We can trivially solve this problem faster for

k = 1

by constructing a segment tree over

Y

, doing dfs on it, and passing down elements of

X

to one of the two children based on queries from

D

constructed on elements from one of the two children.

Complexity Analysis

The cumulative time for building all the data structures will be $O (⌈ m / B ⌉ \cdot p (B))$ .

For queries:

At every $S_{i}$ , we query $Q (u, D (S_{i})) \forall u \in L$ . Since $| L | \leq n$ , this takes $O (n \cdot ⌈ m / B ⌉ \cdot q (B))$ time.
It's easy to see that every node $u \in X$ is added to $H_{i}$ for at most $k$ distinct values of $i$ . Every time a $u$ is added to $H_{i}$ , we compute $f (u, v)$ for $\leq B$ distinct values of $v$ . This takes $O (n \cdot B \cdot k \cdot x)$ time.

Therefore the total time taken is:

$O(n \cdot B \cdot k \cdot x + \lceil m/B \rceil \cdot (p(B) + n\cdot q(B)))$

The choice of $B$ is highly problem dependent, but in most setups where this idea could be used, I think we would have $k ⋘ n$ and $q$ would be pretty fast. I recommend solving the example problem to understand why the complexity is decent if you think it is garbage.

Example Problems

1. CF-1957F2

You are given an undirected tree of $n$ nodes. Each node $v$ has a value $a_{v}$ written on it. You have to answer queries related to the tree.

You are given $q$ queries. In each query, you are given 5 integers, $u_{1}$ , $v_{1}$ , $u_{2}$ , $v_{2}$ , and $k$ . Denote the count of nodes with value $c$ on the path $u_{1} \to v_{1}$ with $x_{c}$ , and the count of nodes with value $c$ on the path $u_{2} \to v_{2}$ with $y_{c}$ . If there are $z$ such values of $c$ such that $x_{c} \neq y_{c}$ , output any $min (z, k)$ such values in any order.

Solution

To be updated