Abstract. Minimizing the weight of an edge set satisfying parity constraints is a challenging branch of combinatorial optimization as witnessed by the binary hypergraph chapter of Alexander Schrijver’s book [ Combinatorial Optimization, Springer-Verlag, 2003, Chapter 80]. This area contains relevant graph theory problems including open cases of the Max Cut problem and some multiflow problems. We clarify the interconnections between some of these problems and establish three levels of difficulty. On the one hand, we prove that the Shortest Odd Path problem in undirected graphs without cycles of negative total weight and several related problems are NP-hard, settling a long-standing open question asked by Lovász (Open Problem 27 in Schrijver’s book [ Combinatorial Optimization, Springer-Verlag, 2003]). On the other hand, we provide an algorithm for the closely related and well-studied Minimum-weight Odd [Formula: see text]-Join problem for nonnegative weights: our algorithm runs in FPT time parameterized by [Formula: see text], where [Formula: see text] is the number of connected components in some efficiently computed minimum-weight [Formula: see text]-join. If negative weights are also allowed, then finding a minimum-weight odd [Formula: see text]-join is equivalent to the Minimum-weight Odd [Formula: see text]-Join problem for arbitrary weights, whose complexity is still only conjectured to be polynomially solvable. The analogous problems for digraphs are also considered.

We give a new, strongly polynomial-time algorithm and improved analysis for the metric s - t path Traveling Salesman Problem (TSP). It finds a tour of cost less than 1.53 times the optimum of the subtour elimination linear program (LP), while known examples show that 1.5 is a lower bound for the integrality gap. A key new idea is the deletion of some edges of the spanning trees used in the best-of-many Christofides-Serdyukov-algorithm, which is then accompanied by novel arguments of the analysis: edge-deletion disconnects the trees, and the arising forests are then partly reconnected by “parity correction.” We show that the arising “connectivity correction” can be achieved for a minor extra cost. On the one hand, this algorithm and analysis extend previous tools such as the best-of-many Christofides-Serdyukov-algorithm. On the other hand, powerful new tools are solicited, such as a flow problem for analyzing the reconnection cost, and the construction of a set of more and more restrictive spanning trees, each of which can still be found by the greedy algorithm. We show that these trees, which are easy to compute, can replace the spanning trees of the best-of-many Christofides-Serdyukov-algorithm. These new methods lead to improving the integrality ratio and approximation guarantee below 1.53, as was shown in the preliminary, shortened version of this article that appeared in FOCS 2016. The algorithm and analysis have been significantly simplified in the current article, while details and explanations have been added.

We give a new, strongly polynomial algorithm and improved analysis of the metric s-t path TSP. It finds a tour of cost less than 1.53 times the optimum of the subtour elimination LP, while known examples show that 1.5 is a lower bound for the integrality gap. A key new idea is the deletion of some edges of Christofides' trees, and we show that the arising "reconnection" problems can be solved for a minor extra cost. On the one hand our algorithm and analysis extend previous tools, at the same time simplifying the framework. On the other hand new tools are introduced, such as a flow problem used for analyzing the reconnection cost, and the use of a set of more and more restrictive minimum cost spanning trees, each of which can still be found by the greedy algorithm. The latter leads to a simple Christofides-like algorithm completely avoiding the computation of a convex combination of spanning trees. Furthermore, the 3/2 target-bound is easily reached in some relevant new cases.

We provide a polynomial algorithm that determines for any given undirected graph $G=(V,E)$, positive integer k, and convex functions $f_v:\mathbb{N}\rightarrow\mathbb{R}$ ($v\in V$) a subgraph $H=(V,F)$ of k edges that minimizes $\sum_{v\in V}f_v(d_H(v))$, where $d_H(v)$ is the degree of v in H. The motivation and at the same time the main application of the results is the problem of finding a subset of k vertices in a line graph that covers as many edges as possible. The latter problem generalizes the vertex cover problem for line graphs, which is in turn equivalent to the maximum matching problem in graphs. Improving paths or walks for factorization problems have to be completed by pairs of such walks for this problem. We provide several solutions leading to different variants of the problem and also show the limits of the methods by proving the NP-completeness of some direct extensions, in particular to all convex functions.

In this paper we are concerned with the so-called clique-colorations of a graph, that is, colorations of the vertices so that no maximal clique is monochromatic. On one hand, it is known to be NP-complete to decide whether a perfect graph is 2-clique-colorable, or whether a triangle-free graph is 3-clique-colorable; on the other hand, there is no example of a perfect graph where more than three colors would be necessary. We first exhibit some simple recursive methods to clique-color graphs and then relate the chromatic number, the domination number, and the maximum cardinality of a stable set to the clique-chromatic number. We show exact bounds and polynomial algorithms that find the clique-chromatic number for some classes of graphs and prove NP-completeness results for some others, trying to find the boundary between the two. For instance, while it is NP-complete to decide whether a graph of maximum degree 3 is 2-clique-colorable, K 1,3 -free graphs without an odd hole turn out to be always 2-clique-colorable by a polynomial algorithm. Finally, we show that "almost" all perfect graphs are 3-clique-colorable.

We give a $\frac{17}{12}$-approximation algorithm for the following NP-hard problem: Given a simple undirected graph, find a 2-edge connected spanning subgraph that has the minimum number of edges. The best previous approximation guarantee was $\frac{3}{2}$. If the well-known $\frac{4}{3}$ conjecture for the metric traveling salesman problem holds, then the optimal value (minimum number of edges) is at most $\frac{4}{3}$ times the optimal value of a linear programming relaxation. Thus our main result gets halfway to this target.

The duality relation between shortest paths and potentials in directed graphs and the significance of both of these in the theory of network flows is well known. In thispaper, we work out the analogous undirected notions, which neither are contained in nor contain their directed counterpart. They are more related to matching theory than to network flows: the corresponding min-path-max-potential theorem can be considered a weighted generalization of the Gallai--Edmonds structure theorem for matchings. In our earlier work [J. Combin. Theory Ser. B, 49 (1990), pp. 10--39], the corresponding theorems are proved in the special case of $\pm 1$ bipartite weightings, and this special case already contains the main points of the general proof. The goal of the present paper is to extrapolate from this $\pm 1$-weighted bipartite special case the arbitrarily weighted general min-path-max-potential theorem and to show some algorithmic consequences related to planar multiflows, the Chinese postman problem, the weighted and unweighted matching structure, etc. In order to make this paper self-contained, we also include a compact, revised variant of earlier proofs, adapted to the present context. In addition to good characterization theorems and polynomial algorithms, efficient (logarithmic polynomial) parallel algorithms follow for some of these problems.

Generalizing the two-commodity flow theorem of Rothschild and Whinston [Oper. Res., 14 (1966), pp. 377--387] and the multiflow theorem of Lovász [Acta Mat. Akad. Sci. Hungaricae, 28 (1976), pp. 129--138] and Cherkasky [Ekonom.-Mat. Metody, 13 (1977), pp. 143--151], Karzanov and Lomonosov [Mathematical Programming, O. I. Larichev, ed., Institute for System Studies, 1978, pp. 59--66] in 1978 proved a min-max theorem on maximum multiflows. Their original proof is quite long and technical and relies on earlier investigations into metrics. The main purpose of the present paper is to provide a relatively simple proof of this theorem. Our proof relies on the locking theorem, which is another result of Karzanov and Lomonosov, and the polymatroid intersection theorem of Edmonds [Combinatorial Structures and Their Applications, R. Guy, H. Hanani, N. Sauer, and J. Schönheim, eds., Gordon and Breach, 1970, pp. 69--87]. For completeness, we also provide a simplified proof of the locking theorem. Finally, we introduce the notion of a node demand problem and, as another application of the locking theorem, we derive a feasibility theorem concerning it. The presented approach gives rise to (combinatorial) polynomial-time algorithms.