Internally disjoint odd paths: is it in co-NP?

Status open medium confidence

Thomassen (1980) asked whether the problem of deciding, given a graph G and two k-subsets X and Y of V(G), whether there exist k internally disjoint (X,Y)-paths of odd length, is in co-NP (where k is part of the input). No resolution of this specific question has been found in the literature. For fixed k, the parity k-disjoint paths problem—deciding whether k vertex-disjoint paths exist each with a specified parity—is solvable in nearly linear time (Kawarabayashi, Reed, and Wollan, FOCS 2011), but this does not resolve the variable-k membership question. The co-NP question posed by Thomassen remains open.

Reviewer notes. The problem as stated has k as part of the input (X and Y are k-subsets). The question is whether the complement (non-existence of k odd internally disjoint (X,Y)-paths) is in NP, i.e., whether there is a polynomial-size certificate for non-existence. This would require a min-max or duality theorem for parity-constrained disjoint paths. The closest known result is by Kawarabayashi, Reed, and Wollan ('The Graph Minor Algorithm with Parity Conditions', FOCS 2011), which gives an O(m α(m,n) n) algorithm for the parity k-disjoint paths problem for each fixed k; this puts the fixed-k version in P (hence also in co-NP) but does not resolve the variable-k co-NP question. No verified primary source addressing Thomassen's exact co-NP question was found within the allowed search budget. The problem is distinct from but related to the 'parity 2-disjoint rooted paths' work of Kawarabayashi, Li, and Reed (SODA 2010). URLs for the Kawarabayashi et al. papers could not be verified via WebFetch and are therefore not included as citations.

Auto-reviewed 2026-09-10 with claude-sonnet-4-6 (web search enabled).