7
$\begingroup$

Given a graph $G(V,E)$ and a subset of vertices $T \subseteq V$, define $\mathsf{cutset}(T)$ = the set of edges connecting a vertex at $T$ with a vertex at $V\setminus T$.

Our goal is to preprocess $G$ such that, given any set $T$, we can quickly return an edge in $\mathsf{cutset}(T)$, or reply that $\mathsf{cutset}(T)$ is empty. The structure should have space complexity $\widetilde{O}(|V|)$, i.e. we are not allowed to keep all the edges. The query complexity should be $\widetilde{O}(|T|)$.

Kapron et al suggest the following neat solution, which works when the size of each cutset is at most 1.

Give each edge a unique number. For each vertex $v$, keep $\mathsf{xor}(v)$ - the binary XOR of the numbers of all the edges adjacent to it. Given a query on $T$, calculate $\mathsf{xor}(T)$ - the binary XOR of all vertices in T. Every edge which is internal to $T$ (i.e. has both endpoints inside $T$) is XORed twice, and hence is not included in $\mathsf{xor}(T)$. So, $\mathsf{xor}(T)$ is actually a XOR of all edges in $\mathsf{cutset}(T)$.

If the size of each cutset is at most 1, then there are two options: either $\mathsf{xor}(T)=0$, which means that $\mathsf{cutset}(T)$ is empty, or $\mathsf{xor}(T)$ is the number of the single edge in $\mathsf{cutset}(T)$.

The authors then go on and describe a complex, randomized structure to handle the case in which $\mathsf{cutset}(T)$ contains more than a single edge.

But in the conclusion, they say that:

It is not hard to see that the technique described here can be made deterministic with an additional $\widetilde{O}(k)$ factor in the update time, if we know the cuts are of size no greater than $k$, through the use of combinatorial designs".

Unfortunately, for me this seems to be hard... I don't understand: how can combinatorial designs can be used to solve the problem when the size of all cutsets is at most $k$?

$\endgroup$

1 Answer 1

5
$\begingroup$

You can use a linear code with distance $2k$ or so. The parity check matrix of the code has the property that the XOR of any set of at most $2k-1$ columns is non-zero. This means, in particular, that given the XOR of at most $k$ columns, you can determine (not necessarily efficiently) how many columns were XORed (since if you couldn't you would obtain a set of at most $2k-1$ columns which XORs to zero). The cost of this encoding is the number of rows of the parity check matrix. If you choose the parameters correctly and an efficiently decodable code (recall that the parity check matrix of a code is the generator matrix of its dual), then you probably obtain the conclusion stated in the remark.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.