On a Conjecture for Parameterized st-Orientations

Abstract

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 ${\ell }_{\max }\ge {\ell }_{\min }$ for every biconnected graph $G$, where ${\ell }_{\max }$ and ${\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 ${\ell }_{\max }=6$ while MinSTN yields ${\ell }_{\min }=7$, regardless of how ties are broken in either algorithm.