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 , the aim is to find an ( s , t ) -path with odd length and, among all such paths, of minimum weight. For the case when the weight function is conservative, i.e., when every cycle has non-negative total weight, the complexity of the Shortest Odd Path problem had been open for 20 years, and was recently shown to be NP -hard. We give a polynomial-time algorithm for the special case when the weight function is conservative and the set E − of negative-weight edges forms a single tree. Our algorithm exploits the strong connection between Shortest Odd Path and the problem of finding two internally vertex-disjoint paths between two terminals in an undirected edge-weighted graph. It also relies on solving an intermediary problem variant called Shortest Parity-Constrained Odd Path where for certain edges we have parity constraints on their position along the path. Also, we exhibit two FPT algorithms for solving Shortest Odd Path . The first 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 − , when the weight function is conservative. Our second FPT algorithm is parameterized by the treewidth of G , and the algorithm does not rely on conservativeness.

We consider pixel labeling problems where the label set forms a tree, and where the observations are also labels. Such problems arise in feature-space analysis with a very large label set, for instance in color image segmentation. In this case a tree of labels can be constructed via hierarchical clustering of the observations. This leads to an obvious distance function between two labels, namely their distance within the tree; such tree metrics have been extensively studied outside of computer vision. We provide fast algorithms that use graph cuts to exactly minimize the energy function for pixel labeling problems with tree metrics. Our work substantially improves a facility location algorithm of Kolen, which is impractical for large label sets L since it requires O(|L|) min cuts on large graphs. Our main technical contribution is a new ordering of swap moves that reduces the running time to the equivalent of O(log |L|) min cuts; as a result, we can handle realistic-sized color images in a few seconds.

We show that the maximum number of colors that can be used in a vertex coloring of a cubic 3-connected plane graph G that avoids a face with vertices of mutually distinct colors (a rainbow face) is equal to $\frac{n}{2}+\mu^*-2$, where n is the number of vertices of G and $\mu^*$ is the size of the maximum matching of the dual graph $G^*$.

In this paper we propose a (semi-strongly) polynomial time algorithm to find a maximum packing subject to node-capacities, and thus we obtain a generalization of Keijsper, Pendavingh and Stougie algorithm concerning edge-capacities. Our method is based on Gerards' strongly polynomial time algorithm to find a maximum b-matching in a graph, which is based on a so-called Proximity Lemma. Our node-capacitated A-path packing algorithm first constructs a maximum fractional packing by using an ellipsoid method subroutine, then takes its integer part to obtain a near-optimal integral packing, and finally we construct a maximum integer packing by a short sequence of augmentations. This short sequence of augmentations is constructed by applying the version of Gerards' Proximity Lemma, specially formulated for the node-capacitated A-path packing problem.