A Quadratic Algorithm for Finding Next-to-Shortest Paths in Graphs

Given an edge-weighted undirected graph G and two prescribed vertices u and v, a next-to-shortest (u,v)-path is a shortest (u,v)-path amongst all (u,v)-paths having length strictly greater than the length of a shortest (u,v)-path. In this paper, we deal with the problem of computing a next-to-shortest (u,v)-path. We propose an O(n²){\mathcal{O}}(n^{2}) time algorithm for solving this problem, which significantly improves the bound of a previous one in O(n³){\mathcal{O}}(n^{3}) time where n is the number of vertices in G.     

Finding next-to-shortest paths in a graph

We study the problem of finding the next-to-shortest paths in a graph. A next-to-shortest (u,v)-path is a shortest (u,v)-path amongst (u,v)-paths with length strictly greater than the length of the shortest (u,v)-path. In contrast to the situation in directed graphs, where the problem has been shown to be NP-hard, providing edges of length zero are allowed, we prove the somewhat surprising result that there is a polynomial time algorithm for the undirected version of the problem.     

Paths in Möbius cubes and crossed cubes

The Möbius cube MQn and the crossed cube CQn are two important variants of the hypercube Qn. This paper shows that for any two different vertices u and v in G∈{MQn,CQn} with n?3, there exists a uv-path of every length from dG(u,v)+2 to n²−1 except for a shortest uv-path, where dG(u,v) is the distance between u and v in G. This result improves some known results.     

A new sufficient condition for Hamiltonicity of graphs

Rahman and Kaykobad proved the following theorem on Hamiltonian paths in graphs. Let G be a connected graph with n vertices. If d(u)+d(v)+δ(u,v)?n+1 for each pair of distinct non-adjacent vertices u and v in G, where δ(u,v) is the length of a shortest path between u and v in G, then G has a Hamiltonian path. It is shown that except for two families of graphs a graph is Hamiltonian if it satisfies the condition in Rahman and Kaykobad's theorem. The result obtained in this note is also an answer for a question posed by Rahman and Kaykobad.     

Constructing the nearly shortest path in crossed cubes

A graph G is panconnected if each pair of distinct vertices u,v∈V(G) are joined by a path of length l for all d_G(u,v)?l?|V(G)|-1, where d_G(u,v) is the length of a shortest path joining u and v in G. Recently, Fan et. al. [J. Fan, X. Lin, X. Jia, Optimal path embedding in crossed cubes, IEEE Trans. Parall. Distrib. Syst. 16 (2) (2005) 1190-1200, J. Fan, X. Jia, X. Lin, Complete path embeddings in crossed cubes, Inform. Sci. 176 (22) (2006) 3332-3346] and Xu et. al. [J.M. Xu, M.J. Ma, M. Lu, Paths in Möbius cubes and crossed cubes, Inform. Proc. Lett. 97 (3) (2006) 94-97] both proved that n-dimensional crossed cube, CQ_n, is almost panconnected except the path of length d_CQn(u,v)+1 for any two distinct vertices u,v∈V(CQ_n). In this paper, we give a necessary and sufficient condition to check for the existence of paths of length d_CQn(u,v)+1, called the nearly shortest paths, for any two distinct vertices u,v in CQ_n. Moreover, we observe that only some pair of vertices have no nearly shortest path and we give a construction scheme for the nearly shortest path if it exists.     

Fully dynamic biconnectivity in graphs

We present an algorithm for maintaining the biconnected components of a graph during a sequence of edge insertions and deletions. It requires linear storage and preprocessing time. The amortized running time for insertions and for deletions isO(m ^2/3 ), wherem is the number of edges in the graph. Any query of the form ‘Are the verticesu andv biconnected?’ can be answered in timeO(1). This is the first sublinear algorithm for this problem. We can also output all articulation points separating any two vertices efficiently. If the input is a plane graph, the amortized running time for insertions and deletions drops toO(√n logn) and the query time isO(log² n), wheren is the number of vertices in the graph. The best previously known solution takes timeO(n ^2/3 ) per update or query.     

Improved algorithms for the k simple shortest paths and the replacement paths problems

Given a directed, non-negatively weighted graph G=(V,E) and s,t∈V, we consider two problems. In the k simple shortest paths problem, we want to find the k simple paths from s to t with the k smallest weights. In the replacement paths problem, we want the shortest path from s to t that avoids e, for every edge e in the original shortest path from s to t. The best known algorithm for the k simple shortest paths problem has a running of O(k(mn+n²logn)). For the replacement paths problem the best known result is the trivial one running in time O(mn+n²logn).In this paper we present two simple algorithms for the replacement paths problem and the k simple shortest paths problem in weighted directed graphs (using a solution of the All Pairs Shortest Paths problem). The running time of our algorithm for the replacement paths problem is O(mn+n²loglogn). For the k simple shortest paths we will perform O(k) iterations of the second simple shortest path (each in O(mn+n²loglogn) running time) using a useful property of Roditty and Zwick [L. Roditty, U. Zwick, Replacement paths and k simple shortest paths in unweighted directed graphs, in: Proc. of International Conference on Automata, Languages and Programming (ICALP), 2005, pp. 249-260]. These running times immediately improve the best known results for both problems over sparse graphs.Moreover, we prove that both the replacement paths and the k simple shortest paths (for constant k) problems are not harder than APSP (All Pairs Shortest Paths) in weighted directed graphs.     

Bandwidth on AT-free graphs

We study the classical Bandwidth problem from the viewpoint of parametrised algorithms. Given a graph G=(V,E) and a positive integer k, the Bandwidth problem asks whether there exists a bijective function β:{1,…,∣V∣}→V such that for every edge uv∈E, ∣β⁻¹(u)−β⁻¹(v)∣≤k. It is known that under standard complexity assumptions, no algorithm for Bandwidth with running time of the form f(k)n^O(1) exists, even when the input is restricted to trees. We initiate the search for classes of graphs where such algorithms do exist. We present an algorithm with running time n⋅2^O(klogk) for Bandwidth on AT-free graphs, a well-studied graph class that contains interval, permutation, and cocomparability graphs. Our result is the first non-trivial algorithm that shows fixed-parameter tractability of Bandwidth on a graph class on which the problem remains NP-complete.     

A Simpler and More Efficient Algorithm for the Next-to-Shortest Path Problem

Given an undirected graph G=(V,E) with positive edge lengths and two vertices s and t, the next-to-shortest path problem is to find an st-path which length is minimum amongst all st-paths strictly longer than the shortest path length. In this paper we show that the problem can be solved in linear time if the distances from s and t to all other vertices are given. Particularly our new algorithm runs in O(|V|log|V|+|E|) time for general graphs, which improves the previous result of O(|V|²) time and takes only linear time for unweighted graphs, planar graphs, and graphs with positive integer edge lengths.     

Additive Spanners and Distance and Routing Labeling Schemes for Hyperbolic Graphs

δ-Hyperbolic metric spaces have been defined by M. Gromov in 1987 via a simple 4-point condition: for any four points u,v,w,x, the two larger of the distance sums d(u,v)+d(w,x),d(u,w)+d(v,x),d(u,x)+d(v,w) differ by at most?2δ. They play an important role in geometric group theory, geometry of negatively curved spaces, and have recently become of interest in several domains of computer science, including algorithms and networking. In this paper, we study unweighted δ-hyperbolic graphs. Using the Layering Partition technique, we show that every n-vertex δ-hyperbolic graph with δ≥1/2 has an additive O(δlog?n)-spanner with at most O(δn) edges and provide a simpler, in our opinion, and faster construction of distance approximating trees of δ-hyperbolic graphs with an additive error O(δlog?n). The construction of our tree takes only linear time in the size of the input graph. As a consequence, we show that the family of n-vertex δ-hyperbolic graphs with δ≥1/2 admits a routing labeling scheme with O(δlog?² n) bit labels, O(δlog?n) additive stretch and O(log?₂(4δ)) time routing protocol, and a distance labeling scheme with O(log?² n) bit labels, O(δlog?n) additive error and constant time distance decoder.     

Efficient algorithms for constructing (1+∊,β)-spanners in the distributed and streaming models

For an unweighted undirected graph G = (V,E), and a pair of positive integers α ≥ 1, β ≥ 0, a subgraph G′ = (V,H), H ⊂eqE, is called an (α,β)-spanner of G if for every pair of vertices u,v ∊ V, dist_G′(u,v) ≤ α ⋅ dist_G(u,v) + β. It was shown in [21] that for any ∊ > 0, κ = 1,2,…, there exists an integer β = β(∊,κ) such that for every n-vertex graph G there exists a (1+∊,β)-spanner G′ with O(n^1+1/κ) edges. An efficient distributed protocol for constructing (1+∊,β)-spanners was devised in [19]. The running time and the communication complexity of that protocol are O(n^1+ρ) and O(|E|n^ρ), respectively, where ρ is an additional control parameter of the protocol that affects only the additive term β. In this paper we devise a protocol with a drastically improved running time (O(n^ρ) as opposed to O(n^1+ρ)) for constructing (1+∊,β)-spanners. Our protocol has the same communication complexity as the protocol of [19], and it constructs spanners with essentially the same properties as the spanners that are constructed by the protocol of [19]. The protocol can be easily extended to a parallel implementation which runs in O(log n + (|E|⋅ n^ρlog n)/p) time using p processors in the EREW PRAM model. In particular, when the number of processors, p, is at least |E|⋅ n^ρ, the running time of the algorithm is O(log n). We also show that our protocol for constructing (1+∊,β)-spanners can be adapted to the streaming model, and devise a streaming algorithm that uses a constant number of passes and O(n^1+1/κ⋅ {log} n) bits of space for computing all-pairs-almost-shortest-paths of length at most by a multiplicative factor (1+∊) and an additive term of β greater than the shortest paths. Our algorithm processes each edge in time O(n^ρ), for an arbitrarily small ρ > 0. The only previously known algorithm for the problem [23] constructs paths of length κ times greater than the shortest paths, has the same space requirements as our algorithm, but requires O(n^1+1/κ) time for processing each edge of the input graph. However, the algorithm of [23] uses just one pass over the input, as opposed to the constant number of passes in our algorithm. We also show that any streaming algorithm for o(n)-approximate distance computation requires Ω(n) bits of space. This work was Supported by the DoD University Research Initiative (URI) administered by the Office of Naval Research under Grant N00014-01-1-0795. Michael Elkin was supported by ONR grant N00014-01-1-0795. Jian Zhang was supported by ONR grant N00014-01-1-0795 and NSF grants CCR-0105337 and ITR-0331548. Preliminary version of this paper was published in PODC’04, see [22]. After the preliminary version of our paper [22] appeared on PODC’04, Feigenbaum et al. [24] came up with a new streaming algorithm for the problem that is far more efficient than [23] in terms of time-per-edge processing. However, our algorithm is still the only existing streaming algorithm that provides an almost additive approximation of distances.     

Approximating Node-Connectivity Augmentation Problems

We consider the (undirected) Node Connectivity Augmentation (NCA) problem: given a graph J=(V,E _J ) and connectivity requirements $\{r(u,v): u,v \in V\}$ , find a minimum size set I of new edges (any edge is allowed) such that the graph J∪I contains r(u,v) internally-disjoint uv-paths, for all u,v∈V. In Rooted NCA there is s∈V such that r(u,v)>0 implies u=s or v=s. For large values of k=max? _u,v∈V r(u,v), NCA is at least as hard to approximate as Label-Cover and thus it is unlikely to admit an approximation ratio polylogarithmic in k. Rooted NCA is at least as hard to approximate as Hitting-Set. The previously best approximation ratios for the problem were O(kln?n) for NCA and O(ln?n) for Rooted NCA. In this paper we give an approximation algorithm with ratios O(kln?² k) for NCA and O(ln?² k) for Rooted NCA. This is the first approximation algorithm with ratio independent of?n, and thus is a constant for any fixed k. Our algorithm is based on the following new structural result which is of independent interest. If $\mathcal{D}$ is a set of node pairs in a graph?J, then the maximum degree in the hypergraph formed by the inclusion minimal tight sets separating at least one pair in $\mathcal{D}$ is O(? ²), where ? is the maximum connectivity in J of a pair in $\mathcal{D}$ .     

Finding Maximum Edge Bicliques in Convex Bipartite Graphs

A bipartite graph G=(A,B,E) is convex on B if there exists an ordering of the vertices of B such that for any vertex v??A, vertices adjacent to v are consecutive in?B. A complete bipartite subgraph of a graph G is called a biclique of G. Motivated by an application to analyzing DNA microarray data, we study the problem of finding maximum edge bicliques in convex bipartite graphs. Given a bipartite graph G=(A,B,E) which is convex on B, we present a new algorithm that computes a maximum edge biclique of G in O(nlog?³ nlog?log?n) time and O(n) space, where n=|A|. This improves the current O(n ²) time bound available for the problem. We also show that for two special subclasses of convex bipartite graphs, namely for biconvex graphs and bipartite permutation graphs, a maximum edge biclique can be computed in O(n??(n)) and O(n) time, respectively, where n=min?(|A|,|B|) and ??(n) is the slowly growing inverse of the Ackermann function.     

On edge connectivity of direct products of graphs

Let λ(G) be the edge connectivity of G. The direct product of graphs G and H is the graph with vertex set V(G×H)=V(G)×V(H), where two vertices (u₁,v₁) and (u₂,v₂) are adjacent in G×H if u₁u₂∈E(G) and v₁v₂∈E(H). We prove that λ(G×Kn)=min{n(n−1)λ(G),(n−1)δ(G)} for every nontrivial graph G and n?3. We also prove that for almost every pair of graphs G and H with n vertices and edge probability p, G×H is k-connected, where k=O(²(n/logn)).     

All-pairs shortest-paths computation in the presence of negative cycles

We present an algorithm that solves the all-pairs shortest-paths problem on a directed graph with n vertices and m arcs in time O(nm+n²logn), where the arcs are assigned real, possibly negative costs. Our algorithm is new in the following respect. It computes the distance μ(v,w) between each pair v,w of vertices even in the presence of negative cycles, where μ(v,w) is defined as the infimum of the costs of all directed paths from v to w.     

Improved algorithm for all pairs shortest paths

We present an improved algorithm for all pairs shortest paths. For a graph of n vertices our algorithm runs in O(n³(loglogn/logn)^5/7) time. This improves the best previous result which runs in O(n³(loglogn/logn)^1/2) time.     

Hamiltonian connectivity and globally 3∗-connectivity of dual-cube extensive networks

In 2000, Li et al. introduced dual-cube networks, denoted by DC_n for n?1, using the hypercube family Q_n and showed the vertex symmetry and some fault-tolerant hamiltonian properties of DC_n. In this article, we introduce a new family of interconnection networks called dual-cube extensive networks, denoted by DCEN(G). Given any arbitrary graph G, DCEN(G) is generated from G using the similar structure of DC_n. We show that if G is a nonbipartite and hamiltonian connected graph, then DCEN(G) is hamiltonian connected. In addition, if G has the property that for any two distinct vertices u,v of G, there exist three disjoint paths between u and v such that these three paths span the graph G, then DCEN(G) preserves the same property. Furthermore, we prove that the similar results hold when G is a bipartite graph.     

Approximate Shortest Paths Avoiding a Failed Vertex: Near Optimal Data Structures for Undirected Unweighted Graphs

Let G=(V,E) be an undirected unweighted graph. A path between any two vertices u,v∈V is said to be t-approximate shortest path if its length is at most t times the length of the shortest path between u and v. We address the problem of building a compact data structure which can efficiently answer the following query for any u,v,x∈V and t>1: Report t-approximate shortest path between u and v when vertex x fails. We present data structures for the single source as well as all-pairs versions of this problem. The query time guaranteed by our data structures is optimal up to a constant factor. Moreover, the size of each of them nearly matches the size of the corresponding data structure with no failures.     

Efficient algorithms for clique problems

The k-clique problem is a cornerstone of NP-completeness and parametrized complexity. When k is a fixed constant, the asymptotically fastest known algorithm for finding a k-clique in an n-node graph runs in O(n0.792k) time (given by Nešet?il and Poljak). However, this algorithm is infamously inapplicable, as it relies on Coppersmith and Winograd's fast matrix multiplication.We present good combinatorial algorithms for solving k-clique problems. These algorithms do not require large constants in their runtime, they can be readily implemented in any reasonable random access model, and are very space-efficient compared to their algebraic counterparts. Our results are the following:

•

We give an algorithm for k-clique that runs in O(nk/(εlogn)^k−1) time and O(nε) space, for all ε>0, on graphs with n nodes. This is the first algorithm to take o(nk) time and O(nc) space for c independent of k.

•

Let k be even. Define a k-semiclique to be a k-node graph G that can be divided into two disjoint subgraphs U={u₁,…,uk/2} and V={v₁,…,vk/2} such that U and V are cliques, and for all i?j, the graph G contains the edge {ui,vj}. We give an time algorithm for determining if a graph has a k-semiclique. This yields an approximation algorithm for k-clique, in the following sense: if a given graph contains a k-clique, then our algorithm returns a subgraph with at least 3/4 of the edges in a k-clique.

     

Fast Maximal Cliques Enumeration in Sparse Graphs

In this paper, we consider the problem of generating all maximal cliques in a sparse graph in polynomial delay. Given a graph G=(V,E) with n vertices and m edges, the latest and fastest polynomial delay algorithm for sparse graphs enumerates all maximal cliques in O(Δ ⁴) time delay, where Δ is the maximum degree of vertices. However, it requires an O(n?m) preprocessing time. We improve it in two aspects. First, our algorithm does not need preprocessing. Therefore, our algorithm is a truly polynomial delay algorithm. Second, our algorithm enumerates all maximal cliques in O(Δ?H ³) time delay, where H is the so called H-value of a graph or equivalently it is the smallest integer satisfying |{v∈V∣δ(v)≥H}|≤H given δ(v) as the degree of a vertex. In real-world network data, H usually is a small value and much smaller than Δ.