The Weighted Center problem takes as its input a graph G = (V,E) together with a profile π such that every vertex v is mapped to some nonnegative multiplicative weight π(v). Its output must be some vertex c minimizing max{π(v)d_G(c,v) : v ∈ V}. The classic Center problem corresponds to the case where π(v) = 1 for every vertex v. In the literature, various almost linear-time algorithms have been proposed for the Center problem on some well-structured classes of graphs. By contrast, similarly efficient algorithms for the Weighted Center problem have been scarce. We investigate how the Gromov hyperbolicity, alone or in combination with other metric and geometric properties on graphs, can be used in the design of exact and approximate almost linear-time algorithms for the Weighted Center problem. In particular, we derive almost optimal algorithms for the following well-studied classes of graphs: chordal graphs, distance-hereditary graphs (both in 𝒪(m) time), dually chordal graphs and chordal bipartite graphs (both in 𝒪(m log n) time).

A vertex in a graph is called central if it minimizes its maximum distance to the other vertices. The radius of a graph G is the largest distance between a central vertex and the other vertices, and it is denoted by rad(G). In the center problem, we are asked to find a central vertex. We study the fine-grained complexity of the center problem on graphs with small Gromov hyperbolicity. Roughly, the Gromov hyperbolicity of a graph represents how close, locally, it is to a tree, from a metric point of view. It has applications in the design of approximation algorithms. In particular, there is a linear-time algorithm that for every δ-hyperbolic graph G outputs some vertex at distance at most rad(G) + 5δ to the other vertices [Chepoi et al, SoCG'08]. However, a linear-time algorithm for computing a central vertex is known only for 0-hyperbolic graphs, whereas its existence was ruled out for 2-hyperbolic graphs under the Hitting Set Conjecture of [Abboud et al, SODA'16]. Our main contribution in the paper is a linear-time algorithm for computing a central vertex in the class of 1/2-hyperbolic graphs. Furthermore, we rule out the existence of such an algorithm for 1-hyperbolic graphs, under the Hitting Set Conjecture, thus completely settling all the cases left open.

Computing the diameter, and more generally, all eccentricities of an undirected graph is an important problem in algorithmic graph theory and the challenge is to identify graph classes for which their computation can be achieved in subquadratic time. Using a new recursive scheme based on the structural properties of median graphs, we provide a quasilinear-time algorithm to determine all eccentricities for this well-known family of graphs. The gist of our technique is to identify the balanced and unbalanced parts of the Θ-class decomposition of median graphs, which are then processed using different recursive schemes. The exact running time of our algorithm is in O (n log4 n ). This outcome not only answers a question asked by Bénéteau et al. (2020) but also greatly improves the recent combinatorial algorithm of Berge et al. (2022) for the same problem, running in time O (n1.6408 logO (1) n ).

In the context of fine-grained complexity, we investigate the notion of certificate enabling faster polynomialtime algorithms. We specifically target radius (minimum eccentricity), diameter (maximum eccentricity), and all-eccentricity computations for which quadratic-time lower bounds are known under plausible conjectures. In each case, we introduce a notion of certificate as a specific set of nodes from which appropriate bounds on all eccentricities can be derived in subquadratic time when this set has sublinear size. The existence of small certificates is a barrier against SETH-based lower bounds for these problems. We indeed prove that for graph classes with small certificates, there exist randomized subquadratic-time algorithms for computing the radius, the diameter, and all eccentricities respectively.

For any set system ℋ = (V,ℛ), ℛ ⊆ 2^V, a subset S ⊆ V is called shattered if every S' ⊆ S results from the intersection of S with some set in ℛ. The VC-dimension of ℋ is the size of a largest shattered set in V. In this paper, we focus on the problem of computing the VC-dimension of graphs. In particular, given a graph G = (V,E), the VC-dimension of G is defined as the VC-dimension of (V, N), where N contains each subset of V that can be obtained as the closed neighborhood of some vertex v ∈ V in G. Our main contribution is an algorithm for computing the VC-dimension of any graph, whose effectiveness is shown through experiments on various types of practical graphs, including graphs with millions of vertices. A key aspect of its efficiency resides in the fact that practical graphs have small VC-dimension, up to 8 in our experiments. As a side-product, we present several new bounds relating the graph VC-dimension to other classical graph theoretical notions. We also establish the W[1]-hardness of the graph VC-dimension problem by extending a previous result for arbitrary set systems.

Abstract We extend known results on chordal graphs and distance-hereditary graphs to much larger graph classes by using only a common metric property of these graphs. Specifically, a graph is called $$\alpha _i$$ α i -metric ( $$i\in {\mathcal {N}}$$ i ∈ N ) if it satisfies the following $$\alpha _i$$ α i -metric property for every vertices u, w, v and x: if a shortest path between u and w and a shortest path between x and v share a terminal edge vw, then $$d(u,x)\ge d(u,v) + d(v,x)-i$$ d ( u , x ) ≥ d ( u , v ) + d ( v , x ) - i . Roughly, gluing together any two shortest paths along a common terminal edge may not necessarily result in a shortest path but yields a “near-shortest” path with defect at most i. It is known that $$\alpha _0$$ α 0 -metric graphs are exactly ptolemaic graphs, and that chordal graphs and distance-hereditary graphs are $$\alpha _i$$ α i -metric for $$i=1$$ i = 1 and $$i=2$$ i = 2 , respectively. We show that an additive O(i)-approximation of the radius, of the diameter, and in fact of all vertex eccentricities of an $$\alpha _i$$ α i -metric graph can be computed in total linear time. Our strongest results are obtained for $$\alpha _1$$ α 1 -metric graphs, for which we prove that a central vertex can be computed in subquadratic time, and even better in linear time for so-called $$(\alpha _1,\varDelta )$$ ( α 1 , Δ ) -metric graphs (a superclass of chordal graphs and of plane triangulations with inner vertices of degree at least 7). The latter answers a question raised in Dragan (Inf Probl Lett 154:105873, 2020), 2020). Our algorithms follow from new results on centers and metric intervals of $$\alpha _i$$ α i -metric graphs. In particular, we prove that the diameter of the center is at most $$3i+2$$ 3 i + 2 (at most 3, if $$i=1$$ i = 1 ). The latter partly answers a question raised in Yushmanov and Chepoi (Math Probl Cybernet 3:217–232, 1991).

Abstract Let be a graph with unit‐length edges and nonnegative costs assigned to its vertices. Given a list of pairwise different vertices , the prioritized Voronoi diagram of with respect to is the partition of in subsets so that, for every with , a vertex is in if and only if is a closest vertex to in and there is no closest vertex to in within the subset . For every with , the load of vertex equals the sum of the costs of all vertices in . The load of equals the maximum load of a vertex in . We study the problem of adding one more vertex at the end of in order to minimize the load. This problem occurs in the context of optimally locating a new service facility (e.g., a school or a hospital) while taking into account already existing facilities, and with the goal of minimizing the maximum congestion at a site. There is a brute‐force algorithm for solving this problem in time on ‐vertex ‐edge graphs. We prove a matching time lower bound–up to sub‐polynomial factors–for the special case where and , assuming the so called Hitting Set Conjecture of Abboud et al. On the positive side, we present simple linear‐time algorithms for this problem on cliques, paths and cycles, and almost linear‐time algorithms for trees, proper interval graphs and (assuming to be a constant) bounded‐treewidth graphs.

An extremity is a vertex such that the removal of its closed neighbourhood does not increase the number of connected components. Let $Ext_α$ be the class of all connected graphs whose quotient graph obtained from modular decomposition contains no more than $α$ pairwise nonadjacent extremities. Our main contributions are as follows. First, we prove that the diameter of every $m$-edge graph in $Ext_α$ can be computed in deterministic ${\cal O}(α^3 m^{3/2})$ time. We then improve the runtime to linear for all graphs with bounded clique-number. Furthermore, we can compute an additive $+1$-approximation of all vertex eccentricities in deterministic ${\cal O}(α^2 m)$ time. This is in sharp contrast with general $m$-edge graphs for which, under the Strong Exponential Time Hypothesis (SETH), one cannot compute the diameter in ${\cal O}(m^{2-ε})$ time for any $ε> 0$. As important special cases of our main result, we derive an ${\cal O}(m^{3/2})$-time algorithm for exact diameter computation within dominating pair graphs of diameter at least six, and an ${\cal O}(k^3m^{3/2})$-time algorithm for this problem on graphs of asteroidal number at most $k$. We end up presenting an improved algorithm for chordal graphs of bounded asteroidal number, and a partial extension of our results to the larger class of all graphs with a dominating target of bounded cardinality. Our time upper bounds in the paper are shown to be essentially optimal under plausible complexity assumptions.

International audience

Abstract. Under the strong exponential-time hypothesis, the diameter of general unweighted graphs cannot be computed in truly subquadratic time (in the size [Formula: see text] of the input), as shown by Roditty and Williams. Nevertheless there are several graph classes for which this can be done such as bounded-treewidth graphs, interval graphs, and planar graphs, to name a few. We propose to study unweighted graphs of constant distance Vapnik–Chervonenkis (VC)-dimension as a broad generalization of many such classes—where the distance VC-dimension of a graph [Formula: see text] is defined as the VC-dimension of its ball hypergraph whose hyperedges are the balls of all possible radii and centers in [Formula: see text]. In particular for any fixed [Formula: see text], the class of [Formula: see text]-minor free graphs has distance VC-dimension at most [Formula: see text]. Our first main result is a Monte Carlo algorithm that on graphs of distance VC-dimension at most [Formula: see text], for any fixed [Formula: see text], either computes the diameter or concludes that it is larger than [Formula: see text] in time [Formula: see text], where [Formula: see text] only depends on [Formula: see text] and the [Formula: see text] notation suppresses polylogarithmic factors. We thus obtain a truly subquadratic-time parameterized algorithm for computing the diameter on such graphs. Then as a byproduct of our approach, we get a truly subquadratic-time randomized algorithm for constant diameter computation on all the nowhere dense graph classes. The latter classes include all proper minor-closed graph classes, bounded-degree graphs, and graphs of bounded expansion. Before our work, the only known such algorithm was resulting from an application of Courcelle’s theorem; see Grohe, Kreutzer, and Siebertz [ J. ACM, 64 (2017), pp. 1–32]. For any graph of constant distance VC-dimension, we further prove the existence of an exact distance oracle in truly subquadratic space, that answers distance queries in truly sublinear time (in the number [Formula: see text] of vertices). The latter generalizes prior results on proper minor-closed graph classes to a much larger graph class. Finally, we show how to remove the dependency on [Formula: see text] for any graph class that excludes a fixed graph [Formula: see text] as a minor. More generally, our techniques apply to any graph with constant distance VC-dimension and polynomial expansion (or equivalently having strongly sublinear balanced separators). As a result for all such graphs one obtains a truly subquadratic-time deterministic algorithm for computing all the eccentricities, and thus both the diameter and the radius. Our approach can be generalized to the [Formula: see text]-minor free graphs with bounded positive integer weights. We note that all our algorithms for the diameter problem can be adapted for computing the radius, and more generally all the eccentricities. Our approach is based on the work of Chazelle and Welzl who proved the existence of spanning paths with strongly sublinear stabbing number for every hypergraph of constant VC-dimension. We show how to compute such paths efficiently by combining known algorithms for the stabbing number problem with a clever use of [Formula: see text]-nets, region decomposition, and other partition techniques.

Recently, independent groups of researchers have presented algorithms to compute a maximum matching in Õ(f(k) ⋅ (n+m)) time, for some computable function f, within the graphs where some clique-width upper bound is at most k (e.g., tree-width, modular-width and P₄-sparseness). However, to the best of our knowledge, the existence of such algorithm within the graphs of bounded clique-width has remained open until this paper. Indeed, we cannot even apply Courcelle’s theorem to this problem directly, because a matching cannot be expressed in MSO₁ logic. Our first contribution is an almost linear-time algorithm to compute a maximum matching in any bounded clique-width graph, being given a corresponding clique-width expression. It can be used to also compute the Edmonds-Gallai decomposition. For that, we do apply Courcelle’s theorem, but in order to compute the cardinality of a maximum matching rather than the matching itself, via the classic Tutte-Berge formula. To obtain with this approach a maximum matching, we need to combine it with a recursive dissection scheme for bounded clique-width graphs based on the existence of balanced edge-cuts with bounded neighbourhood diversity, and with a distributed version of Courcelle’s theorem (Courcelle and Vanicat, DAM 2016) - of which we present here a slightly stronger version than the standard one in the literature - in order to evaluate the Tutte-Berge formula on various subgraphs of the input. Finally, for the bipartite graphs of clique-width at most k, we present an alternative Õ(k²⋅(n+m))-time algorithm for the problem. The algorithm is randomized and it is based on a completely different approach than above: combining various reductions to matching and flow problems on bounded tree-width graphs with a very recent result on the parameterized complexity of linear programming (Dong et. al., STOC'21). Our results for bounded clique-width graphs extend many prior works on the complexity of Maximum Matching within cographs, distance-hereditary graphs, series-parallel graphs and other subclasses.

Given an n-vertex m-edge graph G of clique-width at most k, and a corresponding k-expression, we present algorithms for computing some well-known centrality indices (eccentricity and closeness) that run in O(2^{O(k)}(n+m)^{1+ε}) time for any ε > 0. Doing so, we can solve various distance problems within the same amount of time, including: the diameter, the center, the Wiener index and the median set. Our run-times match conditional lower bounds of Coudert et al. (SODA'18) under the Strong Exponential-Time Hypothesis. On our way, we get a distance-labeling scheme for n-vertex m-edge graphs of clique-width at most k, using O(klog²{n}) bits per vertex and constructible in Õ(k(n+m)) time from a given k-expression. Doing so, we match the label size obtained by Courcelle and Vanicat (DAM 2016), while we considerably improve the dependency on k in their scheme. As a corollary, we get an Õ(kn²)-time algorithm for computing All-Pairs Shortest-Paths on n-vertex graphs of clique-width at most k, being given a k-expression. This partially answers an open question of Kratsch and Nelles (STACS'20). Our algorithms work for graphs with non-negative vertex-weights, under two different types of distances studied in the literature. For that, we introduce a new type of orthogonal range query as a side contribution of this work, that might be of independent interest.

The length of a tree-decomposition of a graph is the maximum distance between two vertices of a same bag of the decomposition. The treelength of a graph is the minimum length among its tree-decompositions. Treelength of graphs has been studied for its algorithmic applications in classical metric problems such as Traveling Salesman Problem or metric dimension of graphs and also, in compact routing in the context of distributed computing. Deciding whether the treelength of a general graph is at most 2 is NP-complete (graphs of treelength one are precisely the chordal graphs), and it is known that the treelength of a graph cannot be approximated up to a factor less than 3/2 (the best known approximation algorithm for treelength has an approximation ratio of 3). However, nothing is known on the computational complexity of treelength in planar graphs, except that the treelength of any outerplanar graph is equal to the third of the maximum size of its isometric cycles. This work initiates the study of treelength in planar graphs by considering the next natural superclass of outerplanar graphs, namely the one of series-parallel graphs. We first fully describe the treelength of melon graphs (set of pairwise internally disjoint paths linking two vertices), showing that, even in such a restricted graph class, the expression of the treelength is not trivial. Then, we show that treelength can be approximated up to a factor 3/2 in series-parallel graphs. Our main result is a polynomial-time algorithm for deciding whether a series-parallel graph has treelength at most 2. Our latter result relies on a characterization of series-parallel graphs with treelength 2 in terms of infinite families of forbidden isometric subgraphs.

Coudert et al. (SODA'18) proved that under the Strong Exponential-Time Hypothesis, for any $ε>0$, there is no ${\cal O}(2^{o(k)}n^{2-ε})$-time algorithm for computing the diameter within the $n$-vertex cubic graphs of clique-width at most $k$. We present an algorithm which given an $n$-vertex $m$-edge graph $G$ and a $k$-expression, computes all the eccentricities in ${\cal O}(2^{{\cal O}(k)}(n+m)^{1+o(1)})$ time, thus matching their conditional lower bound. It can be modified in order to compute the Wiener index and the median set of $G$ within the same amount of time. On our way, we get a distance-labeling scheme for $n$-vertex $m$-edge graphs of clique-width at most $k$, using ${\cal O}(k\log^2{n})$ bits per vertex and constructible in ${\cal O}(k(n+m)\log{n})$ time from a given $k$-expression. Doing so, we match the label size obtained by Courcelle and Vanicat (DAM 2016), while we considerably improve the dependency on $k$ in their scheme. As a corollary, we get an ${\cal O}(kn^2\log{n})$-time algorithm for computing All-Pairs Shortest-Paths on $n$-vertex graphs of clique-width at most $k$. This partially answers an open question of Kratsch and Nelles (STACS'20).

The Wiener index of a graph G is the sum of all its distances. Up to renormalization, it is also the average distance in G. The problem of computing this parameter has different applications in chemistry and networks. We here study when it can be done in truly subquadratic time (in the size n+m of the input) on n-vertex m-edge graphs. Our main result is a complete answer to this question, assuming the Strong Exponential-Time Hypothesis (SETH), for all the hereditary subclasses of chordal graphs. Interestingly, the exact same result also holds for the diameter problem. The case of non-hereditary chordal subclasses happens to be more challenging. For the chordal Helly graphs we propose an intricate Õ(m^{3/2})-time algorithm for computing the Wiener index, where m denotes the number of edges. We complete our results with the first known linear-time algorithm for this problem on the dually chordal graphs. The former algorithm also computes the median set.

Abstract We present new algorithmic results for the class of Helly graphs, that is, for the discrete analogues of hyperconvex metric spaces. Specifically, an undirected unweighted graph is Helly if every family of pairwise intersecting balls has a nonempty common intersection. It is known that every graph isometrically embeds into a Helly graph that makes of the latter an important class of graphs in metric graph theory. We study diameter and radius computations within the Helly graphs, and related graph classes. This is in part motivated by a conjecture on the fine‐grained complexity of these two distance problems within the graph classes of bounded fractional Helly number—that contain as particular cases the proper minor‐closed graph classes and the bounded clique‐width graphs. Note that under plausible complexity assumptions, neither the diameter nor the radius can be computed in truly subquadratic time on general graphs. In contrast to these negative results, we first present algorithms which given an n‐vertex m‐edge Helly graph G as input, compute with high probability (w.h.p.) its radius and its diameter in time (i.e., subquadratic in n + m). Our algorithms are based on the Helly property and on the unimodality of the eccentricity function in Helly graphs: every vertex of locally minimum eccentricity is a central vertex. Then, we improve our results for the C4‐free Helly graphs, that are exactly the Helly graphs whose balls are convex. For this subclass, we present linear‐time algorithms for computing the eccentricity of all vertices. Doing so, we generalize previous results on strongly chordal graphs to a much larger subclass, that includes, among others, all the bridged Helly graphs and the hereditary Helly graphs. Lastly, we derive approximate versions of our results for the class of chordal graphs: with the latter satisfying an almost‐Helly‐type property, and a stronger (induced‐path) convexity property than the C4‐free Helly graphs. For the chordal graphs, we can compute in quasi linear time the eccentricity of all vertices with an additive one‐sided error of at most one, which is best possible under the strong exponential‐time hypothesis. This answers an open question of Dragan. In fact, we obtain this last result as a byproduct from a more general reduction: from diameter computation on chordal graphs to the Disjoint Sets problem. Roughly, it implies that the split graphs are the only hard instances for diameter computation on chordal graphs. We also get from our reduction that on any subclass of chordal graphs with constant VC‐dimension (and so, for undirected path graphs), the diameter can be computed in truly subquadratic time.

Given an $n$-vertex $m$-edge graph $G$ with nonnegative edge-weights, a shortest cycle is one minimizing the sum of the weights on its edges. The girth of $G$ is the weight of a shortest cycle. We obtain several new approximation algorithms for computing the girth of weighted graphs: For any graph $G$ with polynomially bounded integer weights, we present a deterministic algorithm that computes, in $\tilde{\cal O}(n^{5/3}+m)$-time, a cycle of weight at most twice the girth of $G$. This matches the approximation factor of the best known subquadratic-time approximation algorithm for the girth of unweighted graphs. Then, we turn our algorithm into a deterministic $(2+\varepsilon)$-approximation for graphs with arbitrary nonnegative edge-weights, at the price of a slightly worse running time in $\tilde{\cal O}(n^{5/3}\text{polylog}{(1/\varepsilon)}+m)$. For that, we introduce a generic method in order to obtain a polynomial-factor approximation of the girth in subquadratic time, that may be of independent interest. Finally, if we assume that the adjacency lists are sorted then we can get rid off the dependency in the number $m$ of edges. Namely, we can transform our algorithms into an $\tilde{\cal O}(n^{5/3})$-time randomized 4-approximation for graphs with nonnegative edge-weights. This can be derandomized, thereby leading to an $\tilde{\cal O}(n^{5/3})$-time deterministic 4-approximation for graphs with polynomially bounded integer weights, and an $\tilde{\cal O}(n^{5/3}\text{polylog}{(1/\varepsilon)})$-time deterministic $(4+\varepsilon)$-approximation for graphs with nonnegative edge-weights. To the best of our knowledge, these are the first known subquadratic-time approximation algorithms for computing the girth of weighted graphs.

Under the Strong Exponential-Time Hypothesis, the diameter of general unweighted graphs cannot be computed in truly subquadratic time. Nevertheless there are several graph classes for which this can be done such as bounded-treewidth graphs, interval graphs and planar graphs, to name a few. We propose to study unweighted graphs of constant distance VC-dimension as a broad generalization of many such classes – where the distance VC-dimension of a graph G is defined as the VC-dimension of its ball hypergraph: whose hyperedges are the balls of all possible radii and centers in G. In particular for any fixed H, the class of H-minor free graphs has distance VC-dimension at most |V(H)| – 1. Our first main result is a Monte Carlo algorithm that on graphs of distance VC-dimension at most d, for any fixed k, either computes the diameter or concludes that it is larger than k in time (k · mn1−εd), where εd ϵ (0; 1) only depends on d. We thus obtain a truly subquadratic-time parameterized algorithm for computing the diameter on such graphs. Then as a byproduct of our approach, we get the first truly subquadratic-time randomized algorithm for constant diameter computation on all the nowhere dense graph classes. The latter classes include all proper minor-closed graph classes, bounded-degree graphs and graphs of bounded expansion. Finally, we show how to remove the dependency on k for any graph class that excludes a fixed graph H as a minor. More generally, our techniques apply to any graph with constant distance VC-dimension and polynomial expansion (or equivalently having strongly sublinear balanced separators). As a result for all such graphs one obtains a truly subquadratic-time randomized algorithm for computing their diameter. We note that all our results also hold for radius computation. Our approach is based on the work of Chazelle and Welzl who proved the existence of spanning paths with strongly sublinear stabbing number for every hypergraph of constant VC-dimension. We show how to compute such paths efficiently by combining known algorithms for the stabbing number problem with a clever use of ε-nets, region decomposition and other partition techniques.

When can we compute the diameter of a graph in quasi linear time? We address this question for the class of split graphs , that we observe to be the hardest instances for deciding whether the diameter is at most two. We stress that although the diameter of a non-complete split graph can only be either 2 or 3, under the Strong Exponential-Time Hypothesis (SETH) we cannot compute the diameter of a split graph in less than quadratic time. Therefore it is worth to study the complexity of diameter computation on subclasses of split graphs, in order to better understand the complexity border. Specifically, we consider the split graphs with bounded clique-interval number and their complements, with the former being a natural variation of the concept of interval number for split graphs that we introduce in this paper. We first discuss the relations between the clique-interval number and other graph invariants and then almost completely settle the complexity of diameter computation on these subclasses of split graphs: For the k -clique-interval split graphs, we can compute their diameter in truly subquadratic time if \(k=\mathcal{O}(1)\) , and even in quasi linear time if \(k=o(\log {n})\) and in addition a corresponding ordering is given. However, under SETH this cannot be done in truly subquadratic time for any \(k = \omega (\log {n})\) . For the complements of k -clique-interval split graphs, we can compute their diameter in truly subquadratic time if \(k=\mathcal{O}(1)\) , and even in time \(\mathcal{O}(km)\) if a corresponding ordering is given. Again this latter result is optimal under SETH up to polylogarithmic factors. Our findings raise the question whether a k -clique interval ordering can always be computed in quasi linear time. We prove that it is the case for \(k=1\) and for some subclasses such as bounded-treewidth split graphs, threshold graphs and comparability split graphs. Finally, we prove that some important subclasses of split graphs – including the ones mentioned above – have a bounded clique-interval number. A research report version is deposited on HAL repository with number hal-02307397.

We consider a community formation problem in social networks, where the users are either friends or enemies. The users are partitioned into conflict-free groups (i.e., independent sets in the conflict graph G^- =(V,E) that represents the enmities between users). The dynamics goes on as long as there exists any set of at most k users, k being any fixed parameter, that can change their current groups in the partition simultaneously, in such a way that they all strictly increase their utilities (number of friends i.e., the cardinality of their respective groups minus one). Previously, the best-known upper-bounds on the maximum time of convergence were O(|V|alpha(G^-)) for k <= 2 and O(|V|^3) for k=3, with alpha(G^-) being the independence number of G^-. Our first contribution in this paper consists in reinterpreting the initial problem as the study of a dominance ordering over the vectors of integer partitions. With this approach, we obtain for k <= 2 the tight upper-bound O(|V| min {alpha(G^-), sqrt{|V|}}) and, when G^- is the empty graph, the exact value of order ((2|V|)^{3/2})/3. The time of convergence, for any fixed k >= 4, was conjectured to be polynomial [Escoffier et al., 2012][Kleinberg and Ligett, 2013]. In this paper we disprove this. Specifically, we prove that for any k >= 4, the maximum time of convergence is an Omega(|V|^{Theta(log{|V|})}).

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 ( k 4 ⋅ n + m )-time for computing a maximum matching, where k is either the modular-width of the graph or the P 4 -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.

In this paper, we study Gromov hyperbolicity and related parameters, that represent how close (locally) a metric space is to a tree from a metric point of view. The study of Gromov hyperbolicity for geodesic metric spaces can be reduced to the study of graph hyperbolicity. Our main contribution in this note is a new characterization of hyperbolicity for graphs (and for complete geodesic metric spaces). This characterization has algorithmic implications in the field of large-scale network analysis, which was one of our initial motivations. A sharp estimate of graph hyperbolicity is useful, {e.g.}, in embedding an undirected graph into hyperbolic space with minimum distortion [Verbeek and Suri, SoCG'14]. The hyperbolicity of a graph can be computed in polynomial-time, however it is unlikely that it can be done in subcubic time. This makes this parameter difficult to compute or to approximate on large graphs. Using our new characterization of graph hyperbolicity, we provide a simple factor 8 approximation algorithm for computing the hyperbolicity of an n-vertex graph G=(V,E) in optimal time O(n^2) (assuming that the input is the distance matrix of the graph). This algorithm leads to constant factor approximations of other graph-parameters related to hyperbolicity (thinness, slimness, and insize). We also present the first efficient algorithms for exact computation of these parameters. All of our algorithms can be used to approximate the hyperbolicity of a geodesic metric space.

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? As a way to answer this question for distance-hereditary graphs and some other superclasses of cographs, we study the combined effect of modular decomposition with a pruning process over the quotient subgraphs. 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 quasi linear 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. The latter result strictly extends a recent framework in (Coudert et al., SODA'18). 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.

We make progress on the fine-grained complexity of Maximum-Cardinality Matching on graphs of bounded clique-width. Quasi linear-time algorithms for this problem have been recently proposed for the important subclasses of bounded-treewidth graphs (Fomin et al., SODA'17) and graphs of bounded modular-width (Coudert et al., SODA'18). We present such algorithm for bounded split-width graphs - a broad generalization of graphs of bounded modular-width, of which an interesting subclass are the distance-hereditary graphs. Specifically, we solve Maximum-Cardinality Matching in O((k log^2{k})*(m+n) * log{n})-time on graphs with split-width at most k. We stress that the existence of such algorithm was not even known for distance-hereditary graphs until our work. Doing so, we improve the state of the art (Dragan, WG'97) and we answer an open question of (Coudert et al., SODA'18). Our work brings more insights on the relationships between matchings and splits, a.k.a., join operations between two vertex-subsets in different connected components. Furthermore, our analysis can be extended to the more general (unit cost) b-Matching problem. On the way, we introduce new tools for b-Matching and dynamic programming over split decompositions, that can be of independent interest.

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 paper 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 O(k4 · n + m)-time algorithm for computing a maximum matching where k is either the modular-width 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 study the complexity of decomposing a graph by means of clique separators. This common algorithmic tool, first introduced by Tarjan, allows one to cut a graph into smaller pieces, and so it can be applied to preprocess the graph in the computation of optimization problems. However, the best-known algorithms for computing a decomposition have respective ${\cal O}(nm)$-time and ${\cal O}(n^{(3+\alpha)/2}) = o(n^{2.69})$-time complexity with $\alpha < 2.3729$ being the exponent for matrix multiplication. Such running times are prohibitive for large graphs. Here we prove that for every graph $G$, a decomposition can be computed in ${\cal O}(T(G) + \min\{n^{\alpha},\omega^2 n\})$-time with $T(G)$ and $\omega$ being, respectively, the time needed to compute a minimal triangulation of $G$ and the clique-number of $G$. In particular, it implies that every graph can be decomposed by clique separators in ${\cal O}(n^{\alpha}\log n)$-time. Based on prior work from Kratsch et al., we prove in addition that decomposing a graph by clique-separators is as least as hard as triangle detection. Therefore, the existence of any $o(n^{\alpha})$-time algorithm for this problem would be a significant breakthrough in the algorithmic field. Finally, our main result implies that planar graphs, bounded-treewidth graphs, and bounded-degree graphs can be decomposed by clique separators in linear or quasi-linear time.

Tree-likeness parameters have proven their utility in the design of efficient algorithms on graphs. In this paper, we relate the structural tree-likeness of graphs with their metric tree-likeness. To this end, we establish new upper bounds on the diameter of minimal separators in graphs. We prove that in any graph $G$, the diameter of any minimal separator $S$ in $G$ is at most $\lfloor \ell(G) / 2\rfloor \cdot (|S|-1)$, with $\ell(G)$ the length of a longest isometric cycle in $G$. Our result relies on algebraic methods and on the cycle basis of graphs. We improve our bound for the graphs admitting a distance preserving elimination ordering, for which we prove that any minimal separator $S$ has diameter at most $2 \cdot (|S|-1)$. We use our results to prove that the treelength $tl(G)$ of any graph $G$ is at most $\lfloor \ell(G) / {2}\rfloor$ times its treewidth $tw(G)$. In addition, we prove that, for any graph $G$ that excludes an apex graph $H$ as a minor, $tw(G) \leq c_H \cdot tl(G)$ for some constant $c_H$ only depending on $H$. We refine this constant when $G$ has bounded genus. Altogether, we obtain a simple $\mathcal{O} (\ell(G))$-approximation algorithm for computing the treewidth of $n$-node apex-minor-free graphs in $\mathcal{O}(n^2)$-time.

Big Data promises important societal progress but exacerbates the need for due process and accountability. Companies and institutions can now discriminate between users at an individual level using collected data or past behavior. Worse, today they can do so in near perfect opacity. The nascent field of web transparency aims to develop the tools and methods necessary to reveal how information is used, however today it lacks robust tools that let users and investigators identify targeting using multiple inputs.

The shortest-path metric ${\textup{d}}$ of a connected graph $G$ is ${1}/{2}$-hyperbolic if and only if it satisfies ${\textup{d}}(u,v) + {\textup{d}}(x,y) \leq \max \{ {\textup{d}}(u,x) + {\textup{d}}(v,y), {\textup{d}}(u,y) + {\textup{d}}(v,x) \} + 1$, for every $4$-tuple $u$, $x$, $v$, $y$ of $G$. We show that the problem of deciding whether an unweighted graph is ${1}/{2}$-hyperbolic is subcubic equivalent to the problem of determining whether there is a chordless cycle of length $4$ in a graph. An improved algorithm is also given for both problems, taking advantage of fast rectangular matrix multiplication. In the worst case it runs in $O(n^{3.26})$-time.