We propose to study unweighted graphs of constant distance VC-dimension as a broad generalization of many graph classes for which we can compute the diameter in truly subquadratic-time. In particular for any fixed @math , the class of @math -minor free graphs has distance VC-dimension at most @math . Our first main result is that on graphs of distance VC-dimension at most @math , for any fixed @math we can either compute the diameter or conclude that it is larger than @math in time @math , where @math only depends on @math . Then as a byproduct of our approach, we get the first truly subquadratic-time algorithm for constant diameter computation on all the nowhere dense graph classes. Finally, we show how to remove the dependency on @math for any graph class that excludes a fixed graph @math as a minor. More generally, our techniques apply to any graph with constant distance VC-dimension and polynomial expansion. As a result for all such graphs one obtains a truly subquadratic-time algorithm for computing their diameter. 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 the best known approximation algorithms for the stabbing number problem with a clever use of @math -nets, region decomposition and other partition techniques.
An early example of linear-time solvable special case for diameter computation is the class of interval graphs @cite_0 . For every interval graph @math and for any integer @math , if we first compute an interval representation for @math in linear-time @cite_31 then we can compute by dynamic programming, for every vertex @math , the contiguous segment of all the vertices at a distance @math from @math in @math . It takes almost linear-time and it implies a straightforward quasi linear-time algorithm for diameter computation. More efficient algorithms for diameter computation on interval graphs and related graph classes were proposed in @cite_23 . Nevertheless we will show in what follows that interval orderings are a powerful tool for diameter computation on more general geometric graph classes.
@cite_0 @cite_31 @cite_23
2102564932 9515613 2091612923
The Near-Bipartiteness problem is that of deciding whether or not the vertices of a graph can be partitioned into sets @math and @math , where @math is an independent set and @math induces a forest. The set @math in such a partition is said to be an independent feedback vertex set. Yang and Yuan proved that Near-Bipartiteness is polynomial-time solvable for graphs of diameter 2 and NP-complete for graphs of diameter 4. We show that Near-Bipartiteness is NP-complete for graphs of diameter 3, resolving their open problem. We also generalise their result for diameter 2 by proving that even the problem of computing a minimum independent feedback vertex is polynomial-time solvable for graphs of diameter 2. The computational problem of finding the center of a graph is motivated by a number of facility-location problems. We exploit a new characterization of interval graphs for the purpose of obtaining a linear-time algorithm for computing both the center and the diameter of an interval graph. For a positive parameter @math , the @math -bounded distance between a pair of vertices @math in a weighted undirected graph @math is the length of the shortest @math path in @math with at most @math edges, aka hops . For @math as above and @math , a @math -hopset of @math is a graph @math on the same vertex set, such that all distances in @math are @math -approximated by @math -bounded distances in @math . Hopsets are a fundamental graph-theoretic and graph-algorithmic construct, and they are widely used for distance-related problems in a variety of computational settings. Currently existing constructions of hopsets produce hopsets either with @math edges, or with a hopbound @math . In this paper we devise a construction of linear-size hopsets with hopbound @math . This improves the previous bound almost exponentially. We also devise efficient implementations of our construction in PRAM and distributed settings. The only existing PRAM algorithm EN16 for computing hopsets with a constant (i.e., independent of @math ) hopbound requires @math time. We devise a PRAM algorithm with polylogarithmic running time for computing hopsets with a constant hopbound, i.e., our running time is exponentially better than the previous one. Moreover, these hopsets are also significantly sparser than their counterparts from EN16 . We use our hopsets to devise a distributed routing scheme that exhibits near-optimal tradeoff between individual memory requirement @math of vertices throughout preprocessing and routing phases of the algorithm, and stretch @math , along with a near-optimal construction time @math , where @math is the hop-diameter of the input graph. Graphs of clique–width at most k were introduced by Courcelle, Engelfriet and Rozenberg (1993) as graphs which can be defined by k-expressions based on graph operations which use k vertex labels. In this paper we study the clique–width of perfect graph classes. On one hand, we show that every distance–hereditary graph, has clique–width at most 3, and a 3–expression defining it can be obtained in linear time. On the other hand, we show that the classes of unit interval and permutation graphs are not of bounded clique–width. More precisely, we show that for every @math there is a unit interval graph In and a permutation graph Hn having n2 vertices, each of whose clique–width is at least n. These results allow us to see the border within the hierarchy of perfect graphs between classes whose clique–width is bounded and classes whose clique–width is unbounded. Finally we show that every n×n square grid, @math , n ≥ 3, has clique–width exactly n+1. We develop a new technique for constructing sparse graphs that allow us to prove near-linear lower bounds on the round complexity of computing distances in the CONGEST model. Specifically, we show an @math lower bound for computing the diameter in sparse networks, which was previously known only for dense networks [, SODA 2012]. In fact, we can even modify our construction to obtain graphs with constant degree, using a simple but powerful degree-reduction technique which we define. Moreover, our technique allows us to show @math lower bounds for computing @math -approximations of the diameter or the radius, and for computing a @math -approximation of all eccentricities. For radius, we are unaware of any previous lower bounds. For diameter, these greatly improve upon previous lower bounds and are tight up to polylogarithmic factors [, SODA 2012], and for eccentricities the improvement is both in the lower bound and in the approximation factor [Holzer and Wattenhofer, PODC 2012]. Interestingly, our technique also allows showing an almost-linear lower bound for the verification of @math -spanners, for @math . We consider broadcasting in radio networks, modeled as undirected graphs, whose nodes know only their own label and labels of their neighbors. In every step every node acts either as a transmitter or as a receiver. A node acting as a transmitter sends a message which can potentially reach all of its neighbors. A node acting as a receiver in a given step gets a message if and only if exactly one of its neighbors transmits in this step. Bar-Yehuda, Goldreich, and Itai [J. Comput. System Sci., 45 (1992), pp. 104--126] considered broadcasting in this model. They claimed a linear lower bound on the time of deterministic broadcasting in such radio networks of diameter 3. This claim turns out to be incorrect in this model (although it is valid in a more pessimistic model [R. Bar-Yehuda, O. Goldreich, and A. Itai, Errata Regarding "On the time complexity of broadcast in radio networks: An exponential gap between determinism and randomization," http: www.wisdom.weizmann.ac.il mathusers oded p .html, 2002]). We construct an algorithm that broadcasts in logarithmic time on all graphs from the Bar-Yehuda, Goldreich, and Itai paper (BGI). Moreover, we show how to broadcast in sublinear time on all n-node graphs of diameter @math . On the other hand, we construct a class of graphs of diameter 4, such that every broadcasting algorithm requires time @math on these graphs. In view of the randomized algorithm from BGI, running in expected time @math on all @math -node graphs of diameter D (cf. also a recent @math -time algorithm from [D. Kowalski and A. Pelc, Proceedings of the 22nd Annual ACM Symposium on Principles of Distributed Computing, Boston, 2003, pp. 73--82; A. Czumaj and W. Rytter, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, Cambridge, MA, 2003, pp. 492--501]), our lower bound gives the first correct proof of an exponential gap between determinism and randomization in the time of radio broadcasting, under the considered model of radio communication. 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). Edge and vertex connectivity are fundamental concepts in graph theory. While they have been thoroughly studied in the case of undirected graphs, surprisingly not much has been investigated for directed graphs. In this paper we study @math -edge connectivity problems in directed graphs and, in particular, we consider the computation of the following natural relation: We say that two vertices @math and @math are @math -edge-connected if there are two edge-disjoint paths from @math to @math and two edge-disjoint paths from @math to @math . This relation partitions the vertices into blocks such that all vertices in the same block are @math -edge-connected. Differently from the undirected case, those blocks do not correspond to the @math -edge-connected components of the graph. We show how to compute this relation in linear time so that we can report in constant time if two vertices are @math -edge-connected. We also show how to compute in linear time a sparse certificate for this relation, i.e., a subgraph of the input graph that has @math edges and maintains the same @math -edge-connected blocks as the input graph. Determining the diameter of a graph is a fundamental graph operation, yet no efficient (i.e. linear or quadratic time) algorithm is known. In this paper, we examine the diameter problem on chordal graphs and AT-free graphs and show that a very simple (linear time) 2-sweep LexBFS algorithm identifies a vertex of maximum eccentricity unless the given graph has a specified induced subgraph (it was previously known that a single LexBFS algorithm is guaranteed to end at a vertex that is within 1 of the diameter for chordal graphs and AT-free graphs). As a consequence of the forbidden induced subgraph result on chordal graphs, our algorithm is guaranteed to work optimally for directed path graphs (it was previously known that a single LexBFS algorithm is guaranteed to work optimally for interval graphs). We study a natural extension of the Maximum Weight Independent Set Problem (MWIS), one of the most studied optimization problems in Graph algorithms. We are given a graph @math , a weight function @math , a budget function @math , and a positive integer @math . The weight (resp. budget) of a subset of vertices is the sum of weights (resp. budgets) of the vertices in the subset. A @math -budgeted independent set in @math is a subset of vertices, such that no pair of vertices in that subset are adjacent, and the budget of the subset is at most @math . The goal is to find a @math -budgeted independent set in @math such that its weight is maximum among all the @math -budgeted independent sets in @math . We refer to this problem as MWBIS. Being a generalization of MWIS, MWBIS also has several applications in Scheduling, Wireless networks and so on. Due to the hardness results implied from MWIS, we study the MWBIS problem in several special classes of graphs. We design exact algorithms for trees, forests, cycle graphs, and interval graphs. In unweighted case we design an approximation algorithm for @math -claw free graphs whose approximation ratio ( @math ) is competitive with the approximation ratio ( @math ) of MWIS (unweighted). Furthermore, we extend Baker's technique Baker83 to get a PTAS for MWBIS in planar graphs. We study the perfect matching reconfiguration problem: Given two perfect matchings of a graph, is there a sequence of flip operations that transforms one into the other? Here, a flip operation exchanges the edges in an alternating cycle of length four. We are interested in the complexity of this decision problem from the viewpoint of graph classes. We first prove that the problem is PSPACE-complete even for split graphs and for bipartite graphs of bounded bandwidth with maximum degree five. We then investigate polynomial-time solvable cases. Specifically, we prove that the problem is solvable in polynomial time for strongly orderable graphs (that include interval graphs and strongly chordal graphs), for outerplanar graphs, and for cographs (also known as @math -free graphs). Furthermore, for each yes-instance from these graph classes, we show that a linear number of flip operations is sufficient and we can exhibit a corresponding sequence of flip operations in polynomial time. In the recent past, there has been considerable progress in devising algorithms for the all-pairs shortest paths (APSP) problem running in time significantly smaller than the obvious time bound of O(n3). Unfortunately, all the new algorithms are based on fast matrix multiplication algorithms that are notoriously impractical. Our work is motivated by the goal of devising purely combinatorial algorithms that match these improved running times. Our results come close to achieving this goal, in that we present algorithms with a small additive error in the length of the paths obtained. Our algorithms are easy to implement, have the desired property of being combinatorial in nature, and the hidden constants in the running time bound are fairly small. Our main result is an algorithm which solves the APSP problem in unweighted, undirected graphs with an additive error of 2 in time @math . This algorithm returns actual paths and not just the distances. In addition, we give more efficient algorithms with running time @math for the case where we are only required to determine shortest paths between k specified pairs of vertices rather than all pairs of vertices. The starting point for all our results is an @math algorithm for distinguishing between graphs of diameter 2 and 4, and this is later extended to obtaining a ratio 2 3 approximation to the diameter in time @math . Unlike in the case of APSP, our results for approximate diameter computation can be extended to the case of directed graphs with arbitrary positive real weights on the edges. In this paper, we consider a popular randomized broadcasting algorithm called push-algorithm defined as follows. Initially, one vertex of a graph G=(V,E) owns a piece of information which is spread iteratively to all other vertices: in each timestep t=1,2,… every informed vertex chooses a neighbor uniformly at random and informs it. The question is how many time steps are required until all vertices become informed (with high probability). For various graph classes, involved methods have been developed in order to show an upper bound of @math on the runtime of the push-algorithm, where N is the number of vertices and @math denotes the diameter of G. However, no asymptotically tight bound on the runtime based on the mixing time of random walks has been established. In this work we fill this gap by deriving an upper bound of @math , where @math denotes the mixing time of a certain random walk on G. After that we prove upper bounds that are based on certain edge expansion properties of G. However, for hypercubes neither the bound based on the mixing time nor the bounds based on edge expansion properties are tight. That is why we develop a general way to combine these two approaches by which we can deduce that the runtime of the push-algorithm is Θ(log N) on every Hamming graph. We present the communication model, which assumes nodes have minimal knowledge about their environment and severely limited communication capabilities. Specifically, nodes have no information regarding the local or global structure of the network, don't have access to synchronized clocks and are woken up by an adversary. Moreover, instead on communicating through messages they rely solely on carrier sensing to exchange information. We study the problem of , a variant of vertex coloring specially suited for the studied beeping model. Given a set of resources, the goal of interval coloring is to assign every node a large contiguous fraction of the resources, such that neighboring nodes share no resources. To highlight the importance of the discreteness of the model, we contrast it against a continuous variant described in [17]. We present an O(1 @math (T ) @math T @math O( n) @math (T ) @math O( n) @math ( n)$ on the time required to solve interval coloring for this model against randomized algorithms. This lower bound implies that our algorithm is asymptotically optimal for constant degree graphs. For an infinite family of @math -regular LPS Ramanujan graphs, we show that the diameter of these graphs is greater than or equal to @math , where @math is an odd prime number and @math is the number of vertices. On the other hand, for any @math -regular Ramanujan graph we show that the distance of only tiny fraction of all pairs of vertices is greater than @math . We also have some numerical experiments for LPS Ramanujan graphs and random Cayley graphs which suggest that the diameters are asymptotically @math and @math , respectively. These are consistent with Sarnak's expectation on the covering exponent of universal quantum gates and our conjecture for the optimal strong approximation for quadratic forms in 4 variables. We present a general technique for detecting and counting small subgraphs. It consists of forming special linear combinations of the numbers of occurrences of different induced subgraphs of fixed size in a graph. These combinations can be efficiently computed by rectangular matrix multiplication. Our two main results utilizing the technique are as follows. Let @math be a fixed graph with @math vertices and an independent set of size @math 1. Detecting if an @math -vertex graph contains a (not necessarily induced) subgraph isomorphic to @math can be done in time @math , where @math is the exponent of fast arithmetic matrix multiplication of an @math matrix by an @math matrix. 2. When @math counting the number of (not necessarily induced) subgraphs isomorphic to @math can be done in the same time, i.e., in time @math It follows in particular that we can count the nu... We study the broadcast version of the CONGEST CLIQUE model of distributed computing. In this model, in each round, any node in a network of size @math can send the same message (i.e. broadcast a message) of limited size to every other node in the network. Nanongkai presented in [STOC'14] a randomized @math -approximation algorithm to compute all pairs shortest paths (APSP) in time @math on weighted graphs, where we use the convention that @math is essentially @math polylog @math and @math is essentially @math polylog @math . We complement this result by proving that any randomized @math -approximation of APSP and @math -approximation of the diameter of a graph takes @math time in the worst case. This demonstrates that getting a negligible improvement in the approximation factor requires significantly more time. Furthermore this bound implies that already computing a @math -approximation of all pairs shortest paths is among the hardest graph-problems in the broadcast-version of the CONGEST CLIQUE model and contrasts a recent @math -approximation for APSP that runs in time @math in the unicast version of the CONGEST CLIQUE model. On the positive side we provide a deterministic version of Nanongkai's @math -approximation algorithm for APSP. To do so we present a fast deterministic construction of small hitting sets. We also show how to replace another randomized part within Nanongkai's algorithm with a deterministic source-detection algorithm designed for the CONGEST model presented by Lenzen and Peleg at PODC'13. We consider an interval coverage problem. Given @math intervals of the same length on a line @math and a line segment @math on @math , we want to move the intervals along @math such that every point of @math is covered by at least one interval and the sum of the moving distances of all intervals is minimized. As a basic geometry problem, it has applications in mobile sensor barrier coverage in wireless sensor networks. The previous work solved the problem in @math time. In this paper, by discovering many interesting observations and developing new algorithmic techniques, we present an @math time algorithm. We also show an @math time lower bound for this problem, which implies the optimality of our algorithm. Motivated by the immense success of random walk and Markov chain methods in the design of classical algorithms, we consider quantum walks on graphs. We analyse in detail the behaviour of unbiased quantum walk on the line, with the example of a typical walk, the Hadamard walk''''. In particular, we show that after @math time steps, the probability distribution on the line induced by the Hadamard walk is almost uniformly distributed over the interval @math . This implies that the same walk defined on the circle mixes in linear time. This is in direct contrast with the quadratic mixing time for the corresponding classical walk. We conclude by indicating how our techniques may be applied to more general graphs. The distributed single-source shortest paths problem is one of the most fundamental and central problems in the message-passing distributed computing. Classical Bellman-Ford algorithm solves it in @math time, where @math is the number of vertices in the input graph @math . Peleg and Rubinovich (FOCS'99) showed a lower bound of @math for this problem, where @math is the hop-diameter of @math . Whether or not this problem can be solved in @math time when @math is relatively small is a major notorious open question. Despite intensive research LP13,N14,HKN15,EN16,BKKL16 that yielded near-optimal algorithms for the approximate variant of this problem, no progress was reported for the original problem. In this paper we answer this question in the affirmative. We devise an algorithm that requires @math time, for @math , and @math time, for larger @math . This running time is sublinear in @math in almost the entire range of parameters, specifically, for @math . For the all-pairs shortest paths problem, our algorithm requires @math time, regardless of the value of @math . We also devise the first algorithm with non-trivial complexity guarantees for computing exact shortest paths in the multipass semi-streaming model of computation. From the technical viewpoint, our algorithm computes a hopset @math of a skeleton graph @math of @math without first computing @math itself. We then conduct a Bellman-Ford exploration in @math , while computing the required edges of @math on the fly. As a result, our algorithm computes exactly those edges of @math that it really needs, rather than computing approximately the entire @math .