Guillaume Ducoffe: A variation of Boolean distance, 405-419

Abstract:

Let ${\cal P}$ be a family of paths in a connected graph $G$ so that there exists a $uv$-path in ${\cal P}$ for every choice of vertices $u$ and $v$. The ${\cal P}$-interval $J_{\cal P}(u,v)$ is the union of vertex sets of all $uv$-paths in ${\cal P}$. We address the problem of maximizing $\vert J_{\cal P}(u,v)\vert$ over all vertices $u$ and $v$, for various families ${\cal P}$ of paths.

Key Words: Boolean distance, intervals of graphs, transit functions, NP-hardness, SETH-hardness.

2010 Mathematics Subject Classification: Primary: 05C85, 05C12.

Download the paper in pdf format here.