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.
For instance, a well-known greedy approach consists in, given some total ordering @math over the vertices in the graph, to consider the exposed vertices @math by increasing order, then to try to match them with some exposed neighbour @math that appears later in the ordering @cite_14 . The candidate vertex @math can be chosen either arbitrarily or according to some specific rules depending on the graph class we consider. On the positive side, variants of the greedy approach have been used in order to compute maximum matchings in quasi linear-time on some graph classes that admit a vertex-ordering characterization, such as: interval graphs @cite_15 , convex bipartite graphs @cite_46 , strongly chordal graphs @cite_21 , cocomparability graphs @cite_53 , etc. But on the negative side, the greedy approach does not look promising for chordal graphs (defined by the existence of a perfect elimination ordering) since computing a maximum matching in a given split graph is already @math -time equivalent to the same problem on general bipartite graphs @cite_21 .
@cite_14 @cite_15 @cite_53 @cite_21 @cite_46
1591789561 2151690061 2605027943 2963014036
In this note a greedy algorithm is considered that computes a matching for a graph with a given ordering of its vertices, and those graphs are studied for which a vertex ordering exists such that the greedy algorithm always yields maximum cardinality matchings for each induced subgraph. We show that these graphs, called greedy matchable graphs, are a subclass of weakly triangulated graphs and contain strongly chordal graphs and chordal bipartite graphs as proper subclasses. The question when can this ordering be produced efficiently is discussed too. The greedy sequential algorithm for maximal independent set (MIS) loops over the vertices in an arbitrary order adding a vertex to the resulting set if and only if no previous neighboring vertex has been added. In this loop, as in many sequential loops, each iterate will only depend on a subset of the previous iterates (i.e. knowing that any one of a vertex's previous neighbors is in the MIS, or knowing that it has no previous neighbors, is sufficient to decide its fate one way or the other). This leads to a dependence structure among the iterates. If this structure is shallow then running the iterates in parallel while respecting the dependencies can lead to an efficient parallel implementation mimicking the sequential algorithm. In this paper, we show that for any graph, and for a random ordering of the vertices, the dependence length of the sequential greedy MIS algorithm is polylogarithmic (O(log^2 n) with high probability). Our results extend previous results that show polylogarithmic bounds only for random graphs. We show similar results for greedy maximal matching (MM). For both problems we describe simple linear-work parallel algorithms based on the approach. The algorithms allow for a smooth tradeoff between more parallelism and reduced work, but always return the same result as the sequential greedy algorithms. We present experimental results that demonstrate efficiency and the tradeoff between work and parallelism. Copyright © 2017, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. Motivated by the fact that in several cases a matching in a graph is stable if and only if it is produced by a greedy algorithm, we study the problem of computing a maximum weight greedy matching on weighted graphs, termed GREEDY-MATCHING. In wide contrast to the maximum weight matching problem, for which many efficient algorithms are known, we prove that GREEDYMATCHING is strongly NP-hard and APX-complete, and thus it does not admit a PTAS unless P=NP, even on graphs with maximum degree at most 3 and with at most three different integer edge weights. Furthermore we prove that GREEDYMATCHING is strongly NP-hard if the input graph is in addition bipartite. Moreover we consider three natural parameters of the problem, for which we establish a sharp threshold behavior between NP-hardness and computational tractability. On the positive side, we present a randomized approximation algorithm (RGMA) for GREEDYMATCHING on a special class of weighted graphs, called bush graphs. We highlight an unexpected connection between RGMA and the approximation of maximum cardinality matching in unweighted graphs via randomized greedy algorithms. We show that, if the approximation ratio of RGMA is θ, then for every ϵ > 0 the randomized MRG algorithm of ( 1995) gives a (ρ - ϵ)-approximation for the maximum cardinality matching. We conjecture that a tight bound for ρ is 2 3; we prove our conjecture true for four subclasses of bush graphs. Proving a tight bound for the approximation ratio of MRG on unweighted graphs (and thus also proving a tight value for ρ) is a long-standing open problem (Poloczek and Szegedy 2012). This unexpected relation of our RGMA algorithm with the MRG algorithm may provide new insights for solving this problem. We introduce a fully online model of maximum cardinality matching in which all vertices arrive online. On the arrival of a vertex, its incident edges to previously-arrived vertices are revealed. Each vertex has a deadline that is after all its neighbors’ arrivals. If a vertex remains unmatched until its deadline, the algorithm must then irrevocably either match it to an unmatched neighbor, or leave it unmatched. The model generalizes the existing one-sided online model and is motivated by applications including ride-sharing platforms, real-estate agency, etc. We show that the Ranking algorithm by (STOC 1990) is 0.5211-competitive in our fully online model for general graphs. Our analysis brings a novel charging mechanic into the randomized primal dual technique by (SODA 2013), allowing a vertex other than the two endpoints of a matched edge to share the gain. To our knowledge, this is the first analysis of Ranking that beats 0.5 on general graphs in an online matching problem, a first step towards solving the open problem by (STOC 1990) about the optimality of Ranking on general graphs. If the graph is bipartite, we show that the competitive ratio of Ranking is between 0.5541 and 0.5671. Finally, we prove that the fully online model is strictly harder than the previous model as no online algorithm can be 0.6317