Search

Canonical decompositions, such as the Gallai–Edmonds and Dulmage–Mendelsohn decompositions, are a series of structure theorems that form the foundation of matching theory. The classical Kotzig–Lovász decomposition is a canonical decomposition applicable to a special class of graphs with perfect matchings, called factor-connected graphs, and is famous for its contribution to the studies of perfect matching polytopes and lattices. Recently, this decomposition has been generalized for general graphs with perfect matchings; this generalized decomposition is called the general Kotzig–Lovász decomposition. In fact, this generalized decomposition can be presented as a component of a more composite canonical decomposition called the Basilica decomposition. As such, the general Kotzig–Lovász decomposition has contributed to the derivation of various new results in matching theory, such as an alternative proof of the tight cut lemma and a characterization of maximal barriers in general graphs. Joins in grafts, also known as T -joins in graphs, is a classical concept in combinatorics and is a generalization of perfect matchings in terms of parity. More precisely, minimum joins and grafts are generalizations of perfect matchings and graphs with perfect matchings, respectively. Under the analogy between matchings and joins, analogues of the canonical decompositions for grafts are expected to be strong and fundamental tools for studying joins. In this paper, we provide a generalization of the general Kotzig–Lovász decomposition for arbitrary grafts. Our result also contains Sebö's generalization of the classical Kotzig–Lovász decomposition for factor-connected grafts. From our results in this paper, a generalization of the Dulmage–Mendelsohn decomposition, which is originally a classical canonical decomposition for bipartite graphs, has been obtained for bipartite grafts. This paper is the first of a series of papers that establish a generalization of the Basilica decomposition for grafts. [ABSTRACT FROM AUTHOR]

The maximum benefit Chinese postman problem (MBCPP) is a practical generalization of the Chinese postman problem. A distinctive feature of MBCPP is that the postman can traverse each edge arbitrary times and obtains a benefit for each traversal of an edge, which depends on the number of times that the edge has been traversed. (Pearn and Wang, Omega 31 (2003) 269–273) discussed MBCPP under the assumption that the benefits of each edge is a non-increasing function of the number of traversals. They showed that MBCPP under this assumption is NP-hard, and proposed a heuristic algorithm which applies the minimum spanning tree and the minimal-cost T-join algorithms. (Corberán, Plana, Rodríguez-Chía and Sanchis, Math. Program. 141 (2013) 21–48) presented an integer programming formulation and a branch-and-cut algorithm for MBCPP without the assumption on the benefits. This is based on the idea of integrating the benefits of each edge into two benefits, each representing that the edge is traversed an odd or even number of times. In this paper, by applying the idea of Corberán et al., we improve the heuristic algorithm of Pearn and Wang. Our algorithm applies to the general case with no assumption on the benefits, and can perform better even if the benefits are non-increasing. We then analyze the efficiency of our heuristic algorithm in theory and in practice, and prove that it finds the optimal solution when the benefits satisfy a certain property. [ABSTRACT FROM AUTHOR]

The input to a PPNC instance is integers n and p , and a non-negative real weighting of the edges of the clique K n on the vertex set {1,..., n }. We are asked to find a set of p disjoint cycles spanning {1,..., n } and subject to this such that the sum of the weights of the edges is minimized. We provide an efficient approximation algorithm for the metric version of this problem which has an approximation ratio of 4 if p ≤ n/5 and an approximation ratio of 51 for larger p. For p > n/5, our algorithm uses a subroutine which approximately solves the Mod 3 T -join With Slack problem. The input to an instance of Mod k T -join with Slack consists of integers n and B , a non-negative weighting of the edges of the clique K n , and a label l(v) from {0,1,..., k - 1} on each vertex of K n. We are asked to find the minimum weight spanning forest F from amongst those satisfying ∑ T∈F ((∑ v∈V(T) l(v)) mod k) ≤ B. If k = 2 and B = 0 this is the well-studied T -join problem which can be solved exactly in polynomial time. [ABSTRACT FROM AUTHOR]

An odd graph is a graph whose vertex degrees are all odd. As introduced by Pyber in 1991, an odd edge‐covering of graph G is a family of odd subgraphs that cover its edges. The minimum size of such family is denoted by covo(G). Answering a question raised by Pyber, Mátrai proved in 2006 that covo(G)≤3 for every simple graph G. In this study, we characterize the same inequality for the class of loopless graphs by proving that, apart from four particular types of loopless graphs on three vertices, every other connected loopless graph admits an odd 3‐edge‐covering. Moreover, there exists such an edge‐covering with at most two edges belonging to more than one subgraph and no edge to all three subgraphs. The latter part of this result implies an interesting consequence for the related notion of odd 3‐edge‐colorability. Our characterization presents a parity counterpart to the characterization of Matthews from 1978 concerning coverability of graph by three even subgraphs. [ABSTRACT FROM AUTHOR]

A graph is even (resp. odd) if all its vertex degrees are even (resp. odd). We consider edge coverings by prescribed number of even and/or odd subgraphs. In view of the 8-Flow Theorem, a graph admits a covering by three even subgraphs if and only if it is bridgeless. Coverability by three odd subgraphs has been characterized recently [Petruševski, M.; Škrekovski, R. Coverability of graph by three odd subgraphs. J. Graph Theory 2019, 92, 304–321]. It is not hard to argue that every acyclic graph can be decomposed into two odd subgraphs, which implies that every graph admits a decomposition into two odd subgraphs and one even subgraph. Here, we prove that every 3-edge-connected graph is coverable by two even subgraphs and one odd subgraph. The result is sharp in terms of edge-connectivity. We also discuss coverability by more than three parity regular subgraphs, and prove that it can be efficiently decided whether a given instance of such covering exists. Moreover, we deduce here a polynomial time algorithm which determines whether a given set of edges extends to an odd subgraph. Finally, we share some thoughts on coverability by two subgraphs and conclude with two conjectures.

We consider the s-t-path TSP: given a finite metric space with two elements s and t, we look for a path from s to t that contains all the elements and has minimum total distance. We improve the approximation ratio for this problem from 1.599 to 1.566. Like previous algorithms, we solve the natural LP relaxation and represent an optimum solution x∗ as a convex combination of spanning trees. Gao showed that there exists a spanning tree in the support of x∗ that has only one edge in each narrow cut [i.e., each cut C with x∗(C)<2]. Our main theorem says that the spanning trees in the convex combination can be chosen such that many of them are such “Gao trees” simultaneously at all sufficiently narrow cuts. [ABSTRACT FROM AUTHOR]

Given an edge-weighted undirected hypergraph and an even-sized set of vertices , a T-cut is a partition of into two parts and such that is odd. A T-join in for is a set of hyperedges such that for every T-cut there is a hyperedge intersecting both and . A directed hypergraph has for every hyperedge exactly one vertex, called the head, and several vertices, that are tails. A directed hypergraph is strongly connected if there exists at least one directed path between any two vertices of the hypergraph, where a directed path is defined to be a sequence of vertices and hyperedges for which each hyperedge has as one of its tails the vertex preceding it and as its head the vertex following it in the sequence. Orienting an undirected hypergraph means choosing a head for each hyperedge. We prove that every edge-weighted undirected hypergraph that admits a strongly connected orientation has a T-join of total weight at most times the total weight of all the edges of the hypergraph, and sketch an improvement to . We also exhibit a series of example showing that one cannot improve the constant above to . [ABSTRACT FROM AUTHOR]

The max-cut problem asks for partitioning the nodes V of a graph G=( V, E) into two sets (one of which might be empty), such that the sum of weights of edges joining nodes in different partitions is maximum. Whereas for general instances the max-cut problem is NP-hard, it is polynomially solvable for certain classes of graphs. For planar graphs, there exist several polynomial-time methods determining maximum cuts for arbitrary choice of edge weights. Typically, the problem is solved by computing a minimum-weight perfect matching in some associated graph. The most efficient known algorithms are those of Shih et al. (IEEE Trans. Comput. 39(5):694-697, ) and that of Berman et al. (WADS, Lecture Notes in Computer Science, vol. 1663, pp. 25-36, Springer, Berlin, ). The running time of the former can be bounded by $O(|V|^{\frac{3}{2}}\log|V|)$. The latter algorithm is more generally for determining T-joins in graphs. Although it has a slightly larger bound on the running time of $O(|V|^{\frac{3}{2}}(\log|V|)^{\frac{3}{2}})\alpha(|V|)$, where α(| V|) is the inverse Ackermann function, it can solve large instances in practice. In this work, we present a new and simple algorithm for determining maximum cuts for arbitrary weighted planar graphs. Its running time is bounded by $O(|V|^{\frac{3}{2}}\log|V|)$, the same bound achieved by Shih et al. It can easily determine maximum cuts in huge random as well as real-world graphs with up to 10 nodes. We present experimental results for our method using two different matching implementations. We furthermore compare our approach with those of Shih et al. and Berman et al. It turns out that our algorithm is considerably faster in practice than Shih et al. Moreover, it yields a much smaller associated graph. Its expanded graph size is comparable to that of Berman et al. However, whereas the procedure of generating the expanded graph in Berman et al. is very involved (thus needs a sophisticated implementation), implementing our approach is an easy and straightforward task. [ABSTRACT FROM AUTHOR]

Strong product G1⊠ G2 of two graphs G1 and G2 has a vertex set V(G1)×V(G2) and two vertices (u1, v1) and (u2, v2) are adjacent whenever u1=u2 and v1 is adjacent to v2 or u1 is adjacent to u2 and v1=v2, or u1 is adjacent to u2 and v1 is adjacent to v2. We investigate the factor-criticality of G1⊠ G2 and obtain the following. Let G1 and G2 be connected m-factor-critical and n-factor-critical graphs, respectively. Then if m≥ 0, n=0, |V(G1)|≥ 2m+2 and |V(G2)|≥ 4, then G1⊠ G2 is (2m+2)-factor-critical; if n=1, |V(G1)|≥ 2m+3 and either m≥ 3 or |V(G2)|≥ 5, then G1⊠ G2 is (2m+4-ε)-factor-critical, where ε=0 if m is even, otherwise ε=1; if m+2 ≤ |V(G1)|≤ 2m+2, or n+2≤ |V(G2)|≤ 2n+2, then G1⊠ G2 is mn-factor-critical; if |V(G1)|≥ 2m+3 and |V(G2)|≥ 2n+3, then G1⊠ G2 is (mn-min{[3m/2]2, [3n/2]2})-factor-critical. [ABSTRACT FROM AUTHOR]

Lexicographic product G ∘ H of two graphs G and H has vertex set V (G) x V (H) and two vertices (u1; v1) and (u2; v2) are adjacent whenever u1u2 ∊ E(G), or u1 = u2 and v1v2 ∊ E(H). If every matching of G of size k can be extended to a perfect matching in G, then G is called k-extendable. In this paper, we study matching extendability in lexicographic product of graphs. The main result is that the lexicographic product of an m-extendable graph and an n-extendable graph is (m + 1)(n + 1)-extendable. In fact, we prove a slightly stronger result. [ABSTRACT FROM AUTHOR]

We study generators of metric spaces--sets of points with the property that every point of the space is uniquely determined by the distances from their elements. Such generators put a light on seemingly different kinds of problems in combinatorics that are not directly related to metric spaces. The two applications we present concern combinatorial search: problems on false coins known from the borderline of extremal combinatorics and information theory; and a problem known from combinatorial optimization --connected joins in graphs. We use results on the detection of false coins to approximate the metric dimension (minimum size of a generator for the metric space defined by the distances) of some particular graphs for which the problem was known and open. In the opposite direction, using metric generators, we show that the existence of connected joins in graphs can be solved in polynomial time, a problem asked in a survey paper of Frank. On the negative side we prove that the minimization of the number of components of a join is NP-hard. We further explore the metric dimension with some problems.The main problem we are led to is how to extend an isometry given on a metric generator of a metric space. [ABSTRACT FROM AUTHOR]