Crossing matrix is too large for Pace limits

[alanctprado]

8 bytes 3.2 10^4 3.2 10 ^4 > 8 Gb.

Could we compute it on demand for larger cases? Not with the current algorithm...

How to do it better @heittpr?

[alanctprado]

xD

[heittpr]

Kobayashi and Tamaki described an algorithm for computing the crossing numbers $c$ for all orientable pairs (i.e: $c(u, v) > 0$ and $c(v, u) > 0$) only in $O(n +k)$, where $k$ is the number of crossings. This is sufficient for the FPT algorithm for the decision version of OSCM. Do we need the full crossing matrix for the IP formulation?

[alanctprado]

Kobayashi and Tamaki described an algorithm for computing the crossing numbers $c$ for all orientable pairs (i.e: $c(u, v) > 0$ and $c(v, u) > 0$) only in $O(n +k)$, where $k$ is the number of crossings. This is sufficient for the FPT algorithm for the decision version of OSCM. Do we need the full crossing matrix for the IP formulation?

i'm pretty sure we need the case when either are positive. @MvKaio ?

[heittpr]

Actually, I think only orientable pairs suffice. A pair of vertices ${u, v}$ can be either:

• Forced to $(u, v)$, if $c(u, v) = 0$ and $c(v, u) > 0$
• Forced to $(v, u)$, if $c(v, u) = 0$ and $c(u, v) > 0$
• Orientable, if $c(u, v) > 0$ and $c(v, u) > 0$
• Free, if $c(u, v) = 0$ and $c(v, u) = 0$

Kobayashi and Tamaki showed that we only need to decide about orientable pairs. Forced pairs are well, forced, and swapping free pairs in a permutation preserves optimality.

[perchuts]

The value of $c(u, v)$ cannot exceed $2^{31}-1$, which is the maximum value representable by a 4-byte signed integer. So why would we require 8 bytes for each $c(u, v)$?

If 8 bytes are truly needed, a minor optimization would be to compute $c(u, v)$ only for $u < v$. Then notice that $c(v, u) = |N(u)| \cdot |N(v)| - c(u, v) - |N(u) \cap N(v)|$. We can precompute $d(u, v) = |N(u) \cap N(v)|$ in something like $O(M^2)$ where $M$ is the number of edges. As $d(u, v)$ is bounded by the number of nodes, which is less than $2^{15}-1$, we can store it using short integers, saving 2GB of memory. But I guess this would make the solver a bit slower.