English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the Shortest Odd Path problem, where given an undirected graph$G$, a weight function on its edges, and two vertices $s$ and $t$ in $G$, theaim is to find an $(s,t)$-path with odd length and, among all such paths, ofminimum weight. For the case when the weight function is conservative, i.e.,when every cycle has non-negative total weight, the complexity of the ShortestOdd Path problem had been open for 20 years, and was recently shown to beNP-hard. We give a polynomial-time algorithm for the special case when theweight function is conservative and the set $E^-$ of negative-weight edgesforms a single tree. Our algorithm exploits the strong connection betweenShortest Odd Path and the problem of finding two internally vertex-disjointpaths between two terminals in an undirected edge-weighted graph. It alsorelies on solving an intermediary problem variant called ShortestParity-Constrained Odd Path where for certain edges we have parity constraintson their position along the path. Also, we exhibit two FPT algorithms forsolving Shortest Odd Path in graphs with conservative weight functions. Thefirst FPT algorithm is parameterized by $|E^-|$, the number of negative edges,or more generally, by the maximum size of a matching in the subgraph of $G$spanned by $E^-$. Our second FPT algorithm is parameterized by the treewidth of$G$.

Shortest Odd Paths in Undirected Graphs with Conservative Weight Functions