We present a quasi linear-time algorithm for Maximum Matching on distance-hereditary graphs and some of their generalizations. This improves on [Dragan, WG'97], who proposed such an algorithm for the subclass of (tent,hexahedron)-free distance-hereditary graphs. Furthermore, our result is derived from a more general one that is obtained for b-Matching. In the (unit cost) b-Matching problem, we are given a graph G = (V, E) together with a nonnegative integer capacity b v for every vertex v ∈ V. The objective is to assign nonnegative integer weights (x e) e∈E so that: for every v ∈ V the sum of the weights of its incident edges does not exceed b v , and e∈E x e is maximized. We present the first algorithm for solving b-Matching on cographs, distance-hereditary graphs and some of their generalizations in quasi linear time. For that, we use a decomposition algorithm that outputs for any graph G a collection of subgraphs of G with no edge-cutsets inducing a complete bipartite subgraph (a.k.a., splits). The latter collection is sometimes called a split decomposition of G. Furthermore, there exists a generic method in order to design graph algorithms based on split decomposition [Rao, DAM'08]. However, this technique only applies to " localized " problems: for which a " best " partial solution for any given subgraph in a split decomposition can be computed almost independently from the remaining of the graph. Such framework does not apply to matching problems since an augmenting path may cross the subgraphs arbitrarily. We introduce a new technique that somehow captures all the partial solutions for a given union of subgraphs in a split decomposition, in a compact and amenable way for algorithms — assuming some piecewise linear assumption holds on the value of such solutions. The latter assumption is shown to hold for b-Matching. Doing so, we prove that solving b-Matching on any pair G, b can be reduced in quasi linear-time to solving this problem on a collection of smaller graphs: that are obtained from the subgraphs in any split decomposition of G by replacing every vertex with a constant-size module. In particular, if G has a split decomposition where all subgraphs have order at most a fixed k, then we can solve b-Matching for G, b in O((k log 2 k)·(m+n)·log ||b|| 1)-time. This answers an open question of [, SODA'18].
There is a long line of work whose aim is to find more efficiently solvable special cases for Maximum Matching ( e.g. , see @cite_38 @cite_16 @cite_9 @cite_37 @cite_2 @cite_41 @cite_31 @cite_17 @cite_48 @cite_42 @cite_27 @cite_29 @cite_4 ). In particular, there exist linear-time algorithms for computing a maximum matching on trees, cographs @cite_27 and subclasses of distance-hereditary graphs @cite_9 We stress that the work in @cite_9 is focused on a generic method in order to compute maximum matchings. In particular, the complexity of Maximum Matching on general distance-hereditary graphs is not considered. . Furthermore, a natural follow-up of such investigations is to study whether the techniques used in every case can also be applied to larger classes of graphs. This has be done, especially, for the Split & Match technique introduced in @cite_27 for cographs ( e.g. , see @cite_0 @cite_37 @cite_2 where the latter technique has been applied to other graph classes). We also consider this above aspect in our work, as we seek for a Maximum Matching algorithm on distance-hereditary graphs that can be easily generalized to larger classes of graphs that we define in what follows.
@cite_38 @cite_37 @cite_4 @cite_41 @cite_48 @cite_9 @cite_42 @cite_29 @cite_0 @cite_27 @cite_2 @cite_31 @cite_16 @cite_17
2062510888 2108763491 2031966632 2605350614 1591789561 2083116175 2091660728 2949142592 1966596093 2026807383 2157529519 2065410741 2144795927
Abstract The P 4 -tidy graphs were introduced by I. Rusu to generalize some already known classes of graphs with “few” induced P 4 s. In this paper, we extend to P 4 -tidy graphs a linear time algorithm of C.-H. Yang and M.-S. Yu for finding a maximum matching in a cograph G (given a parse tree associated to G ). We present an O(n 2logn)-time algorithm that finds a maximum matching in a regular graph with n vertices. More generally, the algorithm runs in O(rn 2logn) time if the difference between the maximum degree and the minimum degree is less than r. This running time is faster than applying the fastest known general matching algorithm that runs in (O( n m) )-time for graphs with m edges, whenever m=ω(rn 1.5logn). A special matching problem arising in industry is shown to be solvable by an algorithm of the form: match objects ai and bj if they satisfy a local optirnality criterion based on a ranking of currently unmatched objects. When no ai and bi remain that can be matched, the largest number of acceptable matches has been found. Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph problems. For general m-edge and n-vertex graphs, it is well-known to be solvable in @math time. We develop a linear-time algorithm to find maximum-cardinality matchings on cocomparability graphs, a prominent subclass of perfect graphs that contains interval graphs as well as permutation graphs. Our algorithm is based on the recently discovered Lexicographic Depth First Search (LDFS). 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. We present a new randomized algorithm for finding a maximum matching in H-minor free graphs. For every fixed H, our algorithm runs in O(n3ω (ω+3)) For graphs with bounded genus, which are special cases of H-minor free graphs, we present a randomized algorithm for finding a maximum matching in O(nω 2) We also present a deterministic algorithm with a running time of O(n1+ω 2) Recently, hardness results for problems in P were achieved using reasonable complexity-theoretic assumptions such as the Strong Exponential Time Hypothesis. According to these assumptions, many graph-theoretic problems do not admit truly subquadratic algorithms. A central technique used to tackle the difficulty of the above-mentioned problems is fixed-parameter algorithms with polynomial dependency in the fixed parameter (P-FPT). Applying this technique to clique-width, an important graph parameter, remained to be done. In this article, we study several graph-theoretic problems for which hardness results exist such as cycle problems, distance problems, and maximum matching. We give hardness results and P-FPT algorithms, using clique-width and some of its upper bounds as parameters. We believe that our most important result is an algorithm in O(k4 ⋅ n + m)-time for computing a maximum matching, where k is either the modular-width of the graph or the P4-sparseness. The latter generalizes many algorithms that have been introduced so far for specific subclasses such as cographs. Our algorithms are based on preprocessing methods using modular decomposition and split decomposition. Thus they can also be generalized to some graph classes with unbounded clique-width. Abstract In this paper, we develop a sequential algorithm for the maximum matching problem on cographs. The input is a parse tree of a cograph. The time complexity is O ( n ). We describe here a technique of decomposition of bipartite graphs which seems to be as interesting within this context as the well known modular and split techniques for the decomposition of general graphs. In particular, we characterize by forbidden subgraphs the family of bipartite graphs which are totally decomposable (i.e. reducible to single vertices) with respect to our decomposition. This family contains previously known families of graphs such as bicographs and P6-free bipartite graphs. As an application we provide polynomial solutions of optimization problems, some of them being NP-complete for general bipartite graphs. 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 . Chordal graphs are graphs with the property that each cycle of length greater than 3 has two non-consecutive vertices that are joined by an edge. An important subclass of chordal graphs are strongly chordal graphs (Farber, 1983). Chordal graphs appear for example in the design of acyclic data base schemes (, 1983). In this paper we study the computational complexity (both sequential and parallel) of the maximum matching problem for chordal and strongly chordal graphs. We show that there is a linear-time greedy algorithm for a maximum matching in a strongly chordal graph provided a strongly perfect elimination ordering is known. This algorithm can also be turned into a parallel algorithm. The technique used can also be extended to the perfect multidimensional matching for chordal and strongly chordal graphs yielding the first polynomial time algorithms for these classes of graphs (the multidimensional matching is NP-complete in general). We present an O(n log n) algorithm for finding a maximum matching in a circular-arc graph. The best known algorithm for the same problem in general graphs takes O(√|V||E|) time.