A tournament is called cycle Mengerian (CM) if it satisfies the minimax relation on packing and covering cycles, for every nonnegative integral weight function defined on A. The purpose of this series of two papers is to show that a tournament is CM iff it contains none of four Möbius ladders as a subgraph; such a tournament is referred to as Möbius-free. In the first paper we have given a structural description of all Möbius-free tournaments, and have proved that every CM tournament is Möbius-free. In this second paper we establish the converse by using our structural theorems and linear programming approach.

In this series of two papers we examine the classical problem of ranking a set of players on the basis of a set of pairwise comparisons arising from a sports tournament, with the objective of minimizing the total number of upsets, where an upset occurs if a higher ranked player was actually defeated by a lower ranked player. This problem can be rephrased as the so-called minimum feedback arc set problem on tournaments, which arises in a rich variety of applications and has been a subject of extensive research. In this series we study this NP-hard problem using structure-driven and linear programming approaches. Let be a tournament with a nonnegative integral weight on each arc e. A subset F of arcs is called a feedback arc set if contains no cycles (directed). A collection of cycles (with repetition allowed) is called a cycle packing if each arc e is used at most times by members of . We call T cycle Mengerian (CM) if, for every nonnegative integral function w defined on A, the minimum total weight of a feedback arc set is equal to the maximum size of a cycle packing. The purpose of these two papers is to show that a tournament is CM iff it contains none of four Möbius ladders as a subgraph; such a tournament is referred to as Möbius-free. In this first paper we present a structural description of all Möbius-free tournaments, which relies heavily on a chain theorem concerning internally 2-strong tournaments.

Given a multigraph $G=(V,E)$ with a positive rational weight $w(e)$ on each edge $e$, the weighted density problem (WDP) is to find a subset $U$ of $V$, with $|U|\ge 3$ and odd, that maximizes $2w(U)/(|U|-1)$, where $w(U)$ is the total weight of all edges with both ends in $U$, and the weighted fractional edge-coloring problem can be formulated as the following linear program: minimize ${\bm 1}^T {\bm x}$ subject to $ A{\bm x} = {\bm w}$, ${\bm x} \ge {\bm 0}$, where $A$ is the edge-matching incidence matrix of $G$. These two problems are closely related to the celebrated Goldberg--Seymour conjecture on edge-colorings of multigraphs, and are interesting in their own right. Even when $w(e)=1$ for all edges $e$, determining whether WDP can be solved in polynomial time was posed by Jensen and Toft [Topics in Chromatic Graph Theory, Cambridge University Press, Cambridge, 2015, pp. 327--357] and by Stiebitz et al. [Graph Edge Colouring: Vizing's Theorem and Goldberg's Conjecture, John Wiley, New York, 2012] as an open problem. In this paper we present strongly polynomial-time algorithms for solving them exactly, and develop a novel matching removal technique for multigraph edge-coloring.

Given an edge-weighted connected graph G on n vertices and a positive integer , a subgraph of G on k vertices is called a k-subgraph in G. We design combinatorial approximation algorithms for finding a connected k-subgraph in G such that its weighted density is at least a factor of the maximum weighted density among all k-subgraph in G (which are not necessarily connected), where implies an -approximation ratio. We obtain improved -approximation for unit weights. These particularly provide the first non-trivial approximations for the heaviest/densest connected k-subgraph problem on general graphs. We also give -approximation for the problem on general weighted interval graphs.

Let G be a digraph and let π(G) be the linear system consisting of nonnegativity, stability, and domination inequalities. We call G kernel ideal if π(H) defines an integral polytope for each induced subgraph H of G, and we call G kernel Mengerian if π(H) is totally dual integral (TDI) for each induced subgraph H of G. In this paper we show that a digraph is kernel ideal iff it is kernel Mengerian iff it contains none of three forbidden structures; our characterization yields a polynomial-time algorithm for the minimum weighted kernel problem on kernel ideal digraphs. We also prove that it is NP-hard to find a kernel of minimum size even in a planar bipartite digraph with maximum degree at most three.