We address the following general question: given a graph class C on which we can solve Maximum Matching in (quasi) linear time, does the same hold true for the class of graphs that can be modularly decomposed into C ? A major difficulty in this task is that the Maximum Matching problem is not preserved by quotient, thereby making difficult to exploit the structural properties of the quotient subgraphs of the modular decomposition. So far, we are only aware of a recent framework in [, SODA'18] that only applies when the quotient subgraphs have bounded order and or under additional assumptions on the nontriv-ial modules in the graph. As a first attempt toward improving this framework we study the combined effect of modular decomposition with a pruning process over the quotient subgraphs. More precisely, we remove sequentially from all such subgraphs their so-called one-vertex extensions (i.e., pendant, anti-pendant, twin, universal and isolated vertices). Doing so, we obtain a "pruned modular decomposition", that can be computed in O(m log n)-time. Our main result is that if all the pruned quotient subgraphs have bounded order then a maximum matching can be computed in linear time. This result is mostly based on two pruning rules on pendant and anti-pendant modules -- that are adjacent, respectively, to one or all but one other modules in the graph. Furthermore, these two latter rules are surprisingly intricate and we consider them as our main technical contribution in the paper. We stress that the class of graphs that can be totally decomposed by the pruned modular decomposition contains all the distance-hereditary graphs, and so, it is larger than cographs. In particular, as a byproduct of our approach we also obtain the first known linear-time algorithms for Maximum Matching on distance-hereditary graphs and graphs with modular-treewidth at most one. Finally, we can use an extended version of our framework in order to compute a maximum matching, in linear-time, for all graph classes that can be modularly decomposed into cycles. Our work is the first to explain why the existence of some nice ordering over the modules of a graph, instead of just over its vertices, can help to speed up the computation of maximum matchings on some graph classes.
A cornerstone of most Maximum Matching algorithms is the notion of augmenting paths @cite_40 @cite_31 . -- See @cite_50 @cite_6 @cite_34 for some other approaches based on matrix multiplication. -- Roughly, given some matching @math in a graph, an @math -augmenting path is a simple path between two exposed vertices ( i.e. , not part of @math ) in which the edges belong alternatively to @math and not to @math . The symmetric difference between @math and any @math -augmenting path leads to a new matching of greater cardinality @math . Therefore, the standard strategy in order to solve Maximum Matching is to repeatedly compute a set of vertex-disjoint augmenting paths (w.r.t. the current matching) until no more such path can be found. However, although we can compute a set of augmenting paths in linear-time @cite_43 , this is a tedious task that involves the technical notion of blossoms and this may need to be repeated @math times before a maximum matching can be computed @cite_37 . One way to circumvent this issue for a specific graph class is to use the structural properties of this class in order to compute the augmenting paths more efficiently.
@cite_37 @cite_6 @cite_43 @cite_40 @cite_50 @cite_31 @cite_34
2157529519 15553240 2030776771 2048652909 2962968573 2610479830
The present paper shows how to construct a maximum matching in a bipartite graph with n vertices and m edges in a number of computation steps proportional to @math . A magnet system for sealing devices for artificial or natural intestinal or similar ducts, comprising a ring-magnet to implant in the tissue around the duct and a rod-shaped center magnet member mounted in a more or less soft sealing member to be in sealing contact with the walls of the duct. The improvement is that the center magnet member comprises at least two, in practice usually two or three, axial aligned individual magnets acting together so as to resist axial displacement; the individual poles are positioned to resist tilting of the center magnet member relative the axis of the duct and the ring-shaped magnet member. This paper presents a linear-time algorithm for the special case of the disjoint set union problem in which the structure of the unions (defined by a “union tree”) is known in advance. The algorithm executes an intermixed sequence of m union and find operations on n elements in 0( m + n ) time and 0( n ) space. This is a slight but theoretically significant improvement over the fastest known algorithm for the general problem, which runs in 0( m α( m + n, n )+ n ) time and 0( n ) space, where α is a functional inverse of Ackermann's function. Used as a subroutine, the algorithm gives similar improvements in the efficiency of algorithms for solving a number of other problems, including two-processor scheduling, the off-line min problem, matching on convex graphs, finding nearest common ancestors off-line, testing a flow graph for reducibility, and finding two disjoint directed spanning trees. The algorithm obtains its efficiency by combining a fast algorithm for the general problem with table look-up on small sets, and requires a random access machine for its implementation. The algorithm extends to the case in which single-node additions to the union tree are allowed. The extended algorithm is useful in finding maximum cardinality matchings on nonbipartite graphs. We investigate the complexity of several fundamental polynomial-time solvable problems on graphs and on matrices, when the given instance has low treewidth; in the case of matrices, we consider the treewidth of the graph formed by non-zero entries. In each of the considered cases, the best known algorithms working on general graphs run in polynomial, but far from linear, time. Thus, our goal is to construct algorithms with running time of the form poly(k)·n or poly(k) · n log n, where k is the width of the tree decomposition given on the input. Such procedures would outperform the best known algorithms for the considered problems already for moderate values of the treewidth, like O(n1 c) for some small constant c. Our results include: -- an algorithm for computing the determinant and the rank of an n × n matrix using O(k3 · n) time and arithmetic operations; -- an algorithm for solving a system of linear equations using O(k3 · n) time and arithmetic operations; -- an O(k3 O n log n)-time randomized algorithm for finding the cardinality of a maximum matching in a graph; -- an O(k4 · n log2 n)-time randomized algorithm for constructing a maximum matching in a graph; -- an O(k2 · n log n)-time algorithm for finding a maximum vertex flow in a directed graph. Moreover, we provide an approximation algorithm for treewidth with time complexity suited to the running times as above. Namely, the algorithm, when given a graph G and integer k, runs in time O(k7 · n log n) and either correctly reports that the treewidth of G is larger than k, or constructs a tree decomposition of G of width O(k2). The above results stand in contrast with the recent work of [SODA 2016], which shows that the existence of algorithms with similar running times is unlikely for the problems of finding the diameter and the radius of a graph of low treewidth. On presente un nouvel algorithme de recherche d'un couplage maximum dans un graphe, qui se ramene essentiellement a l'inversion d'une matrice