On a Conjecture for Parameterized st-Orientations

MaxSTN and MinSTN – proposed by Papamanthou and Tollis (TCS 2008, JGAA 2010) – are two algorithms for producing $st$-orientations of biconnected graphs with long and short longest paths respectively. Based on extensive experiments on planar and non-planar graphs of up to 5,000 nodes, it was conjectured that ${\mathrm{\ell }}_{\max }\ge {\mathrm{\ell }}_{\min }$ for every biconnected graph $G$, where ${\mathrm{\ell }}_{\max }$ and ${\mathrm{\ell }}_{\min }$ denote the longest-path lengths of the two orientations. This paper disproves this conjecture by exhibiting a biconnected graph on 9 vertices for which MaxSTN yields ${\mathrm{\ell }}_{\max }=6$ while MinSTN yields ${\mathrm{\ell }}_{\min }=7$, regardless of how ties are broken in either algorithm.