Approximation ratio for k-outerplanar graphs

Status partial medium confidence

Significant partial progress exists. Chekuri, Naves, and Shepherd (ICALP 2013) showed that the integrality gap of the natural multicommodity LP for MaxEDP is bounded by a constant in $k$-sums of bounded-genus graphs (a class that includes bounded-treewidth graphs and in particular $k$-outerplanar graphs for fixed $k$), giving a constant-factor approximation without congestion in these settings. Ene, Mnich, Pilipczuk, and Risteski (SWAT 2016) gave an $O(r^3)$-approximation for MaxEDP on graphs of treewidth at most $r$, which is constant for any fixed treewidth (and hence for fixed $k$ in $k$-outerplanar graphs, since they have treewidth $O(k)$). Naves, Shepherd, and Xia (IPCO 2021 / Math. Programming 2022) further obtained a constant-factor approximation for the weighted edge-disjoint paths problem on outerplanar graphs ($k=1$). However, whether the approximation ratio is bounded by an absolute constant independent of $k$ (or of the treewidth) remains open.

Cited literature (4)

• partial Maximum Edge-Disjoint Paths in k-sums of Graphs (2013)
  Chandra Chekuri, Guyslain Naves, F. Bruce Shepherd · ICALP 2013 (Lecture Notes in Computer Science, vol. 7965) · arXiv:1303.4897 · doi:10.1007/978-3-642-39206-1_28

  Provides a polynomial-time algorithm that rounds any fractional MaxEDP solution in a bounded-treewidth (more generally $k$-sum of bounded-genus) graph to an integral routing of a constant fraction of the LP value, with no edge congestion, implying a constant integrality gap and a constant-factor approximation in these classes (including $k$-outerplanar graphs for fixed $k$).

• partial On Routing Disjoint Paths in Bounded Treewidth Graphs (2016)
  Alina Ene, Matthias Mnich, Marcin Pilipczuk, Andrej Risteski · SWAT 2016 (LIPIcs vol. 53) · doi:10.4230/LIPIcs.SWAT.2016.15

  Gives an $O(r^3)$-approximation for MaxEDP on graphs of treewidth at most $r$, improving over the previous $O(r \cdot 3^r)$ bound and yielding a constant-factor approximation for any fixed treewidth (and thus for $k$-outerplanar graphs with $k$ fixed).

• partial Maximum Weight Disjoint Paths in Outerplanar Graphs via Single-Tree Cut Approximators (2020)
  Guyslain Naves, F. Bruce Shepherd, Henry Xia · arXiv preprint (later IPCO 2021 / Math. Programming 2022) · arXiv:2007.10537 · doi:10.1007/978-3-030-73879-2_23

  Constructs a single-tree $O(1)$ cut approximator for outerplanar graphs and uses it to give a constant-factor approximation for the maximum-weight (capacitated) edge-disjoint paths / all-or-nothing flow problem in outerplanar graphs, settling the case $k=1$.

• partial New algorithms for maximum disjoint paths based on tree-likeness (2018)
  Krzysztof Fleszar, Matthias Mnich, Joachim Spoerhase · Mathematical Programming, vol. 171 · doi:10.1007/s10107-017-1199-3

  Gives an $O(\sqrt{r}\,\mathrm{polylog}(kr))$-approximation for MaxEDP parametrized by the feedback vertex set number $r$ (a parameter stronger than treewidth), and shows how to route $\Omega(\mathrm{OPT}^*)$ pairs with $O(\log(kr)/\log\log(kr))$ congestion.

Reviewer notes. The original conjecture asks whether the approximation ratio is bounded by an absolute constant in $k$-outerplanar graphs (or in bounded-treewidth graphs). All known results either (i) give constants that depend on $k$ / treewidth $r$ (e.g. the $O(r^3)$ bound of Ene-Mnich-Pilipczuk-Risteski), or (ii) achieve a true constant only for restricted classes such as outerplanar graphs ($k=1$, Naves-Shepherd-Xia) or via constant-congestion / LP-rounding statements (Chekuri-Naves-Shepherd 2013 for $k$-sums of bounded-genus graphs). It is plausible that the Chekuri-Naves-Shepherd result yields a constant approximation ratio for $k$-outerplanar graphs uniformly in $k$, but this could not be confirmed from the abstracts alone within the time budget. EDP is also known to be NP-hard already at treewidth 2 (series-parallel), so improvements must come from approximation, not exact algorithms.

Auto-reviewed 2026-05-08 with claude-sonnet (subagent) (web search enabled).