Finding a dominating set on bipartite graphs

Finding a dominating set of minimum cardinality is an NP-hard graph problem, even when the graph is bipartite. In this paper we are interested in solving the problem on graphs having a large independent set. Given a graph G with an independent set of size z, we show that the problem can be solved in time O^∗(²n−z), where n is the number of vertices of G. As a consequence, our algorithm is able to solve the dominating set problem on bipartite graphs in time O^∗(²n/2). Another implication is an algorithm for general graphs whose running time is O(n^1.7088).     

An algorithm for geometric minimum spanning trees requiring nearly linear expected time

We describe an algorithm for finding a minimum spanning tree of the weighted complete graph induced by a set ofn points in Euclideand-space. The algorithm requires nearly linear expected time for points that are independently uniformly distributed in the unitd-cube. The first step of the algorithm is the spiral search procedure described by Bentleyet al. [BWY82] for finding a supergraph of the MST that hasO(n) edges. (The constant factor in the bound depends ond.) The next step is that of sorting the edges of the supergraph by weight using a radix distribution, or “bucket,” sort. These steps require linear expected time. Finally, Kruskal's algorithm is used with the sorted edges, requiringO(nα(cn, n)) time in the worst case, withc>6. Since the function α(cn, n) grows very slowly, this step requires linear time for all practical purposes. This result improves the previous bestO(n log log*n), and employs a much simpler algorithm. Also, this result demonstrates the robustness of bucket sorting, which requiresO(n) expected time in this case despite the probability dependency between the edge weights.     

Pathwidth of cubic graphs and exact algorithms

We prove that for any ?>0 there exists an integer n? such that the pathwidth of every cubic (or 3-regular) graph on n>n? vertices is at most (1/6+?)n. Based on this bound we improve the worst case time analysis for a number of exact exponential algorithms on graphs of maximum vertex degree three.     

Dominating set based exact algorithms for 3-coloring

We show that the 3-colorability problem can be solved in O(n^1.296) time on any n-vertex graph with minimum degree at least 15. This algorithm is obtained by constructing a dominating set of the graph greedily, enumerating all possible 3-colorings of the dominating set, and then solving the resulting 2-list coloring instances in polynomial time. We also show that a 3-coloring can be obtained in ²o(n) time for graphs having minimum degree at least ω(n) where ω(n) is any function which goes to ∞. We also show that if the lower bound on minimum degree is replaced by a constant (however large it may be), then neither a ²o(n) time nor a ²o(m) time algorithm is possible (m denotes the number of edges) for 3-colorability unless Exponential Time Hypothesis (ETH) fails. We also describe an algorithm which obtains a 4-coloring of a 3-colorable graph in O(n^1.2535) time.     

Fast Sequential Importance Sampling to Estimate the Graph Reliability Polynomial

The reliability polynomial of a graph counts its connected subgraphs of various sizes. Algorithms based on sequential importance sampling (SIS) have been proposed to estimate a graph’s reliability polynomial. We develop an improved SIS algorithm for estimating the reliability polynomial. The new algorithm runs in expected time O(mlogn α(m,n)) at worst and ≈m in practice, compared to Θ(m ²) for the previous algorithm. We analyze the error bounds of this algorithm, including comparison to alternative estimation algorithms. In addition to the theoretical analysis, we discuss methods for estimating the variance and describe experimental results on a variety of random graphs.     

Improved fixed parameter tractable algorithms for two “edge” problems: MAXCUT and MAXDAG

We give improved parameterized algorithms for two “edge” problems MAXCUT and MAXDAG, where the solution sought is a subset of edges. MAXCUT of a graph is a maximum set of edges forming a bipartite subgraph of the given graph. On the other hand, MAXDAG of a directed graph is a set of arcs of maximum size such that the graph induced on these arcs is acyclic. Our algorithms are obtained through new kernelization and efficient exact algorithms for the optimization versions of the problems. More precisely our results include:

(i)

a kernel with at most αk vertices and βk edges for MAXCUT. Here 0<α?1 and 1<β?2. Values of α and β depends on the number of vertices and the edges in the graph;

(ii)

a kernel with at most 4k/3 vertices and 2k edges for MAXDAG;

(iii)

an O^∗(k^1.2418) parameterized algorithm for MAXCUT in undirected graphs. This improves the O^∗(k^1.4143)¹ algorithm presented in [E. Prieto, The method of extremal structure on the k-maximum cut problem, in: The Proceedings of Computing: The Australasian Theory Symposium (CATS), 2005, pp. 119-126];

(iv)

an O^∗(n²) algorithm for optimization version of MAXDAG in directed graphs. This is the first such algorithm to the best of our knowledge;

(v)

an O^∗(k²) parameterized algorithm for MAXDAG in directed graphs. This improves the previous best of O^∗(k⁴) presented in [V. Raman, S. Saurabh, Parameterized algorithms for feedback set problems and their duals in tournaments, Theoretical Computer Science 351 (3) (2006) 446-458];

(vi)

an O^∗(k¹⁶) parameterized algorithm to determine whether an oriented graph having m arcs has an acyclic subgraph with at least m/2+k arcs. This improves the O^∗(k²) algorithm given in [V. Raman, S. Saurabh, Parameterized algorithms for feedback set problems and their duals in tournaments, Theoretical Computer Science 351 (3) (2006) 446-458].

In addition, we show that if a directed graph has minimum out degree at least f(n) (some function of n) then Directed Feedback Arc Set problem is fixed parameter tractable. The parameterized complexity of Directed Feedback Arc Set is a well-known open problem.     

An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs

A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is an evidence that can be used to authenticate the correctness of the answer. A Hamiltonian cycle in a graph is a simple cycle in which each vertex of the graph appears exactly once. The Hamiltonian cycle problem is to determine whether or not a graph contains a Hamiltonian cycle. The best result for the Hamiltonian cycle problem on circular-arc graphs is an O(n²logn)-time algorithm, where n is the number of vertices of the input graph. In fact, the O(n²logn)-time algorithm can be modified as a certifying algorithm although it was published before the term certifying algorithms appeared in the literature. However, whether there exists an algorithm whose time complexity is better than O(n²logn) for solving the Hamiltonian cycle problem on circular-arc graphs has been opened for two decades. In this paper, we present an O(Δn)-time certifying algorithm to solve this problem, where Δ represents the maximum degree of the input graph. The certificates provided by our algorithm can be authenticated in O(n) time.     

A new analysis of a self-stabilizing maximum weight matching algorithm with approximation ratio 2

The maximum weight matching problem is a fundamental problem in graph theory with a variety of important applications. Recently Manne and Mjelde presented the first self-stabilizing algorithm computing a 2-approximation of the optimal solution. They established that their algorithm stabilizes after O(2ⁿ) (resp. O(3ⁿ)) moves under a central (resp. distributed) scheduler. This paper contributes a new analysis, improving these bounds considerably. In particular it is shown that the algorithm stabilizes after O(nm) moves under the central scheduler and that a modified version of the algorithm also stabilizes after O(nm) moves under the distributed scheduler. The paper presents a new proof technique based on graph reduction for analyzing the complexity of self-stabilizing algorithms.     

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.     

Trash removal algorithm for fast construction of the elliptic Gabriel graph using Delaunay triangulation

Given a set of points P, finding near neighbors among the points is an important problem in many applications in CAD/CAM, computer graphics, computational geometry, etc. In this paper, we propose an efficient algorithm for constructing the elliptic Gabriel graph (EGG), which is a generalization of the well-known Gabriel graph and parameterized by a non-negative value α. Our algorithm is based on the observation that a candidate point which may define an edge of an EGG with a given point p∈P is always in the scaled Voronoi region of p with a scale factor 2/α² when the parameter α<1. From this observation, we can reduce the search space for locating neighbors of p in the EGG. For the case of α≥1, due to the fact that EGG is a subgraph of the Delaunay graph of P, EGG can be efficiently computed by watching the validity of each edge in the Delaunay graph. The proposed algorithm is shown to have its time complexity as O(n³) in the worst case and O(n) in the average case when α is moderately close to unity. The idea presented in this paper may similarly apply to other problems for the proximity search for point sets.     

An efficient algorithm for minimum feedback vertex sets in rotator graphs

For a rotator graph with n! nodes, Hsu and Lin [C.C. Hsu, H.R. Lin, H.C. Chang, K.K. Lin, Feedback Vertex Sets in Rotator Graphs, in: Lecture Notes in Comput. Sci., vol. 3984, 2006, pp. 158-164] first proposed an algorithm which constructed a feedback vertex set (FVS) with time complexity O(nn−3). In addition, they found that the size of the FVS is n!/3, which was proved to be minimum. In this paper, we present an efficient algorithm which constructs an FVS for a rotator graph in O(n!) time and also obtains the minimum FVS size n!/3. In other words, this algorithm derives the optimal result with linear time complexity in terms of the number of nodes in the rotator graph.     

Optimal per-edge processing times in the semi-streaming model

We present semi-streaming algorithms for basic graph problems that have optimal per-edge processing times and therefore surpass all previous semi-streaming algorithms for these tasks. The semi-streaming model, which is appropriate when dealing with massive graphs, forbids random access to the input and restricts the memory to bits.Particularly, the formerly best per-edge processing times for finding the connected components and a bipartition are O(α(n)), for determining k-vertex and k-edge connectivity O(k²n) and O(n⋅logn) respectively for any constant k and for computing a minimum spanning forest O(logn). All these time bounds we reduce to O(1).Every presented algorithm determines a solution asymptotically as fast as the best corresponding algorithm up to date in the classical RAM model, which therefore cannot convert the advantage of unlimited memory and random access into superior computing times for these problems.     

Minimum cycle bases of weighted outerplanar graphs

We give the first optimal algorithm that computes a minimum cycle basis for any weighted outerplanar graph. Specifically, for any n-node edge-weighted outerplanar graph G, we give an O(n)-time algorithm to obtain an O(n)-space compact representation Z(C) for a minimum cycle basis C of G. Each cycle in C can be computed from Z(C) in O(1) time per edge. Our result works for directed and undirected outerplanar graphs G.     

Approximating maximum weight K-colorable subgraphs in chordal graphs

We present a 2-approximation algorithm for the problem of finding the maximum weight K-colorable subgraph in a given chordal graph with node weights. The running time of the algorithm is O(K(n+m)), where n and m are the number of vertices and edges in the given graph.     

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.     

A 2-approximation NC algorithm for connected vertex cover and tree cover

The connected vertex cover problem is a variant of the vertex cover problem, in which a vertex cover is additional required to induce a connected subgraph in a given connected graph. The problem is known to be NP-hard and to be at least as hard to approximate as the vertex cover problem is. While several 2-approximation NC algorithms are known for vertex cover, whether unweighted or weighted, no parallel algorithm with guaranteed approximation is known for connected vertex cover. Moreover, converting the existing sequential 2-approximation algorithms for connected vertex cover to parallel ones results in RNC algorithms of rather high complexity at best.In this paper we present a 2-approximation NC (and RNC) algorithm for connected vertex cover (and tree cover). The NC algorithm runs in O(log²n) time using O(Δ²(m+n)/logn) processors on an EREW-PRAM, while the RNC algorithm runs in O(logn) expected time using O(m+n) processors on a CRCW-PRAM, when a given graph has n vertices and m edges with maximum vertex degree of Δ.     

A simple algorithm to find Hamiltonian cycles in proper interval graphs

We present an algorithm to find a Hamiltonian cycle in a proper interval graph in O(m+n) time, where m is the number of edges and n is the number of vertices in the graph. The algorithm is simpler and shorter than previous algorithms for the problem.     

An efficient distributed algorithm for maximum matching in general graphs

We present a distributed algorithm for maximum cardinality matching in general graphs. On a general graph withn vertices, our algorithm requiresO(n ^5/2) messages in the worst case. On trees, our algorithm computes a maximum matching usingO(n) messages after the election of a leader.Work on this paper has been supported by the Office of Naval Research under Contract N00014-85-K-0570.     

Relative neighborhood graphs in the Li-metric

The relative neighborhood graph of a set of n points in the plane under the L₁-metric is considered. An algorithm that runs in O(nlog n) time for constructing the relative neighborhood graph based on the Delaunay triangulation is presented, improving a previously known algorithm that runs in O(n²log n) time.