Serial and Parallel Algorithms for (k,2)-Partite Graphs

We introduce a class of layered graphs which we call (k,2)-partite and which we argue are an interesting class because of several important applications. We show that testing for (k,2)-partiteness can be done efficiently both on sequential and parallel machines, by showing that membership is in NSPACE(log n) and in NC². We show that (k,2)-partite graphs have bounded path width. We then show that a particular NP-complete problem, namely Maximum Independent Set, is solvable in linear time on bounded pathwidth graphs if the path decomposition is included in the input. Finally, we show that the Maximum Independent Set problem is in NC² for (k,2)-partite graphs. We note that linear time solutions for certain NP-complete problems have been shown for a wider class of graphs, namely partial k-trees. Our linear time algorithm is somewhat simpler in structure. We conjecture that our techniques can be used on many NP-complete problems to yield efficient algorithms for (k,2)-partite graphs.     

Partition Into Triangles on Bounded Degree Graphs

We consider the Partition Into Triangles problem on bounded degree graphs. We show that this problem is polynomial-time solvable on graphs of maximum degree three by giving a linear-time algorithm. We also show that this problem becomes $\mathcal{NP}$ -complete on graphs of maximum degree four. Moreover, we show that there is no subexponential-time algorithm for this problem on graphs of maximum degree four unless the Exponential-Time Hypothesis fails. However, the Partition Into Triangles problem on graphs of maximum degree at most four is in many cases practically solvable as we give an algorithm for this problem that runs in $\mathcal{O}(1.02220^{n})$ time and linear space.     

Algorithmic Meta-theorems for Restrictions of Treewidth

Possibly the most famous algorithmic meta-theorem is Courcelle??s theorem, which states that all MSO-expressible graph properties are decidable in linear time for graphs of bounded treewidth. Unfortunately, the running time??s dependence on the formula describing the problem is in general a tower of exponentials of unbounded height, and there exist lower bounds proving that this cannot be improved even if we restrict ourselves to deciding FO logic on trees. We investigate whether this parameter dependence can be improved by focusing on two proper subclasses of the class of bounded treewidth graphs: graphs of bounded vertex cover and graphs of bounded max-leaf number. We prove stronger algorithmic meta-theorems for these more restricted classes of graphs. More specifically, we show it is possible to decide any FO property in both of these classes with a singly exponential parameter dependence and that it is possible to decide MSO logic on graphs of bounded vertex cover with a doubly exponential parameter dependence. We also prove lower bound results which show that our upper bounds cannot be improved significantly, under widely believed complexity assumptions. Our work addresses an open problem posed by Michael Fellows.     

A simple and fast parallel coloring for distance-hereditary graphs

In the literature, there are quite a few sequential and parallel algorithms to solve problems on distance-hereditary graphs. Two well-known classes of graphs, which contain trees and cographs, belong to distance-hereditary graphs. We consider the vertex-coloring problem on distance-hereditary graphs. Let T/sub d/(|V|, |E|) and P/sub d/d(|V|, |E|) denote the time and processor complexities, respectively, required to construct a decomposition tree representation of a distance-hereditary graph G=(V,E) on a PRAM model M/sub d/. Our algorithm runs in O(T/sub d/(|V|, |E|)+log|V|) time using O(P/sub d/(|V|, |E|)+|V|/log|V|) processors on M/sub d/. The best known result for constructing a decomposition tree needs O(log/sup 2/ |V|) time using O(|V|+|E|) processors on a CREW PRAM. If a decomposition tree is provided as input, we solve the problem in O(log |V|) time using O(|V|/log |V|) processors on an EREW PRAM. To the best of our knowledge, there is no parallel algorithm for this problem on distance-hereditary graphs.     

Linear structure of bipartite permutation graphs and the longest path problem

The class of bipartite permutation graphs is the intersection of two well known graph classes: bipartite graphs and permutation graphs. A complete bipartite decomposition of a bipartite permutation graph is proposed in this note. The decomposition gives a linear structure of bipartite permutation graphs, and it can be obtained in O(n) time, where n is the number of vertices. As an application of the decomposition, we show an O(n) time and space algorithm for finding a longest path in a bipartite permutation graph.     

Exponential Speedup of Fixed-Parameter Algorithms for Classes of Graphs Excluding Single-Crossing Graphs as Minors

We present a fixed-parameter algorithm that constructively solves the $k$-dominating set problem on any class of graphs excluding a single-crossing graph (a graph that can be drawn in the plane with at most one crossing) as a minor in $O(4^{9.55\sqrt{k}}n^{O(1)})$ time. Examples of such graph classes are the $K_{3,3}$-minor-free graphs and the $K_{5}$-minor-free graphs. As a consequence, we extend our results to several other problems such as vertex cover, edge dominating set, independent set, clique-transversal set, kernels in digraphs, feedback vertex set, and a collection of vertex-removal problems. Our work generalizes and extends the recent results of exponential speedup in designing fixed-parameter algorithms on planar graphs due to Alber et al. to other (nonplanar) classes of graphs.     

Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition

We study the distributed maximal independent set (henceforth, MIS) problem on sparse graphs. Currently, there are known algorithms with a sublogarithmic running time for this problem on oriented trees and graphs of bounded degrees. We devise the first sublogarithmic algorithm for computing an MIS on graphs of bounded arboricity. This is a large family of graphs that includes graphs of bounded degree, planar graphs, graphs of bounded genus, graphs of bounded treewidth, graphs that exclude a fixed minor, and many other graphs. We also devise efficient algorithms for coloring graphs from these families. These results are achieved by the following technique that may be of independent interest. Our algorithm starts with computing a certain graph-theoretic structure, called Nash-Williams forests-decomposition. Then this structure is used to compute the MIS or coloring. Our results demonstrate that this methodology is very powerful. Finally, we show nearly-tight lower bounds on the running time of any distributed algorithm for computing a forests-decomposition.     

Distributed algorithms for ultrasparse spanners and linear size skeletons

We present efficient algorithms for computing very sparse low distortion spanners in distributed networks and prove some non-trivial lower bounds on the tradeoff between time, sparseness, and distortion. All of our algorithms assume a synchronized distributed network, where relatively short messages may be communicated in each time step. Our first result is a fast distributed algorithm for finding an ${O(2^{{\rm log}^{*} n} {\rm log} n)}We present efficient algorithms for computing very sparse low distortion spanners in distributed networks and prove some non-trivial lower bounds on the tradeoff between time, sparseness, and distortion. All of our algorithms assume a synchronized distributed network, where relatively short messages may be communicated in each time step. Our first result is a fast distributed algorithm for finding an O(2^{log* n} log n){O(2^{{\rm log}^{*} n} {\rm log} n)} -spanner with size O(n). Besides being nearly optimal in time and distortion, this algorithm appears to be the first that constructs an O(n)-size skeleton without requiring unbounded length messages or time proportional to the diameter of the network. Our second result is a new class of efficiently constructible (α, β)-spanners called Fibonacci spanners whose distortion improves with the distance being approximated. At their sparsest Fibonacci spanners can have nearly linear size, namely O(n(loglogn)^f){O(n(\log \log n)^{\phi})} , where f = (1 + ?5)/2{\phi = (1 + \sqrt{5})/2} is the golden ratio. As the distance increases the multiplicative distortion of a Fibonacci spanner passes through four discrete stages, moving from logarithmic to log-logarithmic, then into a period where it is constant, tending to 3, followed by another period tending to 1. On the lower bound side we prove that many recent sequential spanner constructions have no efficient counterparts in distributed networks, even if the desired distortion only needs to be achieved on the average or for a tiny fraction of the vertices. In particular, any distance preservers, purely additive spanners, or spanners with sublinear additive distortion must either be very dense, slow to construct, or have very weak guarantees on distortion.     

A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs

This paper concerns a domination problem in graphs with parity constraints. The task is to find a subset of the vertices with minimum cost such that for every vertex the number of chosen vertices in its neighbourhood has a prespecified parity. This problem is known to be ${\mathcal NP}$ -hard for general graphs. A linear time algorithm was developed for series-parallel graphs and trees with unit cost and restricted to closed neighbourhoods. We present a linear time algorithm for the parity domination problem with open and closed neighbourhoods and arbitrary cost functions on graphs with bounded treewidth and distance-hereditary graphs.     

Polynomial-Time Algorithms for Energy Games with Special Weight Structures

Energy games belong to a class of turn-based two-player infinite-duration games played on a weighted directed graph. It is one of the rare and intriguing combinatorial problems that lie in NP∩co-NP, but are not known to be in P. The existence of polynomial-time algorithms has been a major open problem for decades and apart from pseudopolynomial algorithms there is no algorithm that solves any non-trivial subclass in polynomial time. In this paper, we give several results based on the weight structures of the graph. First, we identify a notion of penalty and present a polynomial-time algorithm when the penalty is large. Our algorithm is the first polynomial-time algorithm on a large class of weighted graphs. It includes several worst-case instances on which previous algorithms, such as value iteration and random facet algorithms, require at least sub-exponential time. Our main technique is developing the first non-trivial approximation algorithm and showing how to convert it to an exact algorithm. Moreover, we show that in a practical case in verification where weights are clustered around a constant number of values, the energy game problem can be solved in polynomial time. We also show that the problem is still as hard as in general when the clique-width is bounded or the graph is strongly ergodic, suggesting that restricting the graph structure does not necessarily help.     

Generalized Model-Checking over Locally Tree-Decomposable Classes

It has been proved in Frick and Grohe that properties of graphs or other relational structures that are definable in first-order logic can be decided in linear time when the input structures are restricted to come from a {\em locally tree-decomposable} class of structures. Important examples of such classes are the class of planar graphs and classes of graphs of bounded degree. In this paper we consider more general computational problems than decision problems, which are induced by formulas with free variables. In this generalized setting we investigate the construction (find a satisfying assignment), listing (all satisfying assignments) and counting (compute the number of satisfying assignments) problems for formulas of first-order logic. We show that each of these problems can be solved in linear time on locally tree-decomposable classes of structures. For instance, we devise an algorithm that, given a planar graph $\cal G$ and a first-order logic formula $\phi(\barx)$, computes a $\bara \in G$ such that $\cal G \models \phi(\bara)$ in time $f(||\phi||) \cdot ||\cal G||$ for some computable function $f$ (the construction case). Accordingly, we obtain linear time algorithms for the counting and listing cases.     

Optimal Reconstruction of Graphs under the Additive Model

We study the problem of reconstructing unknown graphs under the additive combinatorial search model. The main result concerns the reconstruction of bounded degree graphs, i.e., graphs with the degree of all vertices bounded by a constant d . We show that such graphs can be reconstructed in O(dn) nonadaptive queries, which matches the information-theoretic lower bound. The proof is based on the technique of separating matrices. A central result here is a new upper bound for a general class of separating matrices. As a particular case, we obtain a tight upper bound for the class of d -separating matrices, which settles an open question stated by Lindstr?m in [20]. Finally, we consider several particular classes of graphs. We show how an optimal nonadaptive solution of O(n ² / log n) queries for general graphs can be obtained. We also prove that trees with unbounded vertex degree can be reconstructed in a linear number of queries by a nonadaptive algorithm. Received August 1997; revised January 1999.     

Distributed predicate detection in series-parallel systems

This paper addresses the problems of state space decomposition and predicate detection in a distributed computation involving asynchronous messages. We introduce a natural communication dependency which leads to the definition of the communication graph. This abstraction proves to be a useful tool to decompose the state lattice of a distributed computation into simpler structures, known as concurrent intervals. Efficient algorithms have been proposed in the literature to detect special classes of predicates, such as conjunctive predicates and bounded sum predicates. We show that more general classes of predicates can be detected when proper constraints are imposed on the underlying computations. In particular, we introduce a class of predicates, defined as separable predicates, that properly includes the above-mentioned classes. We show that separable predicates can be efficiently detected on distributed computations whose communication graphs satisfy the series-parallel constraint     

Truss decomposition of uncertain graphs

The k-truss of a graph is the largest edge-induced subgraph such that every edge is contained in at least k triangles within the subgraph, where a triangle is a cycle consisting of three vertices. As a new notion of cohesive subgraphs, truss has recently attracted a lot of research attentions in the database and data mining fields. At the same time, uncertainty is an intrinsic property of massive graph data, and truss decomposition (i.e., finding all k-trusses of a graph) has become a key primitive on uncertain graphs. In this paper, we study the truss decomposition problem on uncertain graphs, that is, finding all highly probable k-trusses of an uncertain graph. We first give an formal statement of the truss decomposition problem on uncertain graphs. Then, we prove that the truss decomposition of an uncertain graph attains two elegant properties, namely uniqueness and hierarchy. We show that the truss decomposition of an uncertain graph can be found in \(O(m^{1.5}Q)\) time by proposing an in-memory algorithm called \(\mathtt {TD_{mem}}\), where m is the number of edges of the uncertain graph, and Q is at most the maximum number of common neighbors of the endpoints of an edge. When an uncertain graph is too large to fit into main memory, we propose an external-memory algorithm \(\mathtt {TD_{I/O}}\) to find the truss decomposition of the uncertain graph. Extensive experiments have been carried out to evaluate the practical performance of the proposed algorithms. The experimental results verify that both \(\mathtt {TD_{mem}}\) and \(\mathtt {TD_{I/O}}\) are efficient when an uncertain graph is small enough to fit into main memory, and that \(\mathtt {TD_{I/O}}\) is much faster than \(\mathtt {TD_{mem}}\) when the graph is too large to fit into main memory.     

Drawing Planar Graphs Symmetrically, II: Biconnected Planar Graphs

Symmetry is one of the most important aesthetic criteria in graph drawing because it reveals the structure in the graph. This paper discusses symmetric drawings of biconnected planar graphs. More specifically, we discuss geometric automorphisms, that is, automorphisms of a graph G that can be represented as symmetries of a drawing of G. Finding geometric automorphisms is the first and most difficult step in constructing symmetric drawings of graphs. The problem of determining whether a given graph has a non-trivial geometric automorphism is NP-complete for general graphs. In this paper we present a linear time algorithm for finding planar geometric automorphisms of biconnected planar graphs. A drawing algorithm is also discussed.     

New graph decompositions with applications to emulations

In this paper we present a new type of graph decomposition calleda cut-cover that combines the notions of graph separators andt-neighborhood covers. We show that graphs with good cut-covers can be emulated in hypercubes and we show that planar and certain minor-excluded graphs have good cut-covers. In particular, we show how to emulate anyN-node bounded degree planar graph or anyN-node bounded degree graph that excludes $K_{log^{0(1)} N} $ as a minor with constant slowdown on hypercube networks.     

Parameterized Complexity of the Spanning Tree Congestion Problem

We study the problem of determining the spanning tree congestion of a?graph. We present some sharp contrasts in the parameterized complexity of this problem. First, we show that on apex-minor-free graphs, a general class of graphs containing planar graphs, graphs of bounded treewidth, and graphs of bounded genus, the problem to determine whether a given graph has spanning tree congestion at most k can be solved in linear time for every fixed k. We also show that for every fixed k and d the problem is solvable in linear time for graphs of degree at most d. In contrast, if we allow only one vertex of unbounded degree, the problem immediately becomes NP-complete for any fixed k??8. Moreover, the hardness result holds for graphs excluding the complete graph on 6 vertices as a minor. We also observe that for k??3 the problem becomes polynomially time solvable.     

On approximating the longest path in a graph

We consider the problem of approximating the longest path in undirected graphs. In an attempt to pin down the best achievable performance ratio of an approximation algorithm for this problem, we present both positive and negative results. First, a simple greedy algorithm is shown to find long paths in dense graphs. We then consider the problem of finding paths in graphs that are guaranteed to have extremely long paths. We devise an algorithm that finds paths of a logarithmic length in Hamiltonian graphs. This algorithm works for a much larger class of graphs (weakly Hamiltonian), where the result is the best possible. Since the hard case appears to be that of sparse graphs, we also consider sparse random graphs. Here we show that a relatively long path can be obtained, thereby partially answering an open problem of Broderet al. To explain the difficulty of obtaining better approximations, we also prove hardness results. We show that, for any ε<1, the problem of finding a path of lengthn-n ^ε in ann-vertex Hamiltonian graph isNP-hard. We then show that no polynomial-time algorithm can find a constant factor approximation to the longest-path problem unlessP=NP. We conjecture that the result can be strengthened to say that, for some constant δ>0, finding an approximation of ration ^δ is alsoNP-hard. As evidence toward this conjecture, we show that if any polynomial-time algorithm can approximate the longest path to a ratio of , for any ε>0, thenNP has a quasi-polynomial deterministic time simulation. The hardness results apply even to the special case where the input consists of bounded degree graphs. D. Karger was supported by an NSF Graduate Fellowship, NSF Grant CCR-9010517, and grants from the Mitsubishi Corporation and OTL. R. Motwani was supported by an Alfred P. Sloan Research Fellowship, an IBM Faculty Development Award, grants from Mitsubishi and OTL, NSF Grant CCR-9010517, and NSF Young Investigator Award CCR-9357849, with matching funds from IBM, the Schlumberger Foundation, the Shell Foundation, and the Xerox Corporation, G. D. S. Ramkumar was supported by a grant from the Toshiba Corporation. Communicated by M. X. Goemans.     

An efficient parallel algorithm for the longest path problem in meshes

The longest path problem is the problem of finding a simple path with the maximum number of vertices in a given graph, and so far it has been solved polynomially only for a few classes of graphs. This problem generalizes the well-known Hamiltonian path problem, hence it is NP-hard in general graphs. In this paper, first we give a sequential linear-time algorithm for the longest path problem in meshes. Then based on this algorithm, we present a constant-time parallel algorithm for the problem, which can be run on every parallel machine.     

Logarithmic Barrier Decomposition Methods for Semi-infinite Programming

A computational study of some logarithmic barrier decomposition algorithms for semi-infinite programming is presented in this paper. The conceptual algorithm is a straightforward adaptation of the logarithmic barrier cutting plane algorithm which was presented recently by den Hartog et al. ( Annals of Operations Research , 58 , 69–98, 1995), to solve semi-infinite programming problems. Usually decomposition (cutting plane methods) use cutting planes to improve the localization of the given problem. In this paper we propose an extension which uses linear cuts to solve large scale, difficult real world problems. This algorithm uses both static and (doubly) dynamic enumeration of the parameter space and allows for multiple cuts to be simultaneously added for larger/difficult problems. The algorithm is implemented both on sequential and parallel computers. Implementation issues and parallelization strategies are discussed and encouraging computational results are presented.