Abstract. The problem of finding a maximum 2-matching without short cycles has received significant attention due to its relevance to the Hamiltonian cycle problem. This problem is generalized to finding a maximum [Formula: see text]-matching which excludes specified complete [Formula: see text]-partite subgraphs, where [Formula: see text] is a fixed positive integer. The polynomial solvability of this generalized problem remains an open question. In this paper, we present polynomial-time algorithms for the following two cases of this problem: in the first case the forbidden complete [Formula: see text]-partite subgraphs are edge-disjoint, and in the second case the maximum degree of the input graph is at most [Formula: see text]. Our result for the first case extends the previous work of Nam (1994), showing the polynomial solvability of the problem of finding a maximum 2-matching without cycles of length four, where the cycles of length four are vertex-disjoint. The second result expands upon the works of Bérczi and Végh (2010) and Kobayashi and Yin (2012), which focused on graphs with maximum degree at most [Formula: see text]. Our algorithms are obtained from exploiting the discrete structure of restricted [Formula: see text]-matchings and employing an algorithm for the Boolean edge-CSP.

Abstract In this article, we introduce the b‐bibranching problem in digraphs, which is a common generalization of the bibranching and b‐branching problems. The bibranching problem, introduced by Schrijver, is a common generalization of the branching and bipartite edge cover problems. Previous results on bibranchings include polynomial algorithms, a linear programming formulation with total dual integrality, a packing theorem, and an M‐convex submodular flow formulation. The b‐branching problem, recently introduced by Kakimura, Kamiyama, and Takazawa, is a generalization of the branching problem admitting higher indegree, that is, each vertex v can have indegree at most b(v). For b‐branchings, a combinatorial algorithm, a linear programming formulation with total dual integrality, and a packing theorem for branchings are extended. A main contribution of this article is to extend those previous results on bibranchings and b‐branchings to b‐bibranchings. That is, we present a linear programming formulation with total dual integrality, a packing theorem, and an M‐convex submodular flow formulation for b‐bibranchings. In particular, the linear program and M‐convex submodular flow formulations, respectively, imply polynomial algorithms for finding a shortest b‐bibranching.

We propose a framework for optimal $t$-matchings excluding prescribed $t$-factors in bipartite graphs. The proposed framework is a generalization of the nonbipartite matching problem and includes several problems, such as the triangle-free 2-matching, square-free 2-matching, even factor, and arborescence problems. In this paper, we demonstrate a unified understanding of these problems by commonly extending previous important results. We solve our problem under a reasonable assumption, which is sufficiently broad to include the specific problems listed above. We first present a min-max theorem and a combinatorial algorithm for the unweighted version. We then provide a linear programming formulation with dual integrality and a primal-dual algorithm for the weighted version. A key ingredient of the proposed algorithm is a technique to shrink forbidden structures, which corresponds to the techniques of shrinking odd cycles, triangles, squares, and directed cycles in Edmonds' blossom algorithm, a triangle-free 2-matching algorithm, a square-free 2-matching algorithm, and an arborescence algorithm, respectively.

In this paper, we introduce the concept of b-branchings in digraphs, which is a generalization of branchings serving as a counterpart of b-matchings. Here b is a positive integer vector on the vertex set of a digraph, and a b-branching is defined as a common independent set of two matroids defined by b: an arc set is a b-branching if it has at most b(v) arcs sharing the terminal vertex v, and it is an independent set of a certain sparsity matroid defined by b. We demonstrate that b-branchings yield an appropriate generalization of branchings by extending several classical results on branchings. We first present a multi-phase greedy algorithm for finding a maximum-weight b-branching. We then prove a packing theorem extending Edmonds' disjoint branchings theorem, and provide a strongly polynomial algorithm for finding optimal disjoint b-branchings. As a consequence of the packing theorem, we prove the integer decomposition property of the b-branching polytope. Finally, we deal with a further generalization in which a matroid constraint is imposed on the b(v) arcs sharing the terminal vertex v.

We introduce a new framework of restricted 2-matchings close to Hamilton cycles. For an undirected graph (V,E) and a family U of vertex subsets, a 2-matching F is called U-feasible if, for each setU in U, F contains at most |setU|-1 edges in the subgraph induced by U. Our framework includes C_{<=k}-free 2-matchings, i.e., 2-matchings without cycles of at most k edges, and 2-factors covering prescribed edge cuts, both of which are intensively studied as relaxations of Hamilton cycles. The problem of finding a maximum U-feasible 2-matching is NP-hard. We prove that the problem is tractable when the graph is bipartite and each setU in U induces a Hamilton-laceable graph. This case generalizes the C_{<=4}-free 2-matching problem in bipartite graphs. We establish a min-max theorem, a combinatorial polynomial-time algorithm, and decomposition theorems by extending the theory of C_{<=4}-free 2-matchings. Our result provides the first polynomially solvable case for the maximum C_{<=k}-free 2-matching problem for k >= 5. For instance, in bipartite graphs in which every cycle of length six has at least two chords, our algorithm solves the maximum C_{<=6}-free 2-matching problem in O(n^2 m) time, where n and m are the numbers of vertices and edges, respectively.

The matching forest problem in mixed graphs is a common generalization of the matching problem in undirected graphs and the branching problem in directed graphs. Giles presented an $\mathrm{O}(n^{2}m)$-time algorithm for finding a maximum-weight matching forest, where $n$ is the number of vertices and $m$ is that of edges, and a linear system describing the matching forest polytope. Later, Schrijver proved total dual integrality of the linear system. In the present paper, we reveal another nice property of matching forests: the degree sequences of the matching forests in any mixed graph form a delta-matroid, and the weighted matching forests induce a valuated delta-matroid. We remark that the delta-matroid is not necessarily even, and the valuated delta-matroid induced by weighted matching forests slightly generalizes the well-known notion of Dress and Wenzel's valuated delta-matroids. By focusing on the delta-matroid structure and reviewing Giles' algorithm, we design a simpler $\mathrm{O}(n^{2}m)$-time algorithm for the weighted matching forest problem. By incorporating Gabow's method for the weighted matching problem into Giles' algorithm, we also present a faster algorithm for the weighted matching forest problem running in $\mathrm{O}(n^{3})$-time, which improves upon the previous best complexity of $\mathrm{O}(n^{2}m)$.

In this paper we are interested in algorithms for finding $2$-factors that cover certain prescribed edge-cuts in bridgeless cubic graphs. Since a Hamilton cycle is a 2-factor covering all edge-cuts, imposing the constraint of covering those edge-cuts makes the obtained $2$-factor closer to a Hamilton cycle. We present an algorithm for finding a minimum-weight $2$-factor covering all the $3$-edge cuts in weighted bridgeless cubic graphs, together with a polyhedral description of such 2-factors and that of perfect matchings intersecting all the 3-edge cuts in exactly one edge. We further give an algorithm for finding a 2-factor covering all the $3$- and $4$-edge cuts in bridgeless cubic graphs. Both of these algorithms run in ${\rm O}(n\sp{3})$ time, where $n$ is the number of vertices. As an application of the latter algorithm, we design a 6/5-approximation algorithm for finding a minimum 2-edge-connected spanning subgraph in 3-edge-connected cubic graphs, which improves upon the previous best ratio of 5/4. The algorithm begins with finding a 2-factor covering all 3- and 4-edge cuts, which is the bottleneck in terms of complexity, and thus it has running time ${\rm O}(n\sp{3})$. We then improve this time complexity to ${\rm O}(n\sp{2} \log\sp{4}n)$ by relaxing the condition of the initial $2$-factor and elaborating on the subsequent processes.

This paper deals with the independent even factor problem. For odd-cycle-symmetric digraphs, in which each arc in any odd dicycle has the reverse arc, a min-max formula is established as a common generalization of the Tutte–Berge formula for matchings and the min-max formula of Edmonds [Submodular functions, matroids, and certain polyhedra, in Combinatorial Structures and Their Applications, R. Guy et al., eds., Gordon and Breach, New York, 1970, pp. 69–87] for matroid intersection. We devise a combinatorial efficient algorithm to find a maximum independent even factor in an odd-cycle-symmetric digraph accompanied by general matroids, which commonly extends two of the alternating-path-type algorithms, the even factor algorithm of Pap [Math. Program., 110 (2007), pp. 57–69], and the matroid intersection algorithms. This algorithm gives a proof of the min-max formula and contains a new operation on matroids, which corresponds to shrinking factor-critical components in the matching algorithm of Edmonds [Canad. J. Math., 17 (1965), pp. 449–467]. The running time of the algorithm is $\mathrm{O}(n^4 Q)$, where n is the number of vertices and Q is the time for an independence test. The algorithm also gives a common generalization of the Edmonds–Gallai decomposition for matchings and the principal partition for matroid intersection.