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].
Listing all triangles in an undirected graph is a fundamental graph primitive with numerous applications. It is trivially solvable in time cubic in the number of vertices. It has seen a significant body of work contributing to both theoretical aspects (e.g., lower and upper bounds on running time, adaption to new computational models) as well as practical aspects (e.g. algorithms tuned for large graphs). Motivated by the fact that the worst-case running time is cubic, we perform a systematic parameterized complexity study of triangle enumeration, providing both positive results (new enumerative kernelizations, “subcubic” parameterized solving algorithms) as well as negative results (uselessness in terms of possibility of “faster” parameterized algorithms of certain parameters such as diameter). We show that the eccentricity of every vertex in an undirected graph on n vertices can be computed in time n exp O(k*log(d)), where k is the treewidth of the graph and d is the diameter. This means that the diameter and the radius of the graph can be computed in the same time. In particular, if the diameter is constant, it can be determined in time n*exp(O(k)). This result matches a recent hardness result by Abboud, Vassilevska Williams, and Wang [SODA 2016] that shows that under the Strong Exponential Time Hypothesis of Impagliazzo, Paturi, and Zane [J. Comp. Syst. Sc., 2001], for any epsilon > 0, no algorithm with running time n^ 2-epsilon *exp(o(k)) can distinguish between graphs with diameter 2 and 3. There are many classical problems in P whose time complexities have not been improved over the past decades. Recent studies of "Hardness in P" have revealed that, for several of such problems, the current fastest algorithm is the best possible under some complexity assumptions. To bypass this difficulty, (SODA 2017) introduced the concept of fully polynomial FPT algorithms. For a problem with the current best time complexity @math , the goal is to design an algorithm running in @math time for a parameter @math and a constant @math . In this paper, we investigate the complexity of graph problems in P parameterized by tree-depth, a graph parameter related to tree-width. We show that a simple divide-and-conquer method can solve many graph problems, including Weighted Matching, Negative Cycle Detection, Minimum Weight Cycle, Replacement Paths, and 2-hop Cover, in @math time or @math time, where @math is the tree-depth of the input graph. Because any graph of tree-width @math has tree-depth at most @math , our algorithms also run in @math time or @math time. These results match or improve the previous best algorithms parameterized by tree-width. Especially, we solve an open problem of fully polynomial FPT algorithm for Weighted Matching parameterized by tree-width posed by 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). Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph primitives. For m-edge and n-vertex graphs, it is well-known to be solvable in O(m n ) time; however, for several applications this running time is still too slow. We investigate how linear-time (and almost linear-time) data reduction (used as preprocessing) can alleviate the situation. More specifically, we focus on linear-time kernelization. We start a deeper and systematic study both for general graphs and for bipartite graphs. Our data reduction algorithms easily comply (in form of preprocessing) with every solution strategy (exact, approximate, heuristic), thus making them attractive in various settings. 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.  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. Hyperbolicity measures, in terms of (distance) metrics, how close a given graph is to being a tree. Due to its relevance in modeling real-world networks, hyperbolicity has seen intensive research over the last years. Unfortunately, the best known practical algorithms for computing the hyperbolicity number of a n-vertex graph have running time (O(n^4) ). Exploiting the framework of parameterized complexity analysis, we explore possibilities for “linear-time FPT” algorithms to compute hyperbolicity. For instance, we show that hyperbolicity can be computed in time (2^ O(k) + O(n +m) ) (m being the number of graph edges, k being the size of a vertex cover) while at the same time, unless the SETH fails, there is no (2^ o(k) n^2 )-time algorithm. 