#  $k$-Dominating set in sparse graphs

Mirza Redzic

(February 2023)

##  1 $k$ Dominating set in Sparse graphs

###  1.1 $k\geq 3$

Recall that a $\ell$-orthogonal vectors problem ($\ell$-OV) is stated as
follows;

Given: $\ell$ sets $A_{1},\dots A_{l}$, each containing $n$ binary vectors of
dimension $d$

Question: Is there a set of vectors $a_{1}\in A_{1},\dots,a_{\ell}\in
A_{\ell}$ such that in every dimension $i$ the corresponding component of at
least one vector equals to $0$?

######  Conjecture 1.1 ($\ell$OVH).

For no $\ell\geq 2$ and $\varepsilon>0$ is there an algorithm for $\ell$-OV
problem running in time $\mathcal{O}(n^{\ell-\varepsilon}{\rm poly}(d))$.

Unbalanced variant of OVH deals with the special case when $|A_{i}|=n$ for
every $i<\ell$ and $|A_{\ell}|=n^{\alpha}$ for some $0\leq\alpha\leq 1$.

######  Conjecture 1.2 (Unbalanced $\ell$OVH).

For no $\ell\geq 2$ and $\varepsilon>0$ is there an algorithm for unbalanced
$\ell$-OV problem running in time
$\mathcal{O}(n^{\ell-1+\alpha-\varepsilon}{\rm poly}(d))$.

######  Theorem 1.3.

If $k\geq 3$, and $G$ be a graph with $O(n^{\alpha})$ edges for some
$1\leq\alpha\leq 2$. Then there is no
$\mathcal{O}(n^{k-2+\alpha-\varepsilon})$ time algorithm solving
$k$-dominating sets problem on $G$ unless SETH fails.

###### Proof.

To prove this lower bound, we will use the Unbalanced $\ell$-orthogonal vector
hypothesis and show that this reduction yields the desired result.

Let $A_{1},\dots,A_{k-1}$ denote the sets of $d$-dimension binary vectors of
size $n$ and $A_{k}$ be a set of $d$-dimension binary vectors of size
$n^{\alpha-1}$ for some $1\leq\alpha\leq 2$ and assume $d=\mathcal{O}(\log
n)$. We will construct a graph with $N$ vertices and $N^{\alpha}$ edges with
$N=\mathcal{O}(n)$ that has dominating set of size $k$ if and only if we can
find vectors $a_{1}\in A_{1},\dots,a_{k}\in A_{k}$ such that
$\prod_{i=1}^{k}a_{i}[j]=0$ for every $j=1,\dots,d$.

Cosider the following reduction.

  * •

Let $G$ be an empty graph.

  * •

We start by adding a vertex for every vector in $A_{1}$ to $G$. Label these
vertices by $a^{1}_{1},\dots a^{1}_{n}$ and add a vertex labelled $A_{1}$ and
connect this vertex to all vertices $a^{1}_{i}$.

  * •

Repeat the previous step for all sets $A_{i}$.

  * •

Connect $a^{k}_{j}$ to $a^{s}_{t}$ for every $j=1,\dots,n^{\alpha-1}$ and
every $t=1,\dots,n$, $s=1,\dots,k-1$.

  * •

Add $d$ vertices labelled $D_{1},\dots,D_{d}$ and add an edge between
$a^{i}_{j}$ and $D_{t}$ if and only if $a^{i}_{j}[t]=0$ for all $i,j,t$.

######  Claim 1.4.

Graph $G$ constructed as above has $N=\mathcal{O}(n)$ vertices and
$\tilde{\mathcal{O}}(n^{\alpha})$ edges.

###### Proof.

It is easy to see that $N=d+k+(k-1)n+n^{\alpha-1}=\mathcal{O}(n)$. We proceed
to count the edges. Notice that for all $1\leq i<k$, $a^{i}_{j}$ has degree at
most $d+1$ and $a^{k}_{j}$ has degree at most $d+n$. Furthermore, $A_{i}$ all
have degree exactly $n$ for $i<k$, and $A_{k}$ has degree $n^{\alpha-1}$.
Finally, $D_{i}$ have degrees at most $(k-1)n+n^{\alpha-1}$.

Hence, adding up all degrees yields

$2|E(G)|\leq[(k-1)n+n^{\alpha-1}]+[d((k-1)n+n^{\alpha-1})]+[(k-1)n(d+1)+n^{\alpha-1}(d+n)]=\mathcal{O}(n^{\alpha}+dn)$

which is $\tilde{\mathcal{O}}(n^{\alpha})$ as desired. ∎

We proceed to prove the correctness of our reduction. That is, we prove the
following claim.

######  Claim 1.5.

Given an instance $A_{1},\dots,A_{k}$ of the unbalanced $k$-OV, construct the
graph $G$ as described above. Then $G$ has a dominating set of size $k$ if and
only if there exists set of vectors $a_{1}\in A_{1},\dots,a_{k}\in A_{k}$ such
that in every dimension $i$ the corresponding component of at least one vector
equals to $0$. Furthermore, given a dominating set $S$ of size $k$, we can
find the vectors $a_{1},\dots a_{k}$ as above.

###### Proof.

Let $A_{1},\dots,A_{k}$ be the instance of the unbalanced $k$-OV and let $G$
be a graph constructed as above. Suppose first that there are vectors
$a_{1}\in A_{1},\dots,a_{k}\in A_{k}$ such that $\prod_{i=1}^{k}a_{i}[j]=0$
for every $j=1,\dots,d$. Now we claim that the vertices corresponding to
vectors $a_{1},\dots,a_{k}$, namely $a^{1}_{s_{1}},\dots,a^{k}_{s_{k}}$
dominate $G$.

By construction for every $i=1,\dots,d$, at least one of
$a^{1}_{s_{1}},\dots,a^{k}_{s_{k}}$ is adjacent to $D_{i}$ and hence all
$D_{i}$ are dominated. Furthermore, since each $a^{i}_{s_{i}}$ is adjacent to
$A_{i}$, also all $A_{i}$’s are dominated.

Consider now $a^{k}_{i}$ for some $i$. It is adjacent to $a^{1}_{s_{1}}$,
hence all $a^{k}_{i}$ are also dominated. Finally, every $a^{j}_{i}$, for some
$j\leq k-1$, is adjacent to $a^{k}_{s_{k}}$. Thus we showed that all vertices
in $G$ are dominated by $a^{1}_{s_{1}},\dots,a^{k}_{s_{k}}$.

Conversely, suppose that there exists a dominating set $S$ of size $k$. It is
easy to see that $S$ contains exactly one vertex from $N[A_{i}]$ for each $i$.

Consider now the vertex $A_{k}$. It is either dominated by itself, or some
vertex $a^{k}_{i}$ is in $S$. If $A_{k}$ is in $S$, then by the argument
above, no $a^{k}_{i}$ is contained in $S$ and consequently
$S\subseteq\\{A_{1},\dots,A_{k}\\}$ (otherwise if $A_{i}$ was not in $S$, then
by the observation above, $a^{i}_{j}$ would be the only vertex from $N[A_{i}]$
contained in $S$, and it is easy to see that for some $\ell\neq j$,
$a^{i}_{\ell}$ is not dominated). But since $S$ contains $k$ elements, the
equality holds and as e.g. $D_{1}$ is not dominated, this cannot be the case.

Hence, we may conclude that for some $s_{k}$, $a^{k}_{s_{k}}$ is contained in
$S$ and it dominates all $a_{i}^{j}$ for $j<k$. Now W.L.O.G. we may assume
that $S$ contains no vertices $A_{i}$, since the open neighbourhood of each
$A_{i}$ is already dominated by $a^{k}_{s_{k}}$ and whenever we are given a
set $S$ that contains $A_{i}$, we may choose $s_{i}$ arbitrarily, and replace
$A_{i}$ with $a^{i}_{s_{i}}$.

Finally, given such $S=\\{a^{1}_{s_{1}},\dots,a^{k}_{s_{k}}\\}$, we claim that
the vectors corresponding to these elements satisfy the condition that in each
coordinate $i$ at least one of the vectors $a^{j}_{s_{j}}[i]=0$.

This can be argued by observing that for every $i$ there exists some $j$ such
that $a^{j}_{s_{j}}$ dominates $D_{i}$ which in turn gives us that the vector
corresponding to $a^{j}_{s_{j}}\in A_{j}$ has $i$-th entry equal to zero as
desired. ∎

Finally, we proceed to prove that any algorithm that solves Sparse Dominating
Set Problem in $\mathcal{O}(n^{k-2+\alpha-\varepsilon})$ for some positive
$\varepsilon$ violates unbalanced $\ell$OVH.

######  Claim 1.6.

Let $1\leq\alpha\leq 2$ and $G$ be a graph with $\mathcal{O}(n)$ vertices and
$m=\mathcal{O}(n^{\alpha})$ edges. Assuming unbalanced $\ell$OVH, for any
$k\geq 3$ and $\varepsilon>0$ there exists no algorithm solving $k$-dominating
set on $G$ in the running time $\mathcal{O}(n^{k-2+\alpha-\varepsilon})$.

###### Proof.

Assume for contradiction such algorithm existed. Given an instance of
unbalanced $k$-OV $A_{1},\dots,A_{k}$ with $|A_{k}|=n^{\alpha-1}$, we can
apply the reduction from above in $\mathcal{O}(n^{\alpha})$ time to obtain the
corresponding graph $G$. Then, we apply the sparse $k$ dominating set
algorithm in
$\mathcal{O}(n^{k-2+\alpha-\varepsilon})=\mathcal{O}(n^{k-1+(\alpha-1)-\varepsilon})$,
thus yielding a correct solution of our unbalanced $k$-OV instance and
contradicting the $\ell$OVH. ∎

And since SETH $\Rightarrow\ell{\rm OVH}$ reference missing, we can combine
the claims above with our construction to conclude the proof of the theorem. ∎

Figure 1: Example of construction described in the proof of Theorem 1.3 for
$k=3$ and $A_{1}=\\{1001,1111,0110,1011\\}$,
$A_{2}=\\{1100,1110,1001,1100\\}$, $A_{3}=\\{1101,1011\\}$ with dominating set
$\\{a_{3}^{1},a_{3}^{2},a_{1}^{3}\\}$

We proceed to show that the lower bound proved above is tight for $k\geq 3$.
In particular, we design an algorithm that solves the $k$-dominating set
problem on sparse graphs in the best possible time, assuming SETH.

######  Theorem 1.7.

Given a graph $G$ with $n$ vertices and $m=O(n^{\alpha})$ edges, for some
$1\leq\alpha\leq 2$, we can construct an algorithm with running time
$\mathcal{O}(n^{k-2+\alpha})$ that solves the $k$-dominating set problem for
$k\geq 3$ on $G$.

######  Lemma 1.8.

Given any graph $G$, we can solve $k$-dominating set on $G$ in time
$\mathcal{O}(n^{k})$ for any $k\geq 2$, assuming $\omega=2$.

###### Proof.

Fix any vertex $u$ and construct a row vector $r(u)$ that has $i$-th entry $0$
if $u$ dominates $v_{i}$ and $1$ otherwise. Let $A$ be an $n\times n$ matrix
where $i$-th row is $r(v_{i})$.

Let $S$ be an arbitrary subset of $V(G)$ of size $k-1$. Construct a column
vector $c(S)$ that has $i$-th entry $0$ if $S$ dominates $v_{i}$ and $1$
otherwise. Let $B$ be an $n\times{n\choose k-1}=n\times\mathcal{O}(n^{k-1})$
matrix where $i$-th column is $c(S_{i})$ for all subsets $S_{i}$ of $V(G)$ of
size $k-1$.

Let $C=A\cdot B$. It is easy to see that $C_{i,j}=0$ if and only if
$\\{v_{i}\\}\cup S_{j}$ dominate $G$. Assuming $\omega=2$, we can construct
$C$ in $\mathcal{O}(n^{2}+n^{k-1}\cdot n)=\mathcal{O}(n^{k})$ and we can then
find a dominating set of size $k$, or conclude that it does not exist in
$\mathcal{O}(n^{k})$ by iterating through $C$. ∎

###### Proof (of Theorem 1.7)..

By pigeonhole principle, at least one vertex in any dominating set of size $k$
dominates at least $\frac{n}{k}$ vertices. There are only
$\mathcal{O}(\frac{m}{n})$ such vertices and we can detect them all in linear
time. Let $U$ be a set of all such vertices.

Fix a vertex $u\in U$. We partition $V(G)$ in three parts $V_{1},V_{2},V_{3}$
as follows. Let $V_{1}=\\{u\\}$, $V_{2}=N(u)$, $V_{3}=V(G)\setminus(V_{1}\cup
V_{2})$.

Run the algorithm as in previous lemma on $G[V_{3}]$ to check in time
$\mathcal{O}(n^{k-1})$ if it admits a dominating set of size $k-1$. If it
does, return True.

Otherwise, let $G_{u}$ be obtained from $G[V_{2}\cup V_{3}]$ by adding all
edges $uv$ for each $u,v$ in $V_{2}$. We can construct $G_{u}$ in
$\mathcal{O}(n^{2})$.

We claim that now $G_{u}$ admits a dominating set of size $k-1$ if and only if
$G$ has a dominating set of size $k$ that contains $u$ (assuming $G[V_{3}]$
has no dominating set of size $k-1$, as such set would be detected above).

Indeed, first direction is trivial, so to prove the second direction, assume
that $G$ has a dominating set $S$ of size $k$ that contains $u$ and assume for
contradiction that $G_{u}$ has no dominating sets of size $k-1$. Clearly $S$
dominates all vertices in $V_{3}$, and since none of these vertices are
adjacent to $u$, after deleting $u$ from $S$, they are still dominated. Hence,
we may assume that some vertex $v$ from $v_{2}$ is not dominated by
$S\setminus\\{u\\}$. Furthermore, since $V_{2}$ forms a clique in $G_{u}$,
this implies that no vertex from $V_{2}$ is in $S$. But this means that the
set $S\setminus\\{u\\}\subseteq V_{3}$ is a set of size $k-1$ that dominates
$V_{3}$, and equivalently that $G[V_{3}]$ admits a dominating set of size
$k-1$, which is a contradiction.

Now we run the algorithm as in previous lemma on $G_{u}$ to check in time
$\mathcal{O}(n^{k-1})$ if it admits a dominating set of size $k-1$. If it
does, return True.

Since we fixed an arbitrary vertex $u\in U$, we repeat the same algorithm on
every vertex in $U$ until it returns True. If we exhaust all vertices from
$U$, return False.

Obviously this algorithm is correct and runs in
$\mathcal{O}(\frac{m}{n}(n^{2}+2\cdot n^{k-1}))=\mathcal{O}(n^{\alpha}\cdot
n^{k-2})$, assuming $k\geq 3$. ∎

##  2 $k=2$ case

###  2.1 Upper bound

For $2$-dominating set problem in sparse graphs, we consider two cases based
on how sparse the graph is:

  * •

$m=\mathcal{O}(n^{\frac{3}{2}})$

  * •

$m=\Omega(n^{\frac{3}{2}})$.

We notice that $m=\Theta(n^{\frac{3}{2}})$ is contained in both cases and we
will deal with this case later.

We first construct a very simple combinatorial algorithm that works well for
graphs with high sparsity (that is for $m=\mathcal{O}(n^{\frac{3}{2}})$).

Input: A sparse graph $G$.

Result: True if $G$ admits a 2-dominating set, False otherwise.

1 _initialisation:_

2 $U:=\\{u\in V(G)\mid\deg(u)\geq\frac{n}{2}-1\\}$

3 $Q:=V(G)$

4 $s:=V(G)$

5

6 _main part:_

7 for  _$u$ in $U$_ do

8 for  _$v$ in $N[u]$_ do

9 $Q$.delete($v$);

10 end for

11 for  _$v$ in $Q$_ do

12 $s$ = intersection($s,N[v]$)

13 end for

14 if  _$|s| >0$_ then

15 return True

16 end if

17

18 end for

return False

Algorithm 1 Combinatorial $2$-dominating set algorithm

######  Lemma 2.1.

Algorithm 1 is correct.

###### Proof.

We have to show that the algorithm will return True if and only if $G$ admits
a dominating set of size two. First observe that by pigeonhole principle, if a
two dominating set $S=\\{u,v\\}$ exists, then at least one vertex in $S$ has
degree at least $\frac{n}{2}-1$.

Assume that $G$ has a dominating set of size two $S=\\{u,w\\}$ and W.L.O.G,
assume that $u$ has degree at least $\frac{n}{2}-1$.

Since the outer most loop iterates over all vertices of large degree, it will
consider $u$ at some point (or return True before that, which is also fine).
Hence, it is sufficient to argue that $w$ is in the intersection of $N(v)$ for
all $v$ in $Q$, since in that case $\\{w\\}\subseteq s$. However, by observing
that at the end of the for loop at line 7, all vertices that are not dominated
by $u$ are contained in $Q$. By assumption that $\\{u,w\\}$ dominates $G$, all
vertices in $V(G)\setminus N[u]$ must contain $w$ in their closed
neighbourhoods.

Now assume that the algorithm returns True and fix $u,s,Q$ as they were at the
point when the algorithm returns. Then, we claim that $w:=s[0]$ and $u$ from
the last iteration form a dominating set. Let $v\in V(G)$ be any vertex. If it
is in the closed neighbourhood of $u$, then it is dominated by $u$, so we may
assume that it is not in $N[u]$. But then $v$ is contained in $Q$ and every
vertex in $s$ contains $v$ in its closed neighbourhood. In particular $w$
dominates $v$ as we wanted to show. ∎

######  Lemma 2.2.

Algorithm 1 runs in $\mathcal{O}(\frac{m^{2}}{n})$ time.

###### Proof.

Follows from the fact that $U$ contains at most $\mathcal{O}(\frac{m}{n})$
vertices and $\sum_{u\in V(G)}|N(u)|=2m$. ∎

We summarize the previous two lemmas in the following theorem.

######  Theorem 2.3.

Given a graph $G$ with $n$ vertices and $m$ edges, we can solve 2-dominating
set problem in $\mathcal{O}(\frac{m^{2}}{n})$ time.

We move on to constructing a simple matrix multiplication algorithm that works
better than Algorithm 1 in graphs that are more dense (in particular
$m=\Omega(n^{\frac{3}{2}})$), assuming $\omega=2$.

Input: A sparse graph $G$.

Result: True if $G$ admits a 2-dominating set, False otherwise.

1 _initialisation:_

2 $U:=\\{u\in V(G)\mid\deg(u)\geq\frac{n}{2}-1\\}$

3 $A:=$ adjacency matrix of $G$

$A\leftarrow A+I_{n}$ /* Make diagonal entries of $A$ 1 */

4

5 $M:=|U|\times n$ all zero matrix

6 $M[i,j]\leftarrow 1$ if $U[i]$ is not adjacent to $v_{j}$ and $U[i]\neq
v_{j}$

7 _main part:_

8 $C:=M\cdot A$

9 for  _$i$ in $1,\dots,|U|$_ do

10 if  _$max_{1\leq j\leq n}C[i,j]\geq n-\deg(U[i])-1$_ then

11 return True

12 end if

13

14 end for

15return False

Algorithm 2 $2$-dominating set algorithm, using fast matrix multiplication

######  Theorem 2.4.

Algorithm 2 is correct and runs in $\mathcal{O}(n^{2})$ time, assuming
$\omega=2$.

###### Proof.

Assume first that there exists a dominating set $S=\\{u,v\\}$ of size $2$ in
$G$. As we observed previously, by pigeonhole principle, at least one vertex
in $S$, W.L.O.G. $u$, has degree at least $\frac{n}{2}-1$.

We claim that multiplying the row of $M$ corresponding to $u$ by the column of
matrix $A$ corresponding to $v$ is at least $n-\deg(u)-1$. Observe that the
row corresponding to $u$ has $1$ in exactly does entries not dominated by $u$
(exactly $n-|N[u]|=n-(\deg(u)+1)$ ones).

By assumption that $S$ is a dominating set, $v$ dominates all the vertices
that $u$ doesn’t. In other words, any vertex that is not dominated by $u$ is
either $v$, or adjacent to $v$.

It is now sufficient to argue that the column of $A$ corresponding to $v$ has
one in every row that corresponds to a vertex not dominated by $u$. Observing
that diagonal entries of $A$ are equal to one handles the case if $u$ does not
dominate $v$. Finally, since $A-I_{n}$ is adjacency matrix (i.e. has non-
diagonal entries equal to adjacency matrix), the claim also holds for the
vertices not dominated by $u$ that are adjacent to $v$.

Conversely, assume that in the product of the two matrices, there exists an
entry corresponding to vertices $u,v$ that is at least $n-\deg(u)-1$.

We observe that such an entry exists in $C$ if and only if for every vertex
$w_{i}$, for $1\leq i\leq n-\deg(u)-1$ that is not dominated by $u$, the entry
corresponding to $w_{i},v$ in $A$ is equal to one.

But by construction of $A$, an entry corresponding to $w_{i},v$ equals one if
and only if $w_{i}\in N[v]$, or in other words, if $v$ dominates $w_{i}$.
Hence, any vertex not dominated by $u$ is dominated by $v$ and $\\{u,v\\}$ is
a dominating set.

Finally, assuming $\omega=2$, we can multiply two matrices of dimensions
$\frac{m}{n}\times n$ and $n\times n$ in $\mathcal{O}(n^{2})$ time. ∎

We conclude this section by showing that there exists a probabilistic
algorithm that solves $2$-dominating set problem on graph with $n^{\alpha}$
edges in subquadratic time for all $\alpha<2$, assuming $\omega=2$.

######  Lemma 2.5.

Let $G$ be a graph with $n$ vertices and $m=n^{\alpha}$ edges. Let $V_{1}$ be
the set of all vertices in $G$ with degree at least $\frac{n}{2}-1$ and
$V_{2}$, $V_{3}$ be two copies of vertices of $G$. Let $D$ be a weighted
directed tripartite graph with vertex set $V(D)=V_{1}\cup V_{2}\cup V_{3}$ and
add an edge with weight $1$ from $v_{1}\in V_{1}$ to $v_{2}\in V_{2}$ if and
only if $v_{1}$ does not dominate $v_{2}$ in $G$. Furthermore, add an edge
with weight $1$ from $v_{2}\in V_{2}$ to $v_{3}\in V_{3}$ if and only if
$v_{2}$ dominates $v_{3}$ in $G$. Then, there exists a dominating set of size
two in $G$ if and only if there exists $v_{1}\in V_{1},v_{3}\in V_{3}$ such
that $f(D,v_{1},v_{3})=\deg^{+}_{D}(v_{1})$, where $f(D,s,t)$ is the maximal
amount of flow from $s$ to $t$ in $G$.

###### Proof.

Assume first that there exists a dominating set of size two $S=\\{u,v\\}$ in
$G$ and W.L.O.G, assume that $\deg(u)\geq\frac{n}{2}-1$, i.e. $u\in V_{1}$.

Now we claim that the flow from the copy of $u$ in $V_{1}$ to the copy of $v$
in $V_{3}$ is equal to degree of $u$. This is easy to see as every vertex in
$G$ that is not dominated by $u$ is dominated by $v$, hence for every vertex
$x$ in $V_{2}$ such that $(u,x)\in E(D)$ it holds that $(x,v)\in E(D)$, so we
can send one unit of flow from $u$ to $x$ and from $x$ to $v$ for every vertex
in $N^{+}_{D}(u)$, so $f(D,u,v)\geq\deg^{+}_{D}(u)$ and the other inequality
holds trivially, hence we obtain the equality.

Conversely, assume that there exist vertices $u\in V_{1}$ and $v\in V_{3}$
such that $f(D,s,t)=\deg^{+}_{D}(u)$. Then, it follows directly that for any
vertex $x$ in $N^{+}_{D}(u)$, also $(x,v)\in E(D)$. Thus, $v$ dominates every
vertex in $G$ that $u$ does not and finally the set $S=\\{u,v\\}$ dominates
$G$. ∎

For the rest of this section, unless stated otherwise, whenever we use $D$, we
will assume the construction from the previous lemma, and we also observe that
for every $u\in V_{1}$, $N^{+}_{D}(u)=N_{D}(u)$, similarly for $v\in V_{3}$,
$N^{-}_{D}(v)=N_{D}(v)$.

######  Lemma 2.6.

Fix some $\varepsilon>0$ and let $D$ be any weighted tripartite directed graph
with parts $V_{1},V_{2},V_{3}$ and any edge either going from a vertex in
$V_{1}$ to a vertex in $V_{2}$, or from a vertex in $V_{2}$ to a vertex in
$V_{3}$. For convenience we will also assume that $w(e)=1$ for any edge.
Assuming $\omega=2$, we can solve max flow problem on $D$ in time
$\mathcal{O}(|V_{1}|\cdot|V_{2}|+|V_{2}|\cdot|V_{3}|+|V_{1}|\cdot|V_{3}|)$.

###### Proof.

Construct the matrices $A,B,C$ as follows. Let $A$ be a $|V_{1}|\times|V_{2}|$
matrix with $A[v_{1},v_{2}]=1$ if and only if there is an edge from $v_{1}\in
V_{1}$ to $v_{2}\in V_{2}$ and $0$ otherwise. Similarly, let $A$ be a
$|V_{2}|\times|V_{3}|$ matrix with $B[v_{2},v_{3}]=1$ if and only if there is
an edge from $v_{2}\in V_{2}$ to $v_{3}\in V_{3}$ and $0$ otherwise.

Finally, let $C$ be a $V_{1}\times V_{3}$ matrix with $C=A\cdot B$. We claim
that for any vertex $u\in V_{1},v\in V_{3}$, $C[u,v]$ represents the max flow
$f(D,u,v)$. In particular, there exists an entry $C[u,v]$ such that
$C[u,v]=\deg(u)$ if and only if for $u\in V_{1}$ and $v\in V_{3}$
$f(D,u,v)=\deg(u)$.

To see why this holds, fix a row $r$ of $A$ corresponding to an arbitrary
vertex $u\in V_{1}$ and a column $c$ of $B$ corresponding to an arbitrary
vertex $v\in V_{3}$. Now $r[i]\cdot c[i]=1$ if and only if there exists an
edge from $u$ to $i\in V_{2}$ and from $i$ to $v$, i.e. if and only if there
exists a path of length two from $u$ to $v$. Hence $r\cdot c$ is exactly the
number of paths of length two from $u$ to $v$ and since we assumed that
$w(e)=1$ for every edge, it is exactly equal to max flow from $u$ to $v$ (due
to the structure of $D$).

Finally, assuming $\omega=2$, we can multiply these matrices in
$\mathcal{O}(|V_{1}|\cdot|V_{2}|+|V_{2}|\cdot|V_{3}|+|V_{1}|\cdot|V_{3}|)$ and
the verification takes $\mathcal{O}(|V_{1}|\cdot|V_{3}|)$ time. ∎

######  Lemma 2.7.

Given a graph $G$ with $n$ vertices and $m=n^{\alpha}$ edges, fix an
$\varepsilon>0$ and let $D$ be a digraph constructed as above. We can check in
time $\mathcal{O}(m+n^{2-\varepsilon})$ if there exists a vertex $v$ in
$V_{3}$ such that $\deg_{D}(v)\geq n^{\alpha-1+\varepsilon}$ and for some
$u\in V_{1}$ $f(D,u,v)=\deg_{D}(u)$.

###### Proof.

There are at most
$\frac{m}{n^{\alpha-1+\varepsilon}}=\mathcal{O}(\frac{n^{\alpha}}{n^{\alpha-1+\varepsilon}})=\mathcal{O}(n^{1-\varepsilon})$
vertices in $V_{3}$ with degree at least $n^{\alpha-1+\varepsilon}$.

Remove all vertices $v_{3}\in V_{3}$ that have degree smaller than
$n^{\alpha-1+\varepsilon}$ from $D$.

Note that
$|V_{1}|=\mathcal{O}(n^{\alpha-1}),|V_{2}|=n,|V_{3}|=\mathcal{O}(n^{1-\varepsilon})$.
Apply the result from Lemma 2.6 to obtain an algorithm that runs in
$\mathcal{O}(n^{\alpha-1}\cdot n+n\cdot
n^{1-\varepsilon}+n^{\alpha-1}n^{1-\varepsilon})=\mathcal{O}(m+n^{2-\varepsilon})$
as desired. ∎

For the rest of this section, we will assume that every vertex in $V_{3}$ has
degree at most $n^{\alpha-1+\varepsilon}$. Furthermore, observe that if
$f(D,u,v)=\deg(u)>n^{\alpha-1+\varepsilon}$, then also
$\deg(v)>n^{\alpha-1+\varepsilon}$, so we can also remove all vertices from
$V_{1}$ that have degree greater than $n^{\alpha-1+\varepsilon}$, i.e. for the
rest of this section, assume that each vertex in $V_{1}$ has degree at most
$n^{\alpha-1+\varepsilon}$.

######  Lemma 2.8.

Given a graph $G$ with $n$ vertices and $m=n^{\alpha}$ edges, construct a
graph $D$ as above. Assume W.L.O.G. that every vertex in $V_{1}$ and $V_{3}$
has degree at most $n^{\alpha-1+\varepsilon}$ for some $\varepsilon>0$. Then
there exists a probabilistic subquadratic time algorithm that checks if $G$
has a dominating set of size $2$ that returns false only if there is $G$ has
no dominating set of size $2$.

###### Proof.

Let $h:[n]\to[2n^{\alpha-1+\varepsilon}]$ be a uniform hash function. Let
$D^{\prime}$ be a graph obtained from $D$ by hashing $V_{2}$.

In particular, $V_{1}^{\prime}=V_{1}$, $V_{3}^{\prime}=V_{3}$ and
$V_{2}^{\prime}=h(V_{2})$ and $V(D^{\prime})=V_{1}^{\prime}\cup
V_{2}^{\prime}\cup V_{3}^{\prime}$. We add edges naturally, that is, in
$D^{\prime}$ there is an edge between $v_{1}\in V_{1}^{\prime}$ and $v_{2}\in
V_{2}^{\prime}$ if there exists a vertex $x\in V_{2}$ such that $(v_{1},x)\in
E(D)$ and $h(x)=v_{2}$ and similarly for edges between $V_{2}^{\prime}$ and
$V_{3}^{\prime}$.

Run the max flow algorithm using fast matrix multiplication as in Lemma 2.6 on
$D^{\prime}$. This gives us the running time of
$\mathcal{O}(n^{\alpha+\varepsilon})$ which is subquadratic for sufficiently
small $\varepsilon$.

Furthermore, if this algorithm returns false, then for every vertex $v_{1}\in
V_{1}^{\prime}$ and $v_{3}\in V_{3}^{\prime}$ there exists a vertex $v_{2}\in
V_{2}^{\prime}$ such that $(v_{1},v_{2})\in E(D^{\prime})$ and
$(v_{2},v_{3})\not\in E(D^{\prime})$, which further implies that there exists
a vertex $x\in V_{2}$ such that $(v_{1},x)\in E(D)$ and $h(x)=v_{2}$, but
there is no vertex adjacent to $v_{3}$ that $h$ maps to $v_{2}$, in particular
$(x,v_{3})\not\in E(D)$ and thus there is no dominating set of size $2$ in $G$
by Lemma 2.5. ∎

######  Lemma 2.9.

Assuming the setting as in proof of the previous lemma, let $v_{1}\in
V_{1}^{\prime}$, $v_{3}\in V_{3}^{\prime}$ be fixed and let $h$ be a uniform
hash function. Then if $v_{1},v_{3}$ do not dominate $G$, the probability that
the flow from $v_{1}$ to $v_{3}$ in $D^{\prime}$ is equal to degree of $v_{1}$
is at most $\frac{1}{2}$.

###### Proof.

Assuming $v_{1},v_{3}$ do not dominate $G$, there exists a vertex $x\in
N_{D}(v_{1})$ such that $x\not\in N_{D}(v_{3})$. The probability that the flow
from $v_{1}$ to $v_{3}$ in $D^{\prime}$ is equal to degree of $v_{1}$ is at
most the probability that there exists a vertex $y\in N_{D}(v_{3})$ such that
$h(x)=h(y)$.

Since degree of $v_{3}$ in $D$ is at most $n^{\alpha-1+\varepsilon}$, and the
codomain of $h$ is of size $2n^{\alpha-1+\varepsilon}$ we have:

$P(\exists y\in N_{D}(v_{3})\mid h(y)=h(x))\leq
n^{\alpha-1+\varepsilon}\cdot\frac{1}{2n^{\alpha-1+\varepsilon}}=\frac{1}{2}$

∎

We combine the last few lemmas to obtain the algorithm that solves dominating
set in subquadratic time with high probability.

######  Theorem 2.10.

Given a graph $G$ with $n$ vertices and $m=n^{\alpha}$ edges, for some
$1\leq\alpha<2$, there exists an algorithm running in time
$\tilde{\mathcal{O}}(n^{1+\frac{\alpha}{2}})$ that determines if $G$ has a
dominating set of size $2$ with probability at least $p$, for any $p\in(0,1)$.

###### Proof.

Let $\varepsilon>0$ (we will fix the value later). Using Lemma 2.7, we can
determine in time $n^{2-\varepsilon}$ if there exists a dominating set of size
$2$ whose both vertices have degree at least $n^{\alpha-1+\varepsilon}$ in
time $n^{2-\varepsilon}$.

If not, we construct $D$ as in Lemma 2.6 and remove all vertices from $V_{1}$
and $V_{3}$ with degree larger than $n^{\alpha-1+\varepsilon}$.

Let $h_{1},\dots,h_{\ell}:[n]\to[2n^{\alpha-1+\varepsilon}]$ be independent
uniform hash functions and let $D_{i}$ be graph generated by hashing $V_{2}$
with respective hash function $h_{i}$ for all $i\in[\ell]$. Note that $\ell$
will be fixed a bit later and depends on $p$, but we will assume that
$\ell=\mathcal{O}(\log(n))$.

Run the max flow algorithm on each of the $D_{i}$’s. If for some $i$ the
algorithm returns false, then we conclude that there is no dominating set of
size $2$ in $G$ and if for all $i$ the algorithm returns true, then we
conclude that there exists a dominating set of size $2$ in $G$.

We obtain a total running time of $\mathcal{O}(n^{2-\varepsilon}+\ell\cdot
n^{\alpha+\varepsilon})$. Let $\varepsilon=1-\frac{\alpha}{2}$ to obtain the
running time of $\mathcal{O}(n^{1+\frac{\alpha}{2}}+\ell\cdot
n^{1+\frac{\alpha}{2}})=\tilde{\mathcal{O}}(n^{1+\frac{\alpha}{2}})$, which is
subquadratic for all $1\leq\alpha<2$.

We proceed to prove the correctness. By Lemma 2.8, if $G$ has a dominating set
of size two, the algorithm will always yield a correct solution (i.e. there
are no false negatives). So, we may assume we are given a graph $G$ that has
no dominating set of size two.

Fix $v_{1}\in V_{1}$ and $v_{3}\in V_{3}$. By the previous lemma, the
probability that we obtain a false positive on this pair after hashing $V_{2}$
with any $h_{i}$ is at most $\frac{1}{2}$. Using the independence of hash
functions, we obtain that the probability that all hash functions yield a
false positive on $v_{1},v_{3}$ is $\frac{1}{2^{\ell}}$, that is, the
probability that for at least one hash function the algorithm detects that
$v_{1},v_{3}$ do not dominate $G$ is at least $1-\frac{1}{2^{\ell}}$.

Hence the probability that for at least one hash function the algorithm
detects that $G$ has no dominating set of size $2$ is at least
$(1-\frac{1}{2^{\ell}})^{m}$, where $m$ is the number of pairs $v_{1}\in
V_{1},v_{3}\in V_{3}$.

Let $\ell=c\log(m)$ and compute.

$(1-\frac{1}{2^{\ell}})^{m}=(1-\frac{1}{m^{c}})^{m}$

Clearly, for $c>1$, this converges to $1$ as $m$ grows, however, we want to
assure that the probability at least $p$ is achievable even in small graphs.
Furthermore, we can see that $p$ is increasing in $c$.

$(1-\frac{1}{m^{c}})^{m}=p\Rightarrow\frac{1}{m^{c}}=1-\sqrt[m]{p}$
$-c\log(m)=\log(1-\sqrt[m]{p})$
$c=\frac{\log(1-\sqrt[m]{p})}{\log(\frac{1}{m})}$

Hence, letting $\ell=\lceil c\log m\rceil$, gives us the probability of
correctness larger than $p$. ∎

##  3 Variations of $k$-dominating set problem and effect of sparsity on them

###  3.1 $k$ dominating set in Triangle-free graphs

We consider now the case when $G$ is a triangle-free graph and show that in
such graphs we can solve $2$-dominating set problem in linear time.

######  Proposition 3.1.

Let $G$ be a triangle-free graph. We can solve $2$-dominating set on $G$ in
$\mathcal{O}(m)$ time.

###### Proof.

Let $G$ be a triangle free graph. Fix a vertex $u$ with degree
$\geq\frac{n}{2}$. Now partition $V(G)$ into three parts $\\{u\\},X,Y$, where
$X=N(u)$ and $Y=V(G)\setminus(\\{u\\}\cup X)$.

Clearly $X$ is dominated by $u$, hence we only need to check if there is a
vertex $v$ dominating $Y$. Notice that this vertex can either be contained in
$X$, or $Y$, so we check these two cases separately.

Let $x\in X$ be arbitrary. Observe that $X$ forms an independent set, since if
for some $x^{\prime}\in X$ we had $\\{x,x^{\prime}\\}\in E(G)$, then
$\\{u,x,x^{\prime}\\}$ would form a triangle. It follows that $\\{u,x\\}$
dominates $G$ if and only if $\deg(x)=|Y|+1$ and we can thus check if any
vertex from $X$ dominates $Y$ in $\mathcal{O}(n)$ time.

Finally, let $y\in Y$ be arbitrary. Now, if $\\{u,y\\}$ dominates $G$, then
$G[Y]\cong K_{1,|Y|}$. Iterate through $Y$ and for every vertex $y^{\prime}$
check if it is adjacent to $y$. This takes a total of $\mathcal{O}(n)$ time.

If every vertex in $Y$ is adjacent to $y$, then $\\{u,y\\}$ is a dominating
set, otherwise, we check how many vertices in $Y$ are adjacent to $Y$. If at
least two and at most $|Y|-1$ vertices are adjacent to $Y$, we conclude that
there exists no vertex in $Y$ dominating $Y$, since $K_{1,|Y|}$ contains no
such vertex and hence no vertex $v$ in $G$ such that $\\{u,v\\}$ is a
dominating set.

Otherwise if exactly one vertex $y^{\prime}$ from $Y$ is adjacent to $y$, then
this vertex is the only possible candidate to dominate $Y$ and we may check if
it indeed dominates $Y$ in $\mathcal{O}(n)$ time.

Hence for a fixed large degree vertex $u$, we may check if there exists a
dominating set of size two in $G$ that contains $u$ in $\mathcal{O}(n)$ time.
Recall that there are $\mathcal{O}(\frac{m}{n})$ large degree vertices, and
therefore we can check if $G$ admits a dominating set of size two in
$\mathcal{O}(m)$ time, as desired. ∎

######  Conjecture 3.2.

Let $G$ be a graph with at most $\mathcal{O}(n)$ triangles. We can solve
$2$-dominating set on $G$ in $\mathcal{O}(m)$ time.

###  3.2 $k$ Dominating set at distance $\ell$

Let $\ell\geq 1$ be a fixed integer. We consider the dominating set at
distance $\ell$ as a natural generalization of $k$-dominating set problem,
where we say a vertex $u$ dominates a vertex $v$ if there exists a path from
$u$ to $v$ of length at most $\ell$. Clearly, if $\ell=1$, we have the usual
variant of the $k$-dominating set.

Formally, $k$-dominating set at distance $\ell$ problem can be stated as
follows.

Given: A graph $G$

Question: Is there a subset of vertices $S=\\{v_{1},\dots,v_{k}\\}$ such that
for every vertex $v\in V(G)$, distance from $v$ to some $v_{i}\in S$ is at
most $\ell$?

In this section, we prove that sparsity does not affect the fine grained
complexity of $k$-dominating set at distance $\ell$ problem. In fact, we prove
that a lower bound $n^{k}$ holds already for graphs with $m=\mathcal{O}(n)$
edges, assuming the $k$-OV hypothesis. Furthermore, we prove that if
$\omega=2$, we can construct algorithm that runs in
$\tilde{\mathcal{O}}(n^{k})$, thus matching the lower bound.

######  Proposition 3.3.

Let $G$ be a graph with $n$ vertices and $\mathcal{O}(n)$ edges and let
$\ell>1,k$ be fixed. Then, assuming SETH, there exists no algorithm running in
time $\mathcal{O}(n^{k-\varepsilon})$ for any $\varepsilon>0$.

###### Proof.

Consider the following reduction from $k$ orthogonal vectors. Let
$A_{1},\dots,A_{k}$ be an instance of $k$-OV problem of dimension $d$.

  * •

Let $G$ be an empty graph

  * •

Add a vertex for every vector in $A_{1}$ to $G$. Label those vertices by
$a_{1}^{1},\dots,a_{n}^{1}$ and add a vertex labeled $A_{1}$ and connect
$A_{1}$ to all $a^{1}_{i}$. Add $\ell-1$ dummy vertices and connect them to
form a path of length $\ell-1$ with one endpoint in $A_{1}$ and label the
vertex at the other endpoint $v_{1}$.

  * •

Repeat the previous step for all sets $A_{i}$.

  * •

Add $d$ vertices labelled $D_{1},\dots,D_{d}$ and add an edge between
$a_{j}^{i}$ and $D_{t}$ if and only if $a_{j}^{i}[t]=0$ for all $i,j,t$

  * •

For each $D_{i}$, add $\ell-1$ dummy vertices and connect them to form a path
of length $\ell-1$ with one endpoint in $D_{i}$ and label the dummy vertex at
the other endpoint $w_{i}$.

We claim that $G$ has a $k$-dominating set at distance $\ell$ if and only if
there exist vectors $a_{1}\in A_{1},\dots,a_{k}\in A_{k}$ such that
$\prod_{i}=1^{k}a_{i}[j]=0$ for all $j\in[d]$.

Suppose first that there exist such vectors and that they correspond to
vertices $a^{1}_{s_{1}},\dots,a^{k}_{s_{k}}$. Then we claim that those
vertices form a $k$-dominating set at distance $\ell$.

Observe that $a^{i}_{s_{i}}$ is adjacent to $A_{i}$, hence all the vertices
along the path from $A_{i}$ to $v_{i}$ are dominated by it. Furthermore, all
$a^{i}_{j}$ are adjacent to $A_{i}$, and since $\ell\geq 2$, they are also
dominated by $a^{i}_{s_{i}}$. Hence, we only need to make sure that $D_{i}$
and the vertices along the path from $D_{i}$ to $w_{i}$ are dominated for each
$i$.

However, for each $i$, there exists a vector corresponding to a vertex
$a^{j}_{s_{j}}$ such that the $i$-th entry of this vector is $0$ (under the
assumption that these vectors satisfy $k$-OV) and in particular, such vertex
$a^{j}_{s_{j}}$ is adjacent to $D_{i}$ and hence dominates all the vertices
along the path from $D_{i}$ to $w_{i}$ as desired.

Conversely, suppose that there exists a $k$-dominating set at distance $\ell$
in $G$. Fix some $i\in[k]$. There exists a vertex at distance at most $\ell$
from $v_{i}$ in the dominating set. W.L.O.G, we may assume that this vertex is
not an internal vertex on the path from $A_{i}$ to $v_{i}$, nor $v_{i}$, since
the set of vertices that any such vertex dominates is a subset of vertices
dominated by $A_{i}$.

Hence, any $k$-dominating set at distance $\ell$ consists of vertices
$\\{u_{1},\dots,u_{k}\\}$ where $u_{i}\in\\{A_{i}\\}\cup\\{a^{i}_{j}\mid
j\in[n]\\}$.

Assume that for all $i\in[k]$, $u_{i}=A_{i}$. Then clearly $w_{1}$ is not
dominated by any $u_{i}$, and this yields a contradiction. So, we may conclude
that for at least one $i$ and some $j$, $u_{i}=a^{i}_{j}$.

Since for all $i$, $w_{i}$ is dominated by some $u_{j}$, this means that
$u_{j}$ is adjacent to $D_{i}$, or that the vector corresponding to
$u_{j}=a^{j}_{s_{j}}$ has $i$-th entry equal to $0$.

We construct the $k$-orthogonal vectors $S$ as follows. If $u_{i}=a^{i}_{j}$,
put $u_{i}$ in $S$. Otherwise, if $u_{i}=A_{i}$, put $a^{i}_{1}$ in $S$.

It is clear from the arguments above that $S$ contains $k$ vectors that
satisfy the orthogonality condition.

Clearly $G$ has $\mathcal{O}(n)$ vertices, where $n=|A_{1}|=\dots=|A_{k}|$ and
$\mathcal{O}(n)$ edges. The reduction hence takes $\mathcal{O}(n)$ time and
any algorithm solving $k$-dominating set at distance $\ell$ in time
$n^{k-\varepsilon}$ would violate the OVH and thus SETH. ∎

######  Proposition 3.4.

Let $G$ be a graph with $n$ vertices and $m$ edges and fix
$k,\ell=\mathcal{O}(1)$. Assuming $\omega=2$, we can solve $k$-dominating set
at distance $\ell$ in $\mathcal{O}(n^{k})$.

###### Proof.

W.L.O.G, we may assume that $\ell>1$, as otherwise we have an instance of
$k$-dominating set problem and we already know that this statement holds.

Let $A$ be the adjacency matrix of $G$. Compute the matrices
$A^{2},\dots,A^{\ell}$. Assuming $\omega=2$, these computations take $\ell
n^{2}=\mathcal{O}(n^{2})$ time.

Entry $i,j$ in matrix $A^{t}$ counts how many walks of length $t$ are there
between $i$ and $j$ in $G$. Observe that if there exists no path of length $t$
between vertices $i$ and $j$ in $G$, that implies that there are also no walks
of length $t$ between them. Furthermore, every path is a walk, so if there
exists a path of length $t$ between $i$ and $j$, entry $A^{t}_{i,j}$ will be
non-zero.

Compute

$B_{ij}=\bigvee_{t=1}^{\ell}\big{(}A_{i,j}^{t}>0\big{)},$

and let $G^{\prime}$ be a graph with adjacency matrix $B-I_{n}$. Note that
$V(G)=V(G^{\prime})$.

We claim that $G^{\prime}$ has dominating set at most $k$ if and only if $G$
has dominating set of size $k$ at distance $\ell$.

Assume first that $G$ has a $k$-dominating set at distance $\ell$,
$S=\\{v_{1},\dots,v_{k}\\}$. Fix a vertex $v\in V(G)$. We want to show that
$v$ is dominated by some $v_{i}$ in $G^{\prime}$. If $v\in S$, we are done, so
assume this is not the case.

Then for some $1\leq i\leq k$, there exists a (non-trivial) path of length
$t\leq\ell$ between $v_{i}$ and $v$ in $G$.

Hence, the entry corresponding to $v_{i},v$ in $A^{t}$ will be non-zero and
hence, since $v_{i}\neq v$, this entry will be equal to $1$ in $B-I_{n}$ and
hence $v_{i}$ is adjacent to $v$.

Clearly, since $v$ was an arbitrary vertex, we may conclude that $S$ dominates
$G^{\prime}$.

Conversely, suppose that $S=\\{v_{1},\dots,v_{k}\\}$ is a $k$-dominating set
in $G^{\prime}$ and fix a vertex $v\in V(G)$. $v$ is either contained in $S$,
or adjacent to a vertex in $S$ in $G$. If $v$ was contained in $S$, then there
exists a path of length $0<\ell$ between $v$ and a vertex in $S$ and $v$ is
dominated by $S$.

Otherwise, assume that $v$ is adjacent to a vertex $v_{i}\in S$. Then there
exists a walk of length $t\leq\ell$ in $G$ and furthermore, by removing all
the cycles from a walk, we obtain path of length at most $t$. Hence, $v$ is
dominated by $v_{i}$ and $S$ dominates $G$ as desired.

Observe that we can compute $B$ in $\mathcal{O}(n^{2})$, and as we proved
above, we can check if a graph $G$ has a dominating set of size $k$ in
$\mathcal{O}(n^{k})$, assuming $\omega=2$. ∎

##  4 Work in Progress

Neighbourhood Subset problem is stated as follows:

Given: Graph $G$ with $n$ vertices and $m$ edges

Question: Is there a pair of vertices $x_{1},x_{2}\in G$ such that
$N(x_{2})\subseteq N(x_{1})$?

We explore some upper and lower bounds for this problem.

######  Theorem 4.1.

Neighbourhood Subset problem cannot be solved in
$\mathcal{O}(n^{2-\varepsilon})$ for any $\varepsilon>0$, assuming OVH.

###### Proof.

Let $A_{1}$, $A_{2}$ be two sets containing $n$ $d$-dimensional binary
vectors. Furthermore, W.L.O.G. we assume that $A_{1},A_{2}$ contain no all
zero vectors and that they both contain an all one vector (if not, adding one
such vector will not affect the OV instance). Consider the following reduction
from OV problem on instance $A_{1},A_{2}$.

  * •

Let $G$ be a graph whose vertex set contains $A_{1}\cup A_{2}$ and no edges.

  * •

Add $D=\\{D_{1},\dots,D_{d}\\}$ to the vertex set of $G$ and add an edge
between $a^{1}_{i}\in A_{1}$ and $D_{j}$ if $a^{1}_{i}[j]=0$. Similarly add an
edge between $a^{2}_{i}\in A_{2}$ and $D_{j}$ if $a^{2}_{i}[j]=1$.

  * •

Add a vertex $w$ to $G$ and connect it to all vertices in $D$.

  * •

Add a vertex $v$ to $G$ and connect it to all the vertices in $G$.

  * •

Let $\phi:A_{2}\cup D\cup\\{w\\}\to\\{0,1\\}^{\log|A_{2}\cup D\cup\\{w\\}|}$
be a bijective function (assume W.L.O.G. that $|A_{2}\cup D\cup\\{w\\}|=2^{t}$
for some $t$, otherwise add sufficiently many all $1$ vectors to $A_{2}$).

  * •

Add $2t$ vertices $I^{1}_{1},\dots I^{1}_{t}$ and $I^{2}_{1},\dots I^{2}_{t}$
(recall that $t=\mathcal{O}(\log n)$) and label the set containing these $2t$
vertices $I$.

  * •

Add an edge between every pair of distinct vertices $u\in A_{1}\cup I,v\in I$.

  * •

For any vertex $x\in A_{2}\cup D\cup\\{w\\}$, add an edge between $x$ and
$I^{1}_{i}$ if $\phi(x)[i]=1$. Otherwise, add an edge between $x$ and
$I^{2}_{i}$.

  * •

Let $\psi:A_{1}\to\\{0,1\\}^{\log n}$ be a bijective function (Assume W.L.O.G
that $n=2^{k}$ for some $k$, otherwise add all one vectors to $A_{1}$ until
this is satisfied).

  * •

Add $2\log n$ vertices $J^{1}_{1},\dots$ and $J_{s}^{1},J_{1}^{2},\dots
J_{s}^{2}$ (assuming $s=\log n$) and label the set containing these $2s$
vertices $J$.

  * •

Add an edge from $v$ to every vertex in $J$.

  * •

For any vertex $x\in A_{1}$, add an edge between $x$ and $J^{1}_{i}$ if
$\psi(x)[i]=1$. Otherwise, add an edge between $x$ and $J^{2}_{i}$.

  * •

Add edge from every vertex in $I$ to every vertex in $J$.

See Figure 2, for graphical representation of this reduction.

We will break down the proof of correctness of the reduction into couple of
smaller statements.

######  Claim 4.2.

If there exists a pair of vertices $(x_{1},x_{2})$ in $G$ such that
$N(x_{2})\subseteq N(x_{1})$, then $x_{1}\in A_{1}$, $x_{2}\in A_{2}$.

###### Proof.

We will first show that $x_{1}$ can only be in $A_{1}$.

Notice that $x_{1}\in I$ cannot happen since every vertex $x\not\in
I\cup\\{v\\}$ is adjacent to $v$, and clearly $N(v)$ is not a subset of any
vertex in $I$. Hence, $x_{2}\in I$ is the only option, however, this is not
possible due to bijectivity of $\phi$ Marvin says: shouldn’t $\phi$ include
$I$ then? Mirza says: No, we are actually using surjectivity of $\phi$ here
and not injectivity. Fix $I^{1}_{i}$ and $I^{1}_{j}$. If
$N(I^{1}_{j})\subseteq N(I^{1}_{i})$, then for every vertex $x$ in $A_{2}\cup
D\cup\\{w\\}$ we have that $\phi(x)[j]=1\Rightarrow\phi(x)[i]=1$, but this is
clearly not the case, since there exists a vertex $x$ that maps into
$11...1011...1$ where $0$ is in $i$-th place. Similarly for $I^{1}_{i}$ and
$I^{2}_{j}$ and all other combinations of the two.. Similarly $x_{1}\neq v$,
since every other vertex is adjacent to at least one vertex in $I$.

If $x_{1}=w$, then $x_{2}\not\in A_{2}\cup D$ follows from bijectivity of
$\phi$ and construction of $I$. Furthermore, $x_{2}\not\in I$, since any
vertex in $I$ is adjacent to every other vertex in $I$ and $w$ is adjacent to
only half of the vertices in $I$. Also, for the same reason, $x_{2}\not\in
A_{1}$. Furthermore, $x_{2}\neq v$, since $v$ is adjacent to every vertex in
$A_{1}$, and $w$ is not adjacent to any of these vertices. Finally,
$x_{2}\not\in J$, for the similar reason (namely any vertex in $J$ is adjacent
to some vertex in $A_{1}$). Hence $x_{1}$ cannot be equal to $w$.

Suppose now $x_{1}\in J$. Then, $x_{2}\in J$ cannot happen, because of
bijectivity of $\psi$. $x_{2}\in A_{1}$ is not possible, since any vertex in
$A_{1}$ is adjacent to a vertex in $J$. $x_{2}\in D\cup\\{v\\}$ cannot happen,
as these vertices are adjacent to $w$. Also, $x_{2}\not\in I$ is clearly not
possible. Finally, if $x_{2}\in A_{2}$, then $x_{2}$ is not adjacent to any
vertex in $D$, and by construction, this means that $A_{2}$ contains an all
zero vector, which contradicts our assumption.

If $x_{1}\in A_{2}$, then $x_{2}\not\in D\cup\\{w\\}$ from bijectivity, and
$x_{2}\not\in A_{1}\cup I\cup J$ since any such vertex is adjacent to all
vertices in $I$. So we only have to check $x_{2}=v$, but similarly as above,
this would fail, as $v$ is adjacent to every vertex in $A_{1}$.

Finally, if $x_{1}\in D$, similar arguments show that $x_{2}\not\in
A_{2}\cup\\{w\\}\cup A_{1}\cup I\cup J$. So suppose that $x_{2}=v$, however by
our assumption $A_{1}$ contains an all $1$ vector, which is not adjacent to
any vertex in $D$ and is adjacent to $v$, hence yielding a contradiction.

Thus we conclude that the only possibility is $x_{1}\in A_{1}$.

We proceed to show that $x_{2}\in A_{2}$ is the only possibility.

Notice that $x_{2}\neq v$, since $v$ is adjacent to every vertex in $A_{2}$.
Moreover, $x_{2}\not\in D$, since every vertex in $D$ is adjacent to $w$.
Also, every vertex in $I$ is adjacent to some vertex in $A_{2}$ ( Does this
require proof? Basically follows from $|D|+1<n/2$, which is a valid
assumption), so $x_{2}\not\in I$ either. Assuming $n>2$, any vertex in $J$ is
adjacent to at least two vertices in $A_{1}$, hence $x_{2}\not\in J$ either.
Finally, assume that $x_{2}=w$. Then, since $w$ is adjacent to every vertex in
$D$, it follows that $A_{1}$ contains an all zero vector, which contradicts
our assumption and concludes the proof of this claim. ∎

######  Claim 4.3.

If there exists a pair of vertices $(x_{1},x_{2})$ in $G$ such that
$N(x_{2})\subseteq N(x_{1})$, then there exist two vectors $a_{1}\in A_{1}$
and $a_{2}\in A_{2}$ that are orthogonal.

###### Proof.

By the previous claim, we may assume that $x_{1}\in A_{1}$ and $x_{2}\in
A_{2}$.

Fix any vertex $D_{i}\in D$. Then $D_{i}$ is either adjacent to $x_{1}$, or
nonadjacent to $x_{2}$ by the assumption.

If it is adjacent to $x_{1}$, then the vector corresponding to $x_{1}$ has
$i$-th entry $0$, by construction of $A_{1}$. Similarly, if it is non-adjacent
to $x_{2}$, then the vector corresponding to $x_{2}$ has $i$-th entry $0$.
Since $i$ was arbitrary, we may conclude that the vectors corresponding to
$x_{1}$ and $x_{2}$ are orthogonal. ∎

######  Claim 4.4.

If there exists a pair of vectors $a_{1}\in A_{1}$, $a_{2}\in A_{2}$ such that
$a_{1}$ and $a_{2}$ are orthogonal, then $N(a_{2})\subseteq N(a_{1})$.

###### Proof.

It is sufficient to prove that if we fix any vertex in $N(a_{2})$, it is also
contained in $N(a_{1})$.

Let $x$ be an arbitrary vertex in $N(v_{2})$. If $x\in I$, then we are done,
since every vertex in $A_{1}$ is adjacent to any vertex in $I$. Similarly if
$x=v$.

By construction $a_{2}$ is not adjacent to $w$, nor any vertex from $A_{1}\cup
A_{2}$, so the only thing left to check is if $x\in D$.

Assume that $x=D_{i}$ for an arbitrary $i\in[d]$. Then either $a_{1}[i]=0$, or
$a_{2}[i]=0$. By construction of $G$, this means that either $a_{1}$ is
adjacent to $D_{i}$, or $a_{2}$ is non-adjacent to $D_{i}$, which is
sufficient to argue that $D_{i}\not\in N(a_{2})\setminus N(a_{1})$ and to
conclude the proof of this statement. ∎

TODO: Show that $G$ has $\tilde{\mathcal{O}}(n)$ edges. ∎

Figure 2:

Let $M=\\{m,m_{1},\dots,m_{n}\\}$ be a set of $n+1$ vertices inducing a
$K_{1,n}$. $M$ is said to be _attached_ to an $n$ element set
$S=\\{s_{1},\dots,s_{n}\\}$ if we add edges between $m_{i}$ and $s_{i}$ for
all $i\in\\{1,\dots,n\\}$ and no other edges. We will refer to such set $M$ as
_matching gadget_ of size $n$. We represent matching gadgets schematically as
shown in Figure 3.

We further define a _double matching gadget_ as follows. Double matching
gadget $M$ consists of two matching gadgets $M_{1}=\\{m^{1}_{1},\dots
m^{1}_{n}\\},M_{2}=\\{m^{2}_{1},\dots,m^{2}_{n}\\}$ with additional edge added
between $m^{1}_{i}$ and $m^{2}_{i+1}$ (defining $n+1=1$) and no other edges.
We attach a double matching gadget to a set $S=\\{s_{1},\dots,s_{n}\\}$ by
attaching both $M_{1}$ and $M_{2}$ to $S$

Figure 3: Matching gadget $M$ attached to a set $\\{A_{1},\dots,A_{n}\\}$ with
schematic representation.

We define the problem $P$ as follows.

Given: A graph $G$ with $n$ vertices.

Question: Is there a triplet of vertices $x_{1},x_{2},x_{3}\in V(G)$ such that
$N(x_{3})\subseteq N(x_{1})\cup N(x_{2})$

######  Theorem 4.5.

There exists no algorithm solving $P$ in $\mathcal{O}(n^{3-\varepsilon})$ for
any $\varepsilon>0$, unless SETH fails.

Before proving the last theorem, we first prove a few lemmas that will help us
with the proof.

######  Lemma 4.6.

Let $x_{1},x_{2},x_{3}$ be three distinct $d$-dimensional binary vectors for
$d$ sufficiently large. Let $f:\\{0,1\\}^{d}\to M_{d}(\\{0,1\\}^{2})$ be
defined as $f(x)[i,j]=x[i]x[j]$. Then there exists a pair $i,j\in d$ such that
$f(x_{1})[i,j]\not\in\\{f(x_{2})[i,j],f(x_{3})[i,j]\\}$.

###### Proof.

Observe that there exists a pair $i,j$ such that $i\neq j$, and $x_{1}[i]\neq
x_{2}[i]$ and $x_{1}[j]\neq x_{3}[j]$. If such a pair did not exist, $x_{2}$
and $x_{3}$ would both differ from $x_{1}$ in exactly one coordinate $i$, but
since $x_{2}\neq x_{3}$, then $x_{2}$ and $x_{3}$ also differ in coordinate
$i$ (since for every other coordinate $j$, we have
$x_{1}[j]=x_{2}[j]=x_{3}[j]$) and we get a contradiction.

Now we claim that $f(x_{1})[i,j]\not\in\\{f(x_{2})[i,j],f(x_{3})[i,j]\\}$.
Indeed, $f(x_{1})[i,j]$ differs from $f(x_{2})[i,j]$ in the first and from
$f(x_{3})[i,j]$ in the second coordinate. ∎

The following lemma generalizes the result from the previous one on
arbitrarily many vectors.

######  Lemma 4.7.

Let $x_{1},\dots,x_{k}$ be distinct $d$-dimensional binary vectors (assume
$d>k$). Let $f_{k}:\\{0,1\\}^{d}\to[\\{0,1\\}^{k-1}]^{d^{k-1}}$ such that
$f_{(}x)[i_{1},\dots,i_{k-1}]=x[i_{1}]x[i_{2}]\dots x[i_{k-1}]$. Then there
exist distinct indices $i_{1},\dots,i_{k-1}$, such that
$f_{k}(x_{1})[i_{1},\dots,i_{k-1}]\not\in\\{f_{k}(x_{2})[i_{1},\dots,i_{k-1}],\dots,f_{k}(x_{k})[i_{1},\dots,i_{k-1}]\\}$.

###### Proof.

We prove this statement by induction on $k$. For base case, we take $k=3$,
which was proved in the previous lemma.

Assume the statement holds for some $k\geq 3$. Let $x_{1},\dots,x_{k+1}$ be
distinct vectors. By induction hypothesis, there exist distinct indices
$i_{1},\dots,i_{k-1}$ such that
$f_{k}(x_{1})[i_{1},\dots,i_{k-1}]\not\in\\{f_{k}(x_{2})[i_{1},\dots,i_{k-1}],\dots,f_{k}(x_{k})[i_{1},\dots,i_{k-1}]\\}$.

If there exists a coordinate $i_{k}\not\in\\{i_{1},\dots,i_{k-1}\\}$ such that
$x_{k+1}[i_{k}]\neq x_{1}[i_{k}]$, we are done. So assume that for all
$j\not\in\\{i_{1},\dots,i_{k}\\}$ it holds that $x_{k+1}[j]=x_{1}[j]$.

We consider two cases. Suppose that for some $i\in\\{1,\dots,k\\}$ $x_{i}[j]$
$x_{k+1}[i_{j}]=x_{i}[i_{j}]$ for all $j\in\\{1,\dots,k-1\\}$. It is easy to
see that $i\neq 1$. But then, since $x_{i}\neq x_{k+1}$, there exists a
coordinate $j\not\in\\{i_{1},\dots,i_{k-1}\\}$ such that $x_{i}[j]\neq
x_{k+1}[j]$ and consequently $x_{i}[j]\neq x_{1}[j]$. We can conclude this
case by letting $i_{k}=j$.

On the other hand, assume that no such $i$ exists. Then since
$x_{1},\dots,x_{k+1}$ are all distinct, in particular, $x_{1}\neq x_{k+1}$,
there exists $j\in\\{1,\dots,k-1\\}$ such that $x_{1}[i_{j}]\neq x_{k+1}[j]$
and in particular $f(x_{1})[i_{1},\dots,i_{k-1}]\neq
f(x_{k+1})[i_{1},\dots,i_{k-1}]$ and
$f_{k}(x_{1})[i_{1},\dots,i_{k-1}]\not\in\\{f_{k}(x_{2})[i_{1},\dots,i_{k-1}],\dots,f_{k}(x_{k+1})[i_{1},\dots,i_{k-1}]\\}$,
so in particular, we may choose $i_{k}$ arbitrarily. ∎

Figure 4: Double matching gadget consisting of matching gadgets $M_{1}$ and
$M_{2}$ attached to a set $A$ together with schematic representation.

######  Lemma 4.8.

Let $G$ be any graph and $A$ be an independent set consisting of $n>2$ non-
isolated vertices in $G$. Let $G^{\prime}$ be obtained by attaching a double
matching gadget $M=(M_{1},M_{2})$ to set $A$ in $G$ (see Figure 4). Then for
any vertex $w\in A\cup M$, there are no two vertices $u,v\in V(G)-\\{w\\}$
such that $N(w)\subseteq N(u)\cup N(v)$.

###### Proof.

Suppose all vertices are labelled as in Figure 4 We iterate through all the
possible choices of $w$ and show that for each such a pair cannot exist.

First suppose $w=m_{1}$. Then we need to find a pair of vertices that are
adjacent to all $n$ pendant vertices in $G^{\prime}[M_{1}]$. However, by
construction, each vertex in $G^{\prime}-\\{m_{1}\\}$ is adjacent to at most
one vertex in $M_{1}$, and since $n>2$, such a pair does not exist.

Now assume that $w=m^{1}_{1}$ (W.L.O.G). Now, since $w$ is adjacent to
$m_{1}$, one of the $u$, or $v$ needs to be in $M_{1}$. Without loss of
generality, say $u$ is in $M_{1}$. Now, since no vertex in $M_{1}$ other than
$m_{1}^{1}$ is adjacent to $A_{2}$, nor $m_{2}^{2}$, $v$ has to be adjacent to
both of these vertices. However, as $A$ is an independent set, and no vertex
from $M$ other than $m^{1}_{1}$ and $m^{2}_{1}$ are adjacent to $A_{2}$, it is
easy to see that $N(A_{2})\cap N(m^{2}_{2})-\\{m^{1}_{1}\\}=\emptyset$.

Hence $w\not\in M_{1}$ and by symmetry, it is also not in $M_{2}$. Thus, the
only case left to verify is $w\in A$.

Without loss of generality, we may assume that $w=A_{1}$ (otherwise the proof
is completely symmetric). Since $A_{1}$ is non-isolated vertex in $G$ and
furthermore, $A$ is independent, $A_{1}$ has a neighbour in $G-A$. Since no
vertex in $M$ is adjacent to a vertex in $G-A$, we can conclude that $u\in
V(G)$ (W.L.O.G.). However, as no vertex in $G$ other than $A_{1}$ is adjacent
to $m^{1}_{1}$, nor $m^{2}_{1}$, $v$ has to be adjacent to both of these
vertices. It is an easy observation that no such vertex $v$ other than $A_{1}$
exists.

We have thus shown that for no choice of $w$ does there exist a pair $u,v$
satisfying the asserted relationship, as desired. ∎

###### Proof (of Theorem 4.5)..

We reduce from $3$-orthogonal vectors. Let $A_{1},A_{2},A_{3}$ be the sets
consisting of $n$ binary $d$-dimensional vectors each.

We may assume that $A_{3}$ contains no vectors of weight at most $1$, since we
may add two dimensions and set the value of every vector in $A_{3}$ to $1$ and
the value of every vector in $A_{1}\cup A_{2}$ to $0$ at the two added
dimensions.

We assume W.L.O.G. that $n=2^{\ell}-2$ for some $\ell$, otherwise, add at most
$n-1$ all one vectors to each set $A_{i}$. Let
$\phi:A_{3}\to\\{0,1\\}^{\log(n+2)}\setminus\\{00\dots 0,11\dots 1\\}$ be a
bijection and let $f$ be defined as in Lemma 4.6. Finally, define
$\psi=f\circ\phi$.

Let $G$ be a graph constructed as follows.

  * •

Start with an empty graph.

  * •

For each vector in $A_{i}$ add a vertex $a^{i}_{j}$ ($j\in\\{1,\dots,n\\}$)
corresponding to this vector.

  * •

Add $d$ vertices $D_{1},\dots,D_{d}$ corresponding to the dimensions of
vectors in $A_{i}$. Add an edge between $a^{1}_{i}$ and $D_{j}$ if the vector
corresponding to $a^{1}_{i}$ has $j$-th coordinate equal to $0$ (i.e.
$a^{1}_{i}[j]=0$). Similarly for $a^{2}_{i}$. Finally add an edge between
$a^{3}_{i}$ and $D_{j}$ if $a^{3}_{i}[j]=1$.

  * •

Attach a double matching gadget $M_{1}$ to the set $A_{1}\cup A_{2}$.

  * •

Attach a double matching gadget $M_{2}$ to the set $D$.

  * •

For each $i\neq j\in\\{1,\dots,\log(n+2)\\}$ add $4$ vertices
$s_{ij}^{00},s_{ij}^{01},s_{ij}^{10},s_{ij}^{11}$, each quadruplet forming a
clique.

  * •

For each vertex $x\in A_{3}$ add an edge between $x$ and $s_{ij}^{00}$ if and
only if $\psi(x)[i,j]=00$. Similarly for $s_{ij}^{01}$, $s_{ij}^{10}$,
$s_{ij}^{11}$.

  * •

If $i<j$, add all edges between vertices in $A_{1}$ and vertices
$\\{s_{ij}^{00},s_{ij}^{01},s_{ij}^{10},s_{ij}^{11}\\}$, otherwise add all
edges between vertices in $A_{2}$ and vertices
$\\{s_{ij}^{00},s_{ij}^{01},s_{ij}^{10},s_{ij}^{11}\\}$.

  * •

Add $4$ vertices $s_{00},s_{01},s_{10},s_{11}$ and add all edges between
$s_{00}$ and $s_{ij}^{00}$ for all $i,j$, and similarly for the remaining
three vertices.

  * •

Finally, attach a double matching $M_{3}$ to the set
$\\{s_{00},s_{01},s_{10},s_{11}\\}$.

The obtained graph is depicted in Figure 5. For the rest of the proof,
whenever we mention graph $G$, we will refer to the graph constructed above.

######  Claim 4.9.

If $G$ contains three distinct vertices $x_{1},x_{2},x_{3}$ such that
$N(x_{3})\subseteq N(x_{1})\cup N(x_{2})$, then $x_{3}\in A_{3}$.

###### Proof.

We observe that double matching gadget $M_{1}$ is attached to the independent
set $A_{1}\cup A_{2}$, hence by Lemma 4.8, $x_{3}$ cannot be in $A_{1}\cup
A_{2}\cup M_{1}$. Similarly, $x_{3}$ cannot be in $D\cup M_{2}$ and
$\\{s_{00},s_{01},s_{10},s_{11}\cup M_{3}\\}$.

Hence, we only need to argue that $x_{3}$ cannot be in $S$.

Assume for contradiction that such $x_{3}\in S$ exists. Without loss of
generality, assume that $x_{3}=s^{00}_{ij}$ for some $i,j$ and assume it is
adjacent to each vertex in $A_{1}$ (if on the other hand it is adjacent to
$A_{2}$, the argument is completely symmetric).

Since $x_{3}$ is adjacent to $s_{00}$, we may assume that $x_{1}$ is also
adjacent to $s_{00}$. However, notice that $s^{00}_{ij}$ is the only vertex
adjacent to both $s_{00}$ and $s^{01}_{ij}$. Hence, we may assume that $x_{2}$
is adjacent to $s^{01}_{ij}$ and we consider four possibilities.

Either $x_{2}\in S$, or $x_{2}=s_{01}$, or $x_{2}\in A_{3}$, or $x_{2}\in
A_{1}$.

If $x_{2}=s_{01}$, or $x_{2}\in A_{3}$, then clearly, neither $x_{1}$, nor
$x_{2}$ are adjacent to $s^{10}_{ij}$.

On the other hand if $x_{2}\in S$, then
$x_{2}\in\\{s_{ij}^{01},s_{ij}^{10},s_{ij}^{11}\\}$, since $s^{01}_{ij}$ is in
the closed neighbourhood of $x_{2}$. We claim there exists a vertex in $A_{3}$
that is adjacent to $x_{3}$, but not adjacent to $x_{1}$, nor $x_{2}$.

Indeed, since $\phi$ is a bijective function, take $v\in A_{3}$ such that
$\phi(v)=11\dots 1011\dots 1011\dots 1$, where two zeros are in $i$-th and
$j$-th coordinate. This vertex is clearly adjacent to $s_{ij}^{00}$, but for
all $(i^{\prime},j^{\prime})\neq(i,j)$, it is not adjacent to
$s_{i^{\prime}j^{\prime}}^{00}$, in particular, it is non-adjacent to $x_{1}$.
Moreover, for any $(i,j)$, any vertex from $A_{3}$ is adjacent to exactly one
of the elements in $\\{s_{ij}^{01},s_{ij}^{10},s_{ij}^{11}\\}$, thus $v$ is
non-adjacent to $x_{2}$ as desired.

Finally, consider $x_{2}\in A_{1}$. Again, since $x_{2}$ is not adjacent to
any vertex in $A_{3}$, choosing the same vertex $v$ as above yields a
contradiction.

Thus, we exhausted all choices for $x_{1}$ and $x_{2}$ and may conclude that
$x_{3}$ cannot be in $S$. In particular, if a triplet $x_{1},x_{2},x_{3}$
exists such that $N(x_{3})\subseteq N(x_{1})\cup N(x_{2})$, then $x_{3}\in
A_{3}$. ∎

######  Claim 4.10.

If $G$ contains three distinct vertices $x_{1},x_{2},x_{3}$ such that
$N(x_{3})\subseteq N(x_{1})\cup N(x_{2})$, then $x_{1}\not\in A_{3}$.

###### Proof.

By the previous claim, we have that $x_{3}\in A_{3}$. We observe that, by the
result of Lemma 4.6, at least one of the $x_{1}$ or $x_{2}$ must be outside
$A_{3}$.

For contradiction, assume $x_{1}\in A_{3}$ and $x_{2}\not\in A_{3}$.

Since $\phi$ is an injective function,
$\phi(x^{\prime}_{1})\neq\phi(x^{\prime}_{3})$, in particular, fix $i$ such
that $\phi(x^{\prime}_{1})[i]\neq\phi(x^{\prime}_{3})[i]$.

Let $j$ be an arbitrary coordinate and without loss of generality, assume
$j>i$. Clearly, $\psi(x_{3})[i,j]\neq\psi(x_{1})[i,j]$ and
$\psi(x_{3})[j,i]\neq\psi(x_{1})[j,i]$, hence for some
$b_{1},b_{2}\in\\{0,1\\}$ $x_{3}$ is adjacent to $s_{ij}^{b_{1}b_{2}}$ and
$s_{ji}^{b_{2}b_{1}}$ and $x_{1}$ is non-adjacent to both.

In particular, we need to choose $x_{2}$ that is adjacent to both
$s_{ij}^{b_{1}b_{2}}$ and $s_{ji}^{b_{2}b_{1}}$. Clearly, the only choice for
$x_{2}$ is $s_{b_{1}b_{2}}$.

However, if we chose $j$ such that
$\phi(x^{\prime}_{3})[i]\neq\phi(x^{\prime}_{3})[j]$, then $b_{1}\neq b_{2}$
and in particular $s_{b_{1}b_{2}}\neq s_{b_{2}b_{1}}$ and hence no vertex is
adjacent to both $s_{ij}^{b_{1}b_{2}}$ and $s_{ji}^{b_{2}b_{1}}$. Notice that
such choice of $j$ always exists, since $00\dots 0$ and $11\dots 1$ are not in
the codomain of $\phi$. ∎

######  Claim 4.11.

If $G$ contains three distinct vertices
$x^{\prime}_{1},x^{\prime}_{2},x^{\prime}_{3}$ such that
$N(x^{\prime}_{3})\subseteq N(x^{\prime}_{1})\cup N(x^{\prime}_{2})$, then
there exist vertices $x_{1}\in A_{1},x_{2}\in A_{2},x_{3}\in A_{3}$ such that
$N(x_{3})\subseteq N(x_{1})\cup N(x_{2})$.

###### Proof.

Suppose that $G$ contains three vertices
$x^{\prime}_{1},x^{\prime}_{2},x^{\prime}_{3}$ satisfying the desired
relation. Then, by the claim above, $x^{\prime}_{3}\in A_{3}$, so we set
$x_{3}=x^{\prime}_{3}$.

Also, without loss of generality, we may assume that $x^{\prime}_{1}$ and
$x^{\prime}_{2}$ are not in $M_{1}$, nor $M_{3}$, since $N[M_{1}]\cup
N[M_{3}]$ are disjoint to $N[A_{3}]$.

We proceed to show that either $x_{1}^{\prime}$, or $x_{2}^{\prime}$ must be
in $A_{1}\cup A_{2}$.

By the previous claim, $x_{1}^{\prime}\not\in A_{3}$ and symmetrically,
$x^{\prime}_{2}\not\in A_{3}$. Now observe that each vertex in $A_{3}$ has at
least two neighbours in $D$ (by the assumption), hence either both
$x^{\prime}_{1}$ and $x^{\prime}_{2}$ are in $D\cup M_{2}$, which clearly
cannot happen, since no vertex in $D\cup M_{2}$ is adjacent to any vertex in
$S$, or one of the $x^{\prime}_{1}$ or $x^{\prime}_{2}$ are in $A_{1}\cup
A_{2}$ as desired.

Without loss of generality, assume $x_{1}^{\prime}\in A_{1}$ and fix
$x_{1}=x^{\prime}_{1}$. Now assume that $x^{\prime}_{2}$ is not in $A_{2}$.
Then since $x^{\prime}_{1}$ is only adjacent to half of the vertices in
$N(x_{3})\cap S$, $x^{\prime}_{2}$ must be adjacent to the other half.

The only possible choice of such $x^{\prime}_{2}$ outside $A_{2}$ is
$x^{\prime}_{2}\subseteq\\{s_{00},s_{01},s_{10},s_{11}\\}$.

Assume that (without loss of generality) $x^{\prime}_{2}=s_{00}$. Then, since
$N(x_{3})\subseteq N(x_{1})\cup N(x^{\prime}_{2})$ and $x^{\prime}_{2}$ is not
adjacent to any vertex in $D$, we have that $N(x_{3})\cap D\subseteq
N(x_{1})\cap D$.

Fix an arbitrary vertex in $A_{2}$, say $a^{2}_{1}$. We claim that setting
$x_{2}=a^{2}_{1}$ satisfies the desired relation.

To see this, fix any vertex $x$ in $N(x_{3})$. Clearly, $x\in S\cup D$. If
$x\in D$, then by the last observation, $x\in N(x_{1})$. Otherwise, if $x\in
S$, then it is either adjacent to entire $A_{1}$, or entire $A_{2}$, hence,
since $x_{1}\in A_{1}$ and $x_{2}\in A_{2}$, we obtain the desired result. ∎

We conclude this proof by showing that $G$ contains three distinct vertices
$x_{1},x_{2},x_{3}$ such that $N(x_{3})\subseteq N(x_{1})\cup N(x_{2})$ if and
only if there exists a triplet of vectors $a_{1}\in A_{1},a_{2}\in
A_{2},a_{3}\in A_{3}$ such that in each coordinate $i$, $a_{1}[i]\cdot
a_{2}[i]\cdot a_{3}[i]=0$.

Assume first that $G$ contains three distinct vertices $x_{1},x_{2},x_{3}$
such that $N(x_{3})\subseteq N(x_{1})\cup N(x_{2})$. Then, as proved above, we
can assume that $x_{1}\in A_{1},x_{2}\in A_{2},x_{3}\in A_{3}$. Then for every
vertex $D_{i}\in D$, either $x_{3}$ is non-adjacent to this vertex, hence
$x_{3}[i]=0$, or one of the vertices $x_{1},x_{2}$ is adjacent to $D_{i}$,
that is $x_{1}[i]=0$, or $x_{2}[i]=0$. Therefore, choosing vectors
corresponding to vertices $x_{1},x_{2},x_{3}$ satisfies the OV instance.

Conversely, assume that there are vectors $a_{1}\in A_{1},a_{2}\in
A_{2},a_{3}\in A_{3}$ such that in each coordinate $i$, $a_{1}[i]\cdot
a_{2}[i]\cdot a_{3}[i]=0$.

Consider vertices corresponding to vectors $a_{1},a_{2},a_{3}$. By
construction, for each vertex $D_{i}$, either there is no edge from $a_{3}$ to
$D_{i}$ (if $a_{3}[i]=0$), or $a_{1}[i]\cdot a_{2}[i]=0$, in which case there
is an edge from either $a_{1}$ to $D_{i}$, or from $a_{2}$ to $D_{i}$. This
shows that $N(a_{3})\cap D\subseteq N(a_{1})\cup N(a_{2})$.

Finally, we notice that the only vertices adjacent to $a_{3}$ that are not in
$D$ are in $S$. However, by construction $a_{1}$ and $a_{2}$ dominate $S$, so
we obtain the desired result.

∎

Figure 5: Graph construction as described in the proof of Theorem 4.5

.

######  Lemma 4.12.

Let $G$ be a graph and $S\subseteq V(G)$ be an independent set of non-isolated
vertices. Let $G^{\prime}$ be obtained from $G$ by attaching $k$ matching
gadgets $M_{1},\dots,M_{k}$ to $S$ and by matching all the gadgets to one
another (any pendant vertex in a matching $M_{i}$ is adjacent to exactly one
pendant vertex in $M_{j}$ for all $j\neq i$). If
$H=G^{\prime}[M_{1}\cup\dots\cup M_{k}\cup S]$ is $(K_{3},C_{4})$-free, then
for any $u\in V(H)$, there exist no $k$ vertices $v_{1},\dots,v_{k}\in
V(G^{\prime})\setminus\\{u\\}$ such that $N(u)\subseteq N(v_{1})\cup\dots\cup
N(v_{k})$.

###### Proof.

We will show that for different choices of $u$ we cannot find vertices
$v_{1},\dots,v_{k}$ satisfying the desired relation.

Assume first $u\in S$. Vertex $u$ is adjacent to $k$ vertices $m_{1}\in
M_{1},\dots m_{k}\in M_{k}$ in $H$. Now, by assumption that $H$ is
$(K_{3},C_{4})$-free, no pair $m_{i},m_{j}$ has a common neighbour other than
$u$ and furthermore, there is no edge between $m_{i}$ and $m_{j}$. Hence, we
need $k$ distinct vertices $v_{1},\dots,v_{k}$ to cover $m_{1},\dots,m_{k}$
and moreover, observe that $v_{1},\dots,v_{k}$ must all be in $H$. However, by
assumption that the vertex $u$ is not isolated in $G$, there is a vertex $w\in
N(u)\setminus\\{m_{1},\dots,m_{k}\\}$ and by assumption that $S$ was an
independent set, we can conclude that $w\in G-H$.

Now since each $m_{i}$ is only adjacent to $u$ in $S$, no $v_{i}$ can be in
$S$. In particular, this shows that no $v_{i}$ is adjacent to $w$ concluding
the case when $u\in S$.

Assume now $u\in M_{1}$ (without loss of generality) and $u$ is a pendant
vertex of $M_{1}$. By construction, $u$ is adjacent to exactly one pendant
vertex from each of the remaining $k-1$ matchings ($M_{2},\dots,M_{k}$),
exactly one vertex from $S$ and the root vertex from $M_{1}$.

Notice that all the vertices in $N(u)$ lie in $H$ and since $H$ is
$(K_{3},C_{4})$-free, they do not have a common neighbour and hence, one
requires $k+1$ vertices to cover them.

Finally, assume $u\in M_{1}$ and $u$ is the root of $M_{1}$. Now $N(u)$
consists of all the pendant vertices in $M_{1}$, which form an independent set
and have no common neighbours (besides $u$), hence we need $n$ vertices to
cover them. ∎

######  Lemma 4.13.

Let $S$ be a set of $n=4\ell$ vertices (for some positive integer $\ell$) and
$M_{1},\dots,M_{k}$ be the matching gadgets of the same size. Let each vertex
in $S$ correspond to a distinct element of $\mathbb{Z}_{n}$ and similarly, let
all pendant vertices in every matching correspond to distinct element of
$\mathbb{Z}_{n}$. Linearly order the sets $S,M_{1},\dots M_{k}$ such that
$S\prec M_{1}\prec M_{2}\prec\dots\prec M_{k}$. For every
$x\in\mathbb{Z}_{n}$, add an edge between the vertex corresponding to $x$ in
$S$ and the vertex corresponding to $(x+1)\in\mathbb{Z}_{n}$ in $M_{i}$ for
all $1\leq i\leq k$. Furthermore, for all $i<j$, add an edge between the
vertex corresponding to $x$ in $M_{i}$ and the vertex corresponding to
$x+4i+1$ in $M_{j}$ for all $x\in\mathbb{Z}_{n}$. No other edges are added to
this construction. For sufficiently large $n$ (e.g. $n>16k$) this construction
satisfies the following conditions:

  * •

Every vertex in $S$ is adjacent to exactly one vertex in $M_{i}$ for every $i$
and every vertex in $M_{i}$ is adjacent to exactly one vertex in $M_{j}$ for
every $j\neq i$.

  * •

The obtained graph is $(K_{3},C_{4})$-free.

###### Proof.

We begin by proving the first claim. Observe that it is sufficient to prove
that $\phi:\mathbb{Z}_{n}\to\mathbb{Z}_{n}$ defined as $\phi(x)=4i+1$ is a
bijection for every $0\leq i\leq k-1$.

Since the domain and codomain are finite and have the same cardinality, it is
enough to argue injectiveness of $\phi$.

Suppose that for some $i$ there exists a pair $a,b\in\mathbb{Z}_{n}$ such that
$\phi(a)=\phi(b)\iff a+4i+1=b+4i+1$. Now, either $a=b$, or $4i+1=0$. We
conclude the first part of the proof by observing that $4i+1$ cannot be zero,
by assumption that $n=4\ell$.

For the second part, we first argue that if a $K_{3}$, or a $C_{4}$ exist,
they cannot contain two distinct vertices from the same set. Since all the
sets are independent, clearly no $K_{3}$ can contain two vertices from the
same set. Therefore, it is sufficient to verify that no two vertices from the
same set have two common neighbours.

Let $a,b\in S$ correspond to $x,y\in\mathbb{Z}_{n}$ respectively. By
construction, they contain a common neighbour if and only if $x+1=y+1$, i.e.
if and only if $x=y$, which is equivalent to $a=b$.

Similarly in $M_{i}$ any pair of vertices $a,b$, corresponding to
$x,y\in\mathbb{Z}_{n}$ has one common neighbour (the root of the matching) and
has two common neighbours if and only if $x+4i+1=y+4i+1$, or $x-4j-1=y-4j-1$
for some $j<i$. By the parity argument of $n$, both statements are equivalent
to $x=y$ and $a=b$.

Hence, if a triangle of a $C_{4}$ exist, all the vertices inducing them are
contained in different sets.

We observe that a triangle (resp. 4-cycle) exists and consists of vertices
$a\in A,b\in B,c\in C$ ($d\in D$) with $A\prec B\prec C$ ($\prec D$) if and
only if there exists a triangle (4-cycle) $a^{\prime}\in A,b^{\prime}\in
B,c^{\prime}\in C$ ($d^{\prime}\in D$) with $a^{\prime}$ corresponding to
$0\in\mathbb{Z}_{n}$

Thus, we consider without loss of generality the case when the cycle contains
a vertex corresponding to a zero element of $\mathbb{Z}_{n}$ in the smallest
set in our linear ordering.

Assume that there exists a triangle induced by vertices $a\in A,b\in B,c\in
C$, following the conventions from above ($a$ corresponds to $0$ and $A\prec
B\prec C$). And let $b$ correspond to $x$ and $c$ correspond to $y$ in
$\mathbb{Z}_{n}$. Then since $a$ is adjacent to $b$ and $A\prec B$, it follows
that $x\equiv 1\mod 4$, and since $b$ is adjacent to $c$ and $B\prec C$, it
follows that $y\equiv x+1\equiv 2\mod 4$ and finally, since $a$ is adjacent to
$C$ and $A\prec C$, we have that $y\equiv 1\mod 4$, yielding a contradiction.

Hence our construction does not introduce triangles. We only have to verify
that there are also no $C_{4}$’s.

Assume there is a $C_{4}$ $a,b,c,d$ as denoted above and orient the edges in
such a way that $a,b,c,d$ induce a directed cycle as well.

Starting in $a$, if three out of four edges are directed forward in our linear
ordering of sets, the same parity argument as above can be used to show that
such a $4$-cycle does not exist. Similarly if three edges are directed
backwards.

Hence, the only way to construct a valid $4$-cycle would be to go forward
twice and backwards twice in our linear ordering. In other words we have
either $a\sim b\sim d\sim c\sim a$, or $a\sim c\sim b\sim d\sim a$ (Mirza
says: I think these are the only two valid options, but we might also delete
this remark, as we don’t use it).

Let $e_{1},e_{2},e_{3},e_{4}$ be the arcs of the $C_{4}$ induced by $a,b,c,d$.
Let $s_{i}$ be $1$ if $e_{i}$ is directed forwards in the linear ordering and
$-1$ otherwise. Let $e_{j}=(x,y)$ with $x\in X$, $y\in Y$. Then $w_{j}:=4i+1$
where $i$ is the minimum of the index of the set $X$ and the index of the set
$Y$ in the linear ordering (the index of $S$ is $0$ and the index of $M_{i}$
is $i$). Finally, let the weight of the arc $e_{i}$ be $w(e_{i})=s_{i}\cdot
w_{i}$.

Clearly, $a,b,c,d$ induce a $C_{4}$ Mirza says: Note: To use the word induce
here, we need triangle-freeness, which we proved above if and only if
$\sum_{i=1}^{4}w(e_{i})=0$.

Without loss of generality assume that $e_{1}$ and $e_{4}$ are the arcs
containing $a$ as an endpoint. By assumption that $A\prec B\prec C\prec D$, we
have that $w(e_{1})=-w(e_{4})$, that is $\sum_{i=1}^{4}w(e_{i})=0$ if and only
if $w(e_{2})=-w(e_{3})$.

However, this contradicts our assumption that $A,B,C,D$ are pairwise distinct.
∎

###  4.1 On the intersection gadgets and more…

Given a set $S$ with $n$ elements, let $\phi:S\to\\{0,1\\}^{\log(n)}$ be an
injective function called the _identifier_ of $S$.

For some integer $d$, let

$f:\\{0,1\\}^{d}\to M_{d}(\\{0,1\\}^{2})$

be defined as $f(x)[i,j]=(\overline{x[i]},\overline{x[j]})$.

Let

$T=\\{(x,i,j,b_{1},b_{2})\mid x\in S;\;i,j\in[\log(n)];\;i\neq
j;\;b_{1},b_{2}\in\\{0,1\\}\;(b_{1},b_{2})\neq(f\circ\phi)(x)[i,j])\\}.$

######  Lemma 4.14.

Let $\phi,f,S,T$ be as defined above. Then, for every triplet
$x_{1},x_{2},x_{3}\in S$ there exists $i,j,b_{1},b_{2}$ such that
$(x_{1},i,j,b_{1},b_{2})\in T$, $(x_{2},i,j,b_{1},b_{2})\in T$ and
$(x_{3},i,j,b_{1},b_{2})\not\in T$.

###### Proof.

Fix a triplet $x_{1},x_{2},x_{3}$ of distinct elements from $S$ arbitrarily.
Using injectivity of $\phi$, there exists an $i$ such that
$\phi(x_{1})[i]\neq\phi(x_{3})[i]$ and a $j$ such that
$\phi(x_{2})[j]\neq\phi(x_{3})[j]$.

Furthermore, we may assume $i\neq j$. Note that if there exists no such
distinct pair, one may argue that $\phi(x_{1})=\phi(x_{2})$, contradicting the
injectivity of $\phi$.

Let $b_{1}=\phi(x_{1})[i]$ and $b_{2}=\phi(x_{2})[j]$.

We claim that $(x_{1},i,j,b_{1},b_{2})$ and $(x_{2},i,j,b_{1},b_{2})$ are both
in $T$, whereas $(x_{3},i,j,b_{1},b_{2})$ is not.

To see the this, observe that $b_{1}=\overline{\phi(x_{3})[i]}$ and
$b_{2}=\overline{\phi(x_{3})[j]}$, i.e.
$(b_{1},b_{2})=(f\circ\phi)(x_{3})[i,j]$, hence showing the latter. Similarly
$b_{1}=\phi(x_{1})[i]$; $b_{2}=\phi(x_{2})[j]$, hence
$(b_{1},b_{2})\neq(f\circ\phi)(x_{1})[i,j]$ and
$(b_{1},b_{2})\neq(f\circ\phi)(x_{2})[i,j]$ as desired. ∎

Let $G$ be any graph and $A\subseteq V(G)$ with $|A|=c>1$. Let $G^{\prime}$ be
obtained from $G$ as follows

  * •

For all distinct pairs $i,j\in\lceil\log(|c|)+1\rceil$ add 4 vertices, each
corresponding to a pair of bits $b_{1},b_{2}$.

  * •

Let $I:=V(G^{\prime})\setminus V(G)$ and $S:=A\cup I$.

  * •

Let $\lceil\log(|c|)+1\rceil=t$ and $\phi$ be an injective function from $S$
to $\\{0,1\\}^{t}$ with $\phi(x)[t]=0$ if and only if $x\in I$, otherwise $1$.
Furthermore, for any $x\in I$, if $x$ corresponds to $(i,j,b_{1},b_{2})$, let
$\phi(x)[i]=\overline{b_{1}}$ and $\phi(x)[j]=\overline{b_{2}}$.

  * •

Let $f,T$ be as defined above, and let $E(G[S])$ be as follows. For all $x\in
S$, add an edge between $x$ and a vertex corresponding to $(i,j,b_{1},b_{2})$
if and only if $(x,i,j,b_{1},b_{2})\in T$. Note that this construction results
in a simple graph (no loops).

######  Lemma 4.15.

Let $G$ be any graph and $A\subseteq V(G)$ and let $G^{\prime}$ be constructed
as above. Then for any pair $x_{1},x_{2}\in S$ and $x_{3}$ in $V(G^{\prime})$
there exists a vertex $y$ such that $y\in N(x_{1})\cap N(x_{2})$ and $y\not\in
N(x_{3})$

###### Proof.

Select $x_{1},x_{2}\in S$ arbitrarily. If $x_{3}\in V(G^{\prime})\setminus S$,
then this property is trivially satisfied (e.g. take the vertex in $I$ that
corresponds to $1,2,\phi(x_{1})[1],\phi(x_{2})[2]$. It is clearly adjacent to
both $x_{1},x_{2}$ and by construction there are no edges between $I$ and
$V(G^{\prime})\setminus S$).

Thus, we may assume that $x_{3}\in S$ and we may apply Lemma 4.14 to find a
vertex $y\in I$ adjacent to both $x_{1}$ and $x_{2}$, but not to $x_{3}$. We
only have to observe that by construction of $\phi$ above, $y\not\in
x_{1},x_{2}$ and if $y=x_{3}$, then we may select a different $y$ by simply
swapping $i$ and $j$. ∎

Given a graph $G$, and a subset $A$, the set $I$ as above is called
_intersection gadget_ and if we add the edges between $A$ and $I$ as above to
obtain graph $G^{\prime}$, we will use the term _attaching the intersection
gadget_ to $A$. Schematically we will represent this as a parallelogram $I$
connected to set $A$ by a directed edge from $I$ to $A$ as shown on Figure 6.

Figure 6: Schematic representation of the intersection gadget.

Given three sets consisting of $n$ $d$-dimensional binary vectors
$A_{1},A_{2},A_{3}$, construct the graph $G$ as follows.

  * •

Start with a vertex set $V(G)=A_{1}\cup A_{2}\cup A_{3}\cup D$, where $D$ is a
set consisting of $d$ elements, one corresponding to each dimension of vectors
in $A_{i}$.

  * •

For any vertex $x$ corresponding to a vector in $A_{1}$ or $A_{2}$, add an
edge between $x$ and a vertex $D_{i}$, corresponding to the $i$-th dimension,
if and only if $x[i]=1$.

  * •

For any vertex $x$ corresponding to a vector in $A_{3}$, add an edge between
$x$ and the vertex $D_{i}$ if and only if $x[i]=0$.

  * •

Attach an intersection gadget $I_{1}$ to $A_{1}\cup A_{3}$.

  * •

Add all the edges between $D$ and $I_{1}$

  * •

Attach an intersection gadget $I_{2}$ to $A_{2}\cup A_{3}$.

  * •

Add all the edges between $D$ and $I_{2}$

  * •

Attach an intersection gadget $I$ to $A_{1}\cup A_{2}\cup D\cup I_{1}\cup
I_{2}$.

  * •

Add all edges between $A_{3}$ and $I$.

  * •

Linearly order the vertices in $A_{3}$ and add all the edges between first
$k=\mathcal{O}(1)$ vertices in $A_{3}$ and all vertices in $A_{1}$ and all the
edges between second $k$ vertices in $A_{3}$ and all the vertices in $A_{2}$.

  * •

Add $n$ edges between the vertices in $A_{3}$ such that $A_{3}$ induces a
cycle in $G$. (ad hoc patch to a corner case $x_{1}\in I,x_{2},x_{3}\in
A_{3}$; to be replaced with something nicer)

Such a construction is depicted on Figure 7.

Figure 7: Construction of the graph $G$.

######  Theorem 4.16.

) Given the sets of $d$-dimensional binary vectors $A_{1},A_{2},A_{3}$
construct a graph $G$ as above. There exists a triplet $x_{1},x_{2},x_{3}\in
V(G)$ such that $N(x_{1})\cap N(x_{2})\subseteq N(x_{3})$ if and only if there
exists a triplet of orthogonal vectors $y_{1},y_{2},y_{3}$.

Before we prove this theorem, we first have to make a few reasonable
assumptions about the input vectors and the selection of function $\phi$ in
the construction of some intersection gadgets.

######  Assumption 4.17.

Both $A_{1}$ and $A_{2}$ contain an all $1$ vector.

If this assumption is not satisfied in the original input, we may simply add
an all $1$ vector to $A_{1}$ and $A_{2}$ and clearly such a modification of
the input set will not affect the outcome of the orthogonal vector instance.

######  Assumption 4.18.

There exists a coordinate $i$ such that every vector in $A_{1}$ and every
vector in $A_{3}$ has $i$-th entry equal to $1$ and every non-all-one vector
in $A_{2}$ has $i$-th entry equal to $0$.

Symmetrically, there exists a coordinate $j$ such that every vector in $A_{2}$
and every vector in $A_{3}$ has $j$-th entry equal to $1$ and every non-all-
one vector in $A_{1}$ has $j$-th entry equal to $0$.

######  Assumption 4.19.

For every coordinate $j\in D$, there exists at least $k$ vectors
$x_{1},\dots,x_{k}$ in $A_{3}$ such that $x_{i}[j]=0$.

If this assumption is not satisfied in the original input, we may always add
the $\log(n)$ vectors $01\dots 1,101\dots 1,\cdots,11\dots 10$ $k$ times, and
to make sure that these vectors are not used in the solution, we add one
additional dimension $d+1$ to $D$ and for every $x\in A_{1}\cup A_{2}$ set
$x[d+1]=1$ and similarly for all the $k\log n$ added vectors. Finally, for all
$x$ originally in $A_{3}$, set $x[d+1]=0$. Observe that this construction
preserves the assumption (also for $d+1$), whilst making sure that the new
vectors are not used in the solution.

######  Assumption 4.20.

Every vertex in the intersection gadgets $I_{1}$ and $I_{2}$ has at least $k$
neighbours in $A_{3}$.

This can be controlled by choosing the identifier function $\phi$ carefully in
the construction of the intersection gadget. Namely, let $t$ be $\log$ of the
codomain of $\phi$ in construction of $I_{1}$. Then we can take $2k\cdot
t\in\mathcal{O}(\log(n))$ vertices in $A_{3}$ $x_{1},\dots,x_{2kt}$ and let
for each $i\in[t]$, set the $i$-th coordinate of
$\phi(x_{(i-1)k+1}),\dots,\phi(x_{ik})$ to $1$ and similarly for each
$i\in\\{t+1,\dots,2kt\\}$, set the $i$-th coordinate of
$\phi(x_{t+1+(i-1)k}),\dots,\phi(x_{t+1+ik})$ to $0$.

Remaining coordinates are set arbitrarily to preserve the desired properties
of $\phi$.

It is now obvious that the vertex in $I_{1}$ corresponding to the tuple
$(i,j,b_{1},b_{2})$ (assuming w.l.o.g. $b_{1}=1$) will be adjacent to all the
vertices $x_{(i-1)k+1},\dots,x_{ik}$ in $A_{3}$.

We repeat the similar process when constructing $I_{2}$.

We now proceed to prove a few lemmas that will be useful in proving the last
theorem.

######  Lemma 4.21.

Given the sets of $d$-dimensional binary vectors $A_{1},A_{2},A_{3}$ construct
a graph $G$ as above. If there exists a triplet $x_{1},x_{2},x_{3}$ such that
$N(x_{1})\cap N(x_{2})\subseteq N(x_{3})$, then $x_{3}\in A_{3}$.

###### Proof.

Assume that there exists such a triplet and for contradiction assume
$x_{3}\not\in A_{3}$.

Consider first the case when $\\{x_{1},x_{2},x_{3}\\}\cap A_{3}=\emptyset$.
Then $x_{1},x_{2},x_{3}\in A_{1}\cup A_{2}\cup I_{1}\cup I_{2}\cup I\cup D$.
But notice that $I$ is attached to all these sets (excluding itself), and the
existence of such triplet contradicts the Lemma 4.15. Hence, either $x_{1}$,
or $x_{2}$ are in $A_{3}$.

Consider now the case when both $x_{1}$ and $x_{2}$ are in $A_{3}$. Clearly
$I\subseteq N(x_{1})\cap N(x_{2})$ and by construction of $G$, no vertex
outside $A_{3}$ is adjacent to every vertex in $I$, so we reach a
contradiction in this case as well.

Finally, consider the case when exactly one of the $x_{1},x_{2}$ is in $A_{3}$
and w.l.o.g. assume $x_{1}\in A_{3}$, $x_{2}\not\in A_{3}$. Again, using that
$I\subseteq N(x_{1})$, this is possible only if there exists a vertex $x_{3}$
such that $N(x_{2})\cap I\subseteq N(x_{3})\cap I$, but this clearly
contradicts the injectivity of $\phi$ in the construction of the intersection
gadget $I$ [assume for some $i$ (w.l.o.g $i>1$)
$\phi(x_{2})[i]\neq\phi(x_{3})[i]$, and take the vertex in $I$ corresponding
to $(i,1,\phi(x_{2})[i],\overline{\phi(x_{3})[1]}$. This vertex is clearly
adjacent to $x_{2}$ and non-adjacent to $x_{3}$].

We have thus exhausted all the possibilities and may conclude that $x_{3}\in
A_{3}$ as desired. ∎

In the following lemma, the term ”set” refers to a member of
$\\{A_{1},A_{2},A_{3},D,I_{1},I_{2},I\\}$.

######  Lemma 4.22.

Given the sets of $d$-dimensional binary vectors $A_{1},A_{2},A_{3}$ construct
a graph $G$ as above. If there exists a triplet $x_{1},x_{2},x_{3}$ such that
$N(x_{1})\cap N(x_{2})\subseteq N(x_{3})$, then $x_{1},x_{2}$ cannot be in the
same set.

###### Proof.

Assume there exists such a triplet. Using the result of the previous lemma, we
may assume that $x_{3}\in A_{3}$, and verify all the possibilities for
$x_{1},x_{2}$.

If $x_{1},x_{2}$ are both in $A_{1}$, then since $I_{1}$ is attached to both
$A_{1}$ and $A_{3}$, this contradicts the Lemma 4.15-

Similarly argument shows that $x_{1},x_{2}$ cannot be in any of the sets
$A_{2},A_{3},I_{1},I_{2}$ and hence the only choices left are $x_{1},x_{2}\in
I$ and $x_{1},x_{2}\in D$.

So assume $x_{1},x_{2}\in I$. However, since $x_{1}$ and $x_{2}$ are both
adjacent to all the vertices in $A_{3}$, and $x_{3}$ is only adjacent to
exactly two vertices in $A_{3}$, this yields a contradiction.

Finally, assume $x_{1},x_{2}\in D$. By the Assumption 4.17, both $A_{1}$ and
$A_{2}$ contain an all $1$ vector, hence both $x_{1}$ and $x_{2}$ have a
neighbour in $A_{1}$ and $A_{2}$. It is sufficient to observe that no vertex
in $A_{3}$ is adjacent to two vertices $y,z$ such that $y\in A_{2}$, $z\in
A_{3}$. ∎

######  Lemma 4.23.

Given the sets of $d$-dimensional binary vectors $A_{1},A_{2},A_{3}$ construct
a graph $G$ as above. Let $x$ be any vertex in $G$ such that $x\not\in A_{3}$.
Then $x$ is adjacent to at least $k$ vertices in $A_{3}$.

###### Proof.

If $x\in A_{1}$ (resp. $A_{2}$), then by construction, it is adjacent to all
the vertices $a_{1}^{3},\dots,a_{k}^{3}$ (resp.
$a_{k+1}^{3},\dots,a_{2k}^{3}$).

If $x\in I$, then it is adjacent to all vertices in $A_{3}$. If $x\in D$, then
we are done by Assumption 4.19. Finally, if $x\in I_{1}$ (resp. $I_{2}$), then
we are done by Assumption 4.20. ∎

######  Corollary 4.24.

Given the sets of $d$-dimensional binary vectors $A_{1},A_{2},A_{3}$ construct
a graph $G$ as above. If there exists a triplet $x_{1},x_{2},x_{3}$ such that
$N(x_{1})\cap N(x_{2})\subseteq N(x_{3})$, then $x_{1}\not\in I$
(symmetrically $x_{2}\not\in I$).

###### Proof.

By Lemma 4.21, we know that $x_{3}\in A_{3}$ and by the construction of $G$,
$x_{3}$ is adjacent to exactly two vertices in $A_{3}$.

Assume now for contradiction that $x_{1}\in I$. If $x_{2}\not\in A_{3}$, then
by the previous lemma, $N(x_{1})\cap N(x_{2})$ contains at least $k$ vertices
from $A_{3}$, whereas $N(x_{3})$ contains exactly two vertices from $A_{3}$,
yielding a contradiction. Therefore, we may assume that $x_{2}\in A_{3}$. But
then, there exists a vertex $y\in A_{3}$ such that $y\in N(x_{1})\cap
N(x_{2})$ and $y\not\in N[x_{3}]$ (assuming $n>4$), concluding the proof. ∎

###### Proof (of Theorem 4.16)..

Assume first that there exists a triplet of vectors $a_{1}\in A_{1}$,
$a_{2}\in A_{2}$, $a_{3}\in A_{3}$ that are orthogonal. We claim that the
vertices corresponding to these vectors satisfy $N(a_{1})\cap
N(a_{2})\subseteq N(a_{3})$.

First observe that $N(a_{1})\cap N(a_{2})$ contains no vertices from
$A_{1},A_{2},A_{3},I_{1}$, nor $I_{2}$.

Consider now any vertex $y\in I$. By construction $y\in N(a_{3})$, so this
case is also covered.

Finally, consider any vertex $D_{i}$ in $N(a_{1})\cap N(a_{2})\cap D$. Since
$a_{1},a_{2},a_{3}$ are orthogonal, either $a_{1}[i]=0$ (in which case $a_{1}$
is not adjacent to $D_{i}$), or $a_{2}[i]=0$ (in which case $a_{2}$ is not
adjacent to $D_{i}$), or $a_{3}[i]=0$ (in which case $a_{3}$ is adjacent to
$D_{i}$), hence in any case, either $D_{i}$ is contained in $N(a_{3})$, or it
is not contained in $N(a_{1})\cap N(a_{2})$ as desired.

Conversely, assume that there exists a triplet of vertices $x_{1},x_{2},x_{3}$
satisfying $N(x_{1})\cap N(x_{2})\subseteq N(x_{3})$.

Then, by Lemma 4.21, we have that $x_{3}\in A_{3}$.

We first handle the case if $x_{1}\in I_{1}$, $x_{2}\in I_{2}$. Then
$D\subseteq N(x_{1})\cap N(x_{2})$ and clearly $D\subseteq
N(x_{3})\Rightarrow$ $x_{3}$ corresponds to an all zero vector, and clearly in
this case any selection of vectors from $A_{1}$ and $A_{2}$ satisfies the
orthogonality.

We proceed to show that in all other cases the only possibility is $x_{1}\in
A_{1}$ and $x_{2}\in A_{2}$ (or vice versa). To achieve this, we will
exhaustively consider all the possibilities for $x_{1}$ and $x_{2}$. By
Corollary 4.24, we do not have to verify the cases $x_{1}\in I$ (symmetrically
$x_{2}\in I$).

Assume first $x_{1}\in I_{1}$. Then, by Lemma 4.15, we have that $x_{2}\not\in
A_{1}$ and $x_{2}\not\in A_{3}$ and by Lemma 4.22, $x_{2}\not\in I_{1}$.

So suppose first $x_{2}\in A_{2}$. By 4.18, $x_{2}$ there exists a coordinate
$D_{i}\in D$ such that $D_{i}\in N(x_{2})$ and $D_{i}\not\in N(x_{3})$. This
case is concluded by observing that every vertex in $D$ is adjacent to $x_{1}$
(in particular $D_{i}\in N(x_{1})$).

Lastly, suppose that $x_{2}\in D$. Then $x_{2}$ is adjacent to every vertex in
$I_{1}$, and since $I_{1}$ is attached to $A_{3}$, similarly as in the proof
of Lemma 4.21 this contradicts the injectivity of $\phi$ in the construction
of the intersection gadget $I_{1}$.

Hence, we may conclude $x_{1}\not\in I_{1}$ (resp. $x_{2}\not\in I_{1}$) and
symmetrically $x_{1}\not\in I_{2}$ (resp. $x_{2}\not\in I_{2}$).

Finally, assume $x_{1}\in A_{1}$. Applying the same arguments from above,
$x_{2}$ is not in $I\cup I_{1}\cup I_{2}\cup A_{1}$.

Hence, assume $x_{2}\in D$, but since $x_{2}$ is then adjacent to all the
vertices in $I_{1}$, which is attached to both $A_{1}$ and $A_{3}$, we again
apply the same argument as in the proof of Lemma 4.21 to contradict the
injectivity of $\phi$.

We only have to verify that $x_{2}\not\in A_{3}$, but this follows directly by
observing that $I_{1}$ is attached to both $A_{1}$ and $A_{3}$ and applying
the Lemma 4.15.

Symmetrically, one may argue that if $x_{1}\in A_{2}$, $x_{2}$ is not in
$A_{2}\cup A_{3}\cup I_{1}\cup I_{2}\cup I\cup D$.

Finally, we only have to check $x_{1}\in D$. Notice that we already verified
(up to rearranging $x_{1},x_{2}$) the cases when $x_{2}\in I\cup I_{1}\cup
I_{2}\cup A_{1}\cup A_{2}$, so the only case left to check is $x_{2}\in
A_{3}$. One last time, we may apply the same argument as in the proof of Lemma
4.21 to contradict the injectivity of $I_{2}$, since $A_{3}$ is attached to
$I_{2}$ and $x_{1}$ is adjacent to all the vertices in $I_{2}$.

We have thus exhausted all the possibilities, and we may conclude that if
there exists a triplet of vertices $x_{1},x_{2},x_{3}$ satisfying
$N(x_{1})\cap N(x_{2})\subseteq N(x_{3})$, either there exists an all zero
vector in $A_{3}$, in which case we are trivially done, or $x_{1}\in A_{1}$,
$x_{2}\in A_{2}$ (or vice versa).

We claim that if $x_{1}\in A_{1}$, $x_{2}\in A_{2}$, then the vectors
corresponding to $x_{1},x_{2},x_{3}$ are orthogonal.

Indeed, if we consider any dimension $i$, either $x_{3}$ is adjacent to the
vertex $D_{i}$ corresponding to the $i$-th dimension (in which case
$x_{3}[i]=0$), or $x_{1}$ is non-adjacent to $D_{i}$ (in which case
$x_{1}[i]=0$), or $x_{2}$ is non-adjacent to $D_{i}$ (in which case
$x_{2}[i]=0$). ∎

###  4.2 Polychromatic to bichromatic basic problems reduction

In order to prove the hardness of monochromatic basic problems with at least
one negative vertex in the sparse graphs, we introduce the intermediate class
of bichromatic basic problems defined as follows. Let $k$ be a fixed constant
and for every $i\in[k]$, let $F_{i}:X\times Y\to\\{0,1\\}$ be either defined
as $F_{i}(x,y)=E(x,y)$, or $F_{i}(x,y)=\overline{E(x,y)}$. Now all the
bichromatic basic problems can be stated in the following way.

Given: A bipartite graph $G=(X,Y,E)$

Determine: Is there a set of vertices $x_{1},\dots,x_{k}\in X$, such that for
all $y\in Y$ it holds that $F_{1}(x_{1},y)\lor\dots\lor F_{k}(x_{k},y)$?

We proceed to prove that all the bichromatic basic problems (except
bichromatic variant of $k$-dominating set) are $k$-OV hard already in sparse
graphs, by reducing from the corresponding polychromatic basic problems.

Given a set $S$ with $n$ elements, let $\phi:S\to\\{0,1\\}^{\log(n)}$ be an
injective function called the _identifier_ of $S$.

Let $x$ be a binary vector with $d$ dimensions and define

$f(x)=\Big{\\{}\big{(}i_{1}^{(1)},\dots,i_{k}^{(1)},\dots,i_{k}^{(k)},b_{1}^{(1)},\dots,b_{k}^{(1)},\dots,b_{k}^{(k)}\big{)}\mid\bigwedge_{s=1}^{k}\big{(}\bigvee_{t=1}^{k}x[i_{t}^{(s)}]=b_{t}^{(s)}\big{)}\Big{\\}}$

Let $S$ be a set of $n$ elements and

$T=\Big{\\{}\big{(}x,I\big{)}\mid x\in S,I\in f\circ\phi(x)\Big{\\}}$

For the rest of this section, let $S,T,f,\phi$ be as above.

######  Lemma 4.25.

For every subset $\\{x_{1},\dots,x_{k},y_{1},\dots,y_{k}\\}\subseteq S$, there
exist indices $I=(i_{1}^{(1)},\dots,i_{k}^{(k)})$, and bits
$B=(b_{1}^{(1)},\dots,b_{k}^{(k)})$ such that $(x_{i},I\times B)\in T$ and
$(y_{i},I\times B)\not\in T$ for all $i$.

###### Proof.

Since $\phi$ is injective, we can find an index $i_{1}^{(1)}$, such that
$\phi(x_{1})[i_{1}^{(1)}]\neq\phi(y_{1})[i_{1}^{(1)}]$. Similarly, find
indices $i_{2}^{(1)},\dots,i_{k}^{(1)}$, such that
$\phi(x_{j})[i_{j}^{(1)}]\neq\phi(y_{1})[i_{j}^{(1)}]$ for all $2\leq j\leq
k$.

Let $b^{(1)}_{t}=x_{t}[i_{t}^{(1)}]$ for all $1\leq t\leq k$ and observe that
the formula $\bigvee_{t=1}^{k}\phi(y_{1})[i_{t}^{(1)}]=b^{(1)}_{t}$ is not
satisfied, while $\bigvee_{t=1}^{k}\phi(x_{j})[i_{t}^{(1)}]=b^{(1)}_{t}$ is
satisfied for all $j$.

Similarly, one can find indices $i_{1}^{(s)},\dots,i_{k}^{(s)}$, such that
$\phi(x_{j})[i_{j}^{(s)}]\neq\phi(y_{s})[i_{j}^{(s)}]$ for all $2\leq s\leq k$
and symmetrically setting $b^{(s)}_{t}=x_{t}[i_{t}^{(s)}]$ leaves the formula
$\bigvee_{t=1}^{k}\phi(y_{s})[i_{t}^{(s)}]=b^{(s)}_{t}$ unsatisfied, while
satisfying $\bigvee_{t=1}^{k}\phi(x_{j})[i_{t}^{(s)}]=b^{(s)}_{t}$.

Finally, we observe that consequently the formula
$\bigwedge_{s=1}^{k}\big{(}\bigvee_{t=1}^{k}x_{j}[i_{t}^{(s)}]=b_{t}^{(s)}\big{)}$
is satisfied for every $j$ and
$\bigwedge_{s=1}^{k}\big{(}\bigvee_{t=1}^{k}y_{j}[i_{t}^{(s)}]=b_{t}^{(s)}\big{)}$
is not satisfied for any $j$. The desired result follows. ∎

######  Lemma 4.26.

Let $G=(X,Y,E)$ be a bipartite graph and $k$ a fixed constant. If $S\subseteq
X$, then one can add $\tilde{\mathcal{O}}(1)$ vertices to $Y$ and connect
those vertices to $S$ so that for any $k$ vertices $x_{1},\dots,x_{k}\in S$
and for any $k$ vertices $x^{\prime}_{1},\dots,x^{\prime}_{k}\in X$ there
exists a vertex $y\in Y$ such that $y\in N(x_{1})\cap N(x_{2})\cap\dots\cap
N(x_{k})$ and $y\not\in N(x^{\prime}_{1})\cup\dots\cup N(x^{\prime}_{k})$.

###### Proof.

Let $r=\lceil\log(|S|)\rceil$. For every tuple of indices $1\leq
i^{(1)}_{1},\dots,i_{k}^{(1)},\dots,i_{k}^{(k)}\leq r$ add $2^{k}$ vertices to
$Y$, one corresponding to each variation of bits $00\cdots 0,\dots 11\cdots
1$. Add edge between $x\in X$ and a new vertex corresponding to
$I=(i^{(1)}_{1},\dots,i_{k}^{(1)},\dots,i_{k}^{(k)},b_{1}^{(1)},\dots,b_{k}^{(1)},\dots,b_{k}^{(k)})$
if and only if $(x,I)\in T$.

Now fix any tuple of vertices $x_{1},\dots,x_{k}\in S$. By the previous lemma,
for any $x^{\prime}_{1},\dots,x^{\prime}_{k}\in S$, we can find a vertex $y$
corresponding to some indices and bits
$(i^{(1)}_{1},\dots,i_{k}^{(1)},\dots,i_{k}^{(k)},b_{1}^{(1)},\dots,b_{k}^{(1)},\dots,b_{k}^{(k)})$
such that $y\in N(x_{i})$ and $y\not\in N(x^{\prime}_{i})$ for all $i$.

Observe that since $y$ is adjacent only to the vertices in $S$, by choosing a
vertex $x^{\prime}_{i}\in X\setminus S$, this property remains preserved. ∎

Given a bipartite graph $G=(X,Y,E)$ and a subset $S$, the set of
$\tilde{\mathcal{O}}(1)$ vertices as described in the last lemma is called
_identifier gadget_ and is denoted by $J_{S}$. Constructing a graph
$G^{\prime}=(X,Y\cup J_{S},E)$ from $G$ by adding the edges as described above
will be referred to as _attaching_ the identifier gadget to $S$.

######  Proposition 4.27.

Let $\Phi$ be a basic property with at least one negative literal. Given an
instance $G=(V_{1},\dots,V_{k},W)$ of the multichromatic basic problem
corresponding to $\Phi$ with $n$ vertices and $m$ edges, we can construct in
time $\tilde{\mathcal{O}}(m)$ an equivalent instance $G^{\prime}=(X,Y,E)$ of
the corresponding bichromatic basic problem with at most
$\tilde{\mathcal{O}}(m)$ edges.

###### Proof.

Without loss of generality, assume that $\Phi=E(v_{1},w)\lor\dots\lor
E(v_{\ell},w)\lor\overline{E(v_{\ell+1},w)}\lor\overline{E(v_{k},w)}$ and let
$k-\ell=\ell^{\prime}\geq 1$.

Consider the following construction of the graph $G^{\prime}=(X,Y,E)$.

  * •

Fix a $(k-1)$-element subset $S^{\prime}$ of $\\{V_{1},\dots,V_{k}\\}$.

  * •

Let $S=\bigcup_{s\in S^{\prime}}s$ and attach an identifier gadget $J_{S}$ to
$S$.

  * •

If for some $1\leq i\leq\ell$, $V_{i}\not\in S^{\prime}$, add all edges
between $V_{i}$ and $J_{S}$.

  * •

Repeat the last steps for every $(k-1)$-element subset $S^{\prime}$ of
$\\{V_{1},\dots,V_{k}\\}$

  * •

Let $X=V_{1}\cup\dots\cup V_{k}$ and let $Y$ consist of $W$ and all the
gadgets $J_{S}$ as constructed above.

######  Claim 4.28.

If there are vertices $x_{1},\dots,x_{k}\in X$ such that
$N(x_{\ell+1})\cap\dots\cap N(x_{k})\subseteq N(x_{1})\cup\dots\cup
N(x_{\ell})$, then each of the sets $V_{1},\dots,V_{k}$ contains exactly one
of the vertices $x_{1},\dots,x_{k}$.

###### Proof.

Assume that for some $\ell+1\leq i\leq k$ the set $V_{i}$ contains none of the
vertices $x_{1},\dots,x_{k}$.

Observe that the identifier gadget $J_{X\setminus V_{i}}$ is attached to the
whole set $X$ except $V_{i}$, hence contradicting Lemma 4.26.

Assume now that for some $1\leq i\leq\ell$, $V_{i}$ contains none of the
vertices $x_{1},\dots,x_{k}$.

By Lemma 4.26, there exists a vertex $v\in J_{X\setminus V_{i}}$ adjacent to
all $x_{\ell+1},\dots,x_{k}$ and to no other vertex in $X\setminus V_{i}$. In
particular, it is non-adjacent to $x_{j}$ for any $j\in[\ell]$, yielding a
contradiction.

Hence, each set $V_{i}$ contains at least one vertex and since we are placing
$k$ vertices in $k$ sets, the upper bound is also trivially satisfied. ∎

######  Claim 4.29.

If there are vertices $x_{1},\dots,x_{k}\in X$ such that
$N(x_{\ell+1})\cap\dots\cap N(x_{k})\subseteq N(x_{1})\cup\dots\cup
N(x_{\ell})$, then $x_{i}\in V_{j}$ for all $1\leq i\leq\ell$ and some $1\leq
j\leq\ell$.

###### Proof.

Assume for contradiction that there exists some index $i$ such that $x_{i}\in
X\setminus\bigcup_{1\leq j\leq\ell}V_{j}$. Then by the pigeonhole principle,
there exists a set $V_{j}$ (for $1\leq j\leq\ell$) that does not contain any
of the vertices $x_{1},\dots,x_{\ell}$ and by the previous claim, $V_{j}$
contains $x_{k}$ (without loss of generality).

Consider the identifier gadget $J_{X\setminus V_{j}}$. By construction, every
vertex in this gadget is adjacent to $x_{k}$. Hence, by the assumption that
$N(x_{\ell+1})\cap\dots\cap N(x_{k})\subseteq N(x_{1})\cup\dots\cup
N(x_{\ell})$, it must also hold that $N(x_{\ell+1})\cap\dots\cap
N(x_{k-1})\cap J_{X\setminus V_{j}}\subseteq N(x_{1})\cup\dots\cup
N(x_{\ell})$, thus contradicting Lemma 4.26. ∎

Now assume $V_{1},\dots,V_{k},W$ is a yes instance of the polychromatic basic
problem. Namely, we can find $v_{1}\in V_{1},\dots,v_{k}\in V_{k}$, such that
for every $w\in W$, the formula $E(v_{1},w)\lor\dots\lor
E(v_{\ell},w)\lor\overline{E(v_{\ell+1},w)}\lor\dots\lor\overline{E(v_{k},w)}$
is satisfied.

We claim that in $G^{\prime}$, for every $y\in Y$, the formula
$E(v_{1},y)\lor\dots\lor
E(v_{\ell},y)\lor\overline{E(v_{1},y)}\lor\dots\lor\overline{E(v_{k},y)}$ is
satisfied.

Let $v\in Y$ be arbitrary. If $v\in W$, then it is trivially satisfied.
Consider now $v\in Y\setminus W$. Clearly $v\in J_{X\setminus V_{i}}$ for some
$i$. But then by construction $v$ is adjacent to $v_{i}$ and the formula is
satisfied.

Conversely, assume that there are vertices $x_{1},\dots,x_{k}\in X$ such that
for every $y$ in $Y$ the formula $E(x_{1},y)\lor\dots\lor
E(x_{\ell},y)\lor\overline{E(x_{\ell+1},y)}\lor\dots\lor\overline{E(x_{k},y)}$
is satisfied.

The result now follows trivially from the two claims above and the fact that
$W\subseteq Y$. ∎

The following proposition now follows directly.

######  Proposition 4.30.

Let $\Phi$ be a basic property with at least one negative literal. For any
$\varepsilon>0$, the bichromatic basic problem corresponding to $\Phi$ cannot
be solved faster than $\mathcal{O}(n^{k-\varepsilon})$ even on graphs with
$\tilde{\mathcal{O}}(n)$ edges, unless SETH fails.

##  5 Bichromatic to Monochromatic basic problem reduction

We now proceed to prove the hardness of monochromatic basic problems in sparse
graphs with at least one negative literal in the corresponding basic property
by reducing from their bichromatic variants.

######  Lemma 5.1.

Given any positive integer $N$ and a fixed constant $k$, there exists a graph
$G$ with at most $N^{f(k)}$ vertices for some computable function $f$
satisfying the following conditions.

  * •

Every vertex $v$ is labelled by an integer $i\in\\{1,\dots,M\\}$ for $N\leq
M\leq\mathcal{O}(N)$. This is denoted by $\lambda(v)=i$.

  * •

For all $a_{1},\dots,a_{k},b_{1},\dots,b_{k}\in V(G)$ and for every $i\in
1,\dots,N$, there exists a vertex $x\in
V(G)\setminus\\{a_{1},\dots,a_{k},b_{1},\dots,b_{k}\\}$ such that
$\lambda(x)=i$ and $x$ is adjacent to $a_{j}$ and nonadjacent to $b_{j}$ for
all $j$.

Before proving this lemma, we first show how one can use this result to obtain
a reduction from a bichromatic basic problem to the corresponding
monochromatic basic problem.

######  Proposition 5.2.

Let $\Phi$ be a basic property with $k$ variables and at least one negative
literal. Given an instance $G=(X,Y,E)$ of the bichromatic basic problem
corresponding to $\Phi$ with $n$ vertices and at most $\tilde{\mathcal{O}}(n)$
edges, we can construct an equivalent instance $G^{\prime}=(V,E)$ of the
corresponding monochromatic basic problem in time $\tilde{\mathcal{O}}(n)$
consisting of at most $\tilde{\mathcal{O}}(n)$ edges.

###### Proof.

Without loss of generality, assume that $\Phi=E(x_{1},y)\lor\dots\lor
E(x_{\ell},y)\lor\overline{E(x_{\ell+1},y)}\lor\overline{E(x_{k},y)}$, for
some $\ell<k$, and let $k-\ell=\ell^{\prime}\geq 1$. Consider the graph
$G^{\prime}$ constructed as follows.

  * •

Let $H$ be a graph satisfying the properties of Lemma 5.1.

  * •

Let $N=|Y|$ and $M$ be as in Lemma 5.1. Add $M-N$ isolated vertices (trivially
satisfied by $x_{\ell+1}$) to $Y$ in the input graph $G$ and label the
vertices in $Y$ with $1,\dots,M$ such that any two distinct vertices get a
distinct label.

  * •

Let $V(G^{\prime})=V(H)\cup X$.

  * •

Let $H\cong G[V(H)]$ and add an edge between $x\in X$ and $h\in H$ if and only
if $\lambda(h)=i$ and there is an edge between $x$ and a vertex in $Y$ labeled
$i$ in $G$.

  * •

There are no other edges in $G^{\prime}$.

First assume $G$ is a yes instance of the bichromatic basic problem. Namely,
assume that we can find $x_{1},\dots,x_{k}\in X$ such that for every $y\in Y$,
the formula $E(x_{1},y)\lor\dots\lor
E(x_{\ell},y)\lor\overline{E(x_{\ell+1},y)}\lor\dots\lor\overline{E(x_{k},y)}$
is satisfied.

We claim that also $\forall v\in V(G^{\prime})$, the formula
$E(x_{1},v)\lor\dots\lor
E(x_{\ell},v)\lor\overline{E(x_{\ell+1},v)}\lor\dots\lor\overline{E(x_{k},v)}$.
To see this assume first that $v\in X$. Since there are no edges inside $X$,
clearly each vertex is nonadjacent to $x_{\ell+1}$ hence satisfying the
desired formula. Mirza says: This is where the reflexive case fails for
$\ell^{\prime}=1$.

Now assume $v\in V(H)$. Then $\lambda(v)=i$ for some $1\leq i\leq M$. Consider
now the vertex $y$ in $Y\subseteq V(G)$ that is labelled $i$. This vertex
satisfies $E(x_{1},y)\lor\dots\lor
E(x_{\ell},y)\lor\overline{E(y_{1},y)}\lor\dots\lor\overline{E(y_{\ell^{\prime}},y)}$
in $G$.

Now, by construction of $G^{\prime}$, if $E(x_{i},y)$, then $E(x_{i},v)$ and
similarly if $\overline{E(x_{j},y)}$, then $\overline{E(x_{j},v)}$ and
therefore the desired formula is satisfied for $v$ as well. We have thus
covered all the vertices from $V(G^{\prime})$.

Conversely assume that $G^{\prime}$ is a yes instance of the monochromatic
basic problem. That is, assume that we can find $v_{1},\dots,v_{k},\in
V(G^{\prime})$ such that for every $w\in V(G^{\prime})$, the formula
$E(v_{1},w)\lor\dots\lor
E(v_{\ell},w)\lor\overline{E(v_{\ell+1},w)}\lor\dots\lor\overline{E(v_{k},w)}$
is satisfied.

Without loss of generality, assume $x_{1},\dots,x_{t},x_{k-s},\dots,x_{k}\in
V(H)$ for some $0\leq t\leq\ell,0\leq s<\ell^{\prime}$ and
$x_{t+1},\dots,x_{k-s-1}\in X$ (otherwise relabel). Consider an arbitrary
vertex $y\in Y\subseteq V(G)$ with label $i$. By Lemma 5.1, there exists a
vertex $v$ in $V(H)$ with $\lambda(v)=i$ that is nonadjacent to all
$x_{1},\dots,x_{t}$ and adjacent to all $x_{k-s},\dots,x_{k}$.

But then there exists a vertex $x_{j}$ in $X$ that is adjacent to $v$, for
$t+1\leq j\leq\ell$, or $x_{r}$ that is nonadjacent to $v$, for $\ell+1\leq
r\leq k-s-1$ in $G^{\prime}$. However, this implies that in $G$ $x_{j}$ is
adjacent to $y$, or $x_{r}$ is nonadjacent to $y$. In particular, the formula
$E(x_{1},y)\lor\dots\lor
E(x_{\ell},y)\lor\overline{E(x_{\ell+1},y)}\lor\dots\lor\overline{E(x_{K},Y)}$
is satisfied in $G$ by choosing $x_{t+1},\dots,x_{k}$ to be as in $G^{\prime}$
and the remaining vertices arbitrarily.

Since $y$ was selected arbitrarily, this holds for every vertex in $Y$ and
thus concludes our proof. ∎

We now proceed to prove the Lemma 5.1. But before that, we state and prove a
few small lemmas that will be useful.

######  Lemma 5.3.

For any two polynomials $f,g$ with coefficients in a field $\mathbb{F}$ of
degree at most $d$, there are at most $d$ points $x$ in $\mathbb{F}$ such that
$f(x)=g(x)$.

###### Proof.

Suppose for contradiction that this is not the case for some pair of
polynomials $f,g$. Consider the polynomial $h=f-g$. Clearly $h$ is a
polynomial of degree at most $d$ with more than $d$ roots. This however
contradicts the Fundamental Theorem of Algebra (see e.g.
[fine2012fundamental]). ∎

######  Lemma 5.4.

Given $d+1$ distinct points $x_{1},\dots,x_{d+1}\in\mathbb{F}$ and $d+1$
values $y_{1},\dots,y_{d+1}\in\mathbb{F}$, there is a unique polynomial
$f\in\mathbb{F}[X]_{\leq d}$ satisfying $f(x_{i})=y_{i}$ for all $i$.

###### Proof.

We first prove the existence, in particular, we construct a polynomial
satisfying the desired property.

Consider the following polynomial.

$f(x)=\sum_{i=1}^{d+1}y_{i}\prod_{j\neq i}\frac{(x-x_{j})}{(x_{i}-x_{j})}$

Note that since $x_{i}\neq x_{j}$ for any $i\neq j$, such a polynomial is
well-defined and the degree is clearly at most $d$.

For any $t\in\\{1,\dots,d+1\\}$, consider the value $f(x_{t})$. Clearly, for
every $i\neq t$, the product $\prod_{j\neq i}\frac{(x-x_{j})}{(x_{i}-x_{j})}$
contains the term $\frac{x-x_{t}}{x_{i}-x_{t}}$, which evaluates to $0$ and
the whole product consequently evaluates to $0$.

Hence,

$f(x_{t})=y_{t}\prod_{j\neq t}\frac{(x_{t}-x_{j})}{(x_{t}-x_{j})}=y_{t}$

as desired. The uniqueness follows directly from the previous lemma. ∎

###### Proof (of Lemma 5.1)..

Let $p$ be the smallest prime number strictly larger than $k^{2}(\log(N)+k+2)$
and let $\mathbb{F}_{p}$ denote the Galois field of order $p$. Let
$d=\lceil\log_{p}(N)\rceil+k$.

Let ${V(G)=\mathbb{F}_{p}[X]_{\leq d}}$, that is each vertex in $G$
corresponds to a polynomial with coefficients in $\mathbb{F}_{p}$ of degree at
most $d$.

Let $L=\lceil\log_{p}(N)\rceil$ and for $f\in V(G)$ let $\lambda(f)=i$ if and
only if $\psi((f(1),\dots,f(L)))=i$ be the labeling of the vertices in $G$ for
a bijective function $\psi:\mathbb{F}_{p}^{L}\to[p^{L}]$.

Let $R=L+dk+k+1$ and for any $f,g\in V(G)$, let $\\{f,g\\}\in E(G)$ if and
only if there exists an $x$ such that $L<x\leq R$ and $f(x)=g(x)$.

We observe that $p>R$, hence $\\{1,\dots,R\\}$ are all distinct elements in
$\mathbb{F}_{p}$.

######  Claim 5.5.

For any fixed set of polynomials $\\{a,b_{1},\dots,b_{k}\\}\subseteq V(G)$ and
a $k-1$ element set $A\subseteq\\{L+1,\dots,R\\}$ there exists a point
$x\in\\{L+1,\dots,R\\}\setminus A$ such that
$a(x)\not\in\\{b_{1}(x),\dots,b_{k}(x)\\}$

###### Proof.

By Lemma 5.3, $a$ agrees with $b_{i}$ in at most $d$ points. Hence, in total,
there are at most $dk$ points $x$ such that
$a(x)\in\\{b_{1}(x),\dots,b_{k}(x)\\}$.

Consequently, there are at least $R-(L+1)-dk=k$ points $x$ such that
$a(x)\not\in\\{b_{1}(x),\dots,b_{k}(x)\\}$ thus proving the desired. ∎

Let $a_{1},\dots,a_{k},b_{1},\dots,b_{k}$ be arbitrary vertices. By the claim
above, we can find distinct elements $x_{1},\dots,x_{k}$ such that
$a_{i}(x_{i})\not\in\\{b_{1}(x_{i}),\dots,b_{k}(x_{i})\\}$ for any $1\leq
i\leq k$. Let $\ell$ be an arbitrary fixed label such that
$\psi^{-1}(\ell)=(\ell_{1},\dots,\ell_{L})$. Consider the set $S$ consisting
of polynomials $f$ satisfying $f(1)=\ell_{1},\dots,f(L)=\ell_{L}$ and
$f(x_{i})=a_{i}(x_{i})$ for every $1\leq i\leq k$.

Since $d=L+k$, by Lemma 5.4, if we fix a point
$t\in\\{L+1,\dots,R\\}\setminus\\{x_{1},\dots,x_{k}\\}$, there is a unique
polynomial $f$ in $S$, such that $f(t)=b_{j}(t)$ for any $1\leq j\leq k$.
Hence, the set

$T=\\{f\in S\mid\exists L+1\leq t\leq R\;\exists 1\leq j\leq k\text{ such that
}f(t)=b_{j}(t)\\}$

contains at most $(R-L-k-1)k$ elements.

Similarly, by Lemma 5.4, there are at least $p$ distinct polynomials in $S$.

Notice that it is sufficient to show that the set $S\setminus T$ is non-empty,
as this would prove the existence of a vertex adjacent to all $a_{i}$ and non-
adjacent to all $b_{j}$ for all $i,j$.

To this end, we compute the value of

$|S\setminus T|\geq p-(R-L-k-1)k>p-R>0$

and this concludes the proof. ∎

Combining the results from the last two subsections, we obtain the main result
of this chapter.

######  Theorem 5.6.

Let $\Phi$ be a basic property with at least one negative literal. For any
$\varepsilon>0$, the monochromatic basic problem corresponding to $\Phi$
cannot be solved faster than $\mathcal{O}(n^{k-\varepsilon})$ even on graphs
with $\tilde{\mathcal{O}}(n)$ edges, unless SETH fails.

##  6 Closed neighbourhood containment

In this section we show that if we assume that the edge relation is reflexive,
then neighbourhood containment problem becomes easier on sparse graphs. To
this end, we reduce the close neighbourhood containment to triangle listing
and apply the fastest known algorithm, running in
$\mathcal{O}(m^{\frac{2\omega}{w+1}})$.

######  Lemma 6.1.

Given a graph $G$, if there exists a pair of vertices $x,y$, such that
$N[x]\subseteq N[y]$, then $E(x,y)$.

######  Proposition 6.2.

Given a graph $G$, there exists a pair of vertices $x,y$, such that
$N[x]\subseteq N[y]$ if and only if $E(x,y)$ and the number of triangles
containing the edge $\\{x,y\\}$ is equal to $\deg(x)-1$.

###### Proof.

Suppose first that $N[x]\subseteq N[y]$. Then by the previous lemma $E(x,y)$.
Clearly number of triangles containing the edge $\\{x,y\\}$ is at most
$\deg(x)-1$, so it is sufficient to show that the lower bound holds as well.

Assume for contradiction that this number is strictly smaller than
$\deg(x)-1$. Then there exists $z\in N(x)$ such that $z\not\in N(y)$,
contradicting the assumption that $N[x]\subseteq N[y]$.

Conversely, assume that for some pair of adjacent vertices $x,y$ the number of
triangles containing the edge $\\{x,y\\}$ is equal to $\deg(x)-1$.

Then clearly every vertex $z\neq y$ that is adjacent to $x$ is contained in
this triangle. In particular every $z\in N(x)\setminus\\{y\\}$ is adjacent to
$y$ as desired. ∎

######  Theorem 6.3.

Closed neighbourhood containment can be solved in
$\mathcal{O}(m^{\frac{2\omega}{\omega+1}})$

###### Proof.

Follows from the last proposition and the algorithm presented in . ∎

We now come back to the basic properties, but with the additional assumption
that the edge predicate is reflexive (i.e. $E(x,x)$ for all $x\in V(G)$). We
observe that for every monochromatic basic problem

$\exists x_{1}\in V,\dots,\exists x_{\ell}\in V,\exists y_{1}\in
V,\dots,\exists y_{\ell^{\prime}}\in V\forall v\in
V\;\Big{(}\bigvee_{i=1}^{\ell}E(x_{i},v)\Big{)}\lor\Big{(}\bigvee_{i=1}^{\ell^{\prime}}\overline{E(y_{i},v)}\Big{)}$

the same reduction from $(\ell+\ell^{\prime})$ OV works if $\ell^{\prime}>1$.

If $\ell^{\prime}=1$, we observe that in the reduction from bichromatic to
monochromatic instance, $y_{1}$ in $X$ is not satisfied.

This might indicate that for such problems there exists a faster algorithm.
Note that this problem asks exactly if there exists a set of vertices
$x_{1},\dots,x_{k}$, such that $N[x_{k}]\subseteq\bigcup_{i=1}^{k-1}N[x_{i}]$.

Consider the following algorithm. Given a graph $G$ with $n$ vertices and $m$
edges, fix distinct $x_{1},\dots,x_{k-2}$ arbitrarily. Construct a tripartite
graph $G^{\prime}$ as follows. Let
$V_{1}=V_{2}=V(G)\setminus\\{x_{1},\dots,x_{k-2}\\}$ and let
$V_{3}=V(G)\setminus\big{(}N[x_{1}]\cup\dots\cup N[x_{k-2}]\big{)}$. Let
$V(G^{\prime})=V_{1}\cup V_{2}\cup V_{3}$. Finally, add edges in $G^{\prime}$
as follows. If a pair $u\neq v$ is in $E(G)$, add the edge between the vertex
corresponding to $u\in V_{1}$ and the vertex corresponding to $v\in V_{2}$.
Add the edges between $V_{3}$ and $V_{1}$, and $V_{3}$ and $V_{2}$ similarly.
Finally, for any vertex $v$ in $V_{3}$, add the edge between the copy of $v$
in $V_{3}$ and the copy of $v$ in $V_{1}$ and $V_{2}$. For each vertex $x\in
V_{1}\cup V_{2}$ store the number $\pi(x)$ of neighbours of $x$ in $V_{3}$.

Observe first that $G^{\prime}$ has $\mathcal{O}(n)$ vertices and
$\mathcal{O}(m)$ edges.

######  Lemma 6.4.

Given a graph $G$, and a set of distinct vertices $x_{1},\dots,x_{k-2}$, there
exists a pair of distinct vertices $x_{k-1},x_{k}$, such that
$N[x_{k}]\subseteq\bigcup_{i=1}^{k-1}N[x_{i}]$ and $E(x_{k-1},x_{k})$ if and
only if in the graph $G^{\prime}$ as constructed above the number of triangles
containing $x_{k-1}\in V_{1}$ and $x_{k}\in V_{2}$ is equal to $\pi(x_{k})$.

###### Proof.

Suppose first that there exists a pair of distinct vertices $x_{k-1},x_{k}$,
such that $N[x_{k}]\subseteq\bigcup_{i=1}^{k-1}N[x_{i}]$ and
$E(x_{k-1},x_{k})$. Consider the copy of $x_{k-1}$ in $V_{1}$ and the copy of
$x_{k}$ in $V_{2}$.

Fix any vertex $v$ in $V_{3}$ and consider two cases.

  * •

$v$ corresponds to the same vertex as $x_{k-1}$, or $x_{k}$ in $G$.

  * •

$v$, $x_{k-1}$, $x_{k}$ are all distinct vertices in $G$.

Notice that these are the only possibilities, since the endpoints of the edges
going between $V_{1}$ and $V_{2}$ by construction correspond to distinct
vertices in $G$.

If $v\in\\{x_{k-1},x_{k}\\}$, since $x_{k-1}$ and $x_{k}$ are distinct
vertices, adjacent in $G$, in $G^{\prime}$ the vertices $\\{x_{k-1}\in
V_{1},x_{k}\in V_{2},v\in V_{3}\\}$ form a triangle.

Assume now that $v$, $x_{k-1}$, $x_{k}$ are all distinct vertices in $G$.
Since in $G$, $v$ is not in $\bigcup_{i=1}^{k-2}N[x_{i}]$, it is either in
$N(x_{k-1})$, or is not in $N(x_{k})$. But by construction of $G^{\prime}$
this property is preserved and hence if $v\in N(x_{k})$, then $v\in
N(x_{k-1})$, or in other words for any vertex $v\in V_{3}$ that is adjacent to
$x_{k}$, it holds that $v,x_{k-1},x_{k}$ form a triangle, giving us the lower
bound. The upper bound is trivial from the fact that $G^{\prime}$ is
tripartite.

Conversely, assume that for a pair of vertices $x_{k-1}\in V_{1}$ and
$x_{k}\in V_{2}$, the number of triangles in $G^{\prime}$ containing these two
vertices is equal to $\pi(x_{k})$.

Let $v$ be an arbitrary vertex in $G$. If $v$ is not in $V_{3}$ in
$G^{\prime}$, then it is contained in $\bigcup_{i=1}^{k-2}N[x_{i}]$ in $G$. On
the other hand, if it is contained in $V_{3}$, in $G^{\prime}$ it is either
adjacent to $x_{k-1}\in V_{1}$, or nonadjacent to $x_{k}\in V_{2}$. In $G$,
this means that $v$ is either equal to $x_{k}$ or $x_{k-1}$, or adjacent to
$x_{k-1}$, or nonadjacent to $x_{k}$. In other words, if $v\in V_{3}$ in
$G^{\prime}$, then in $G$ it is either contained in $N[x_{k-1}]$, or not
contained in $N[x_{k}]$, as desired. ∎

We can observe that the last lemma gives us an algorithm running in time
$\mathcal{O}(n^{k-2}m^{\frac{2\omega}{\omega+1}})$, beating the
$\Omega(n^{k})$ running time for sufficiently sparse graphs.

##  7 Notes on the Literature

Grandoni, Eisenbrand: $k$-DomSet in $n^{\omega(k/2,1,k/2)}$-time:
https://doi.org/10.1016/j.tcs.2004.05.009

Patrascu, Williams: $k$-DomSet LB https://people.csail.mit.edu/mip/papers/sat-
lbs/paper.pdf

FOPs, dense case: https://dl.acm.org/doi/10.1145/2603088.2603121