Search

We initiate the investigation of the parameterized complexity of Diameter and Connectivity in the streaming paradigm. On the positive end, we show that knowing a vertex cover of size k allows for algorithms in the Adjacency List (AL) streaming model whose number of passes is constant and memory is O (log n) for any fixed k. Underlying these algorithms is a method to execute a breadth-first search in O (k) passes and O (k log n) bits of memory. On the negative end, we show that many other parameters lead to lower bounds in the AL model, where Ω (n / p) bits of memory is needed for any p-pass algorithm even for constant parameter values. In particular, this holds for graphs with a known modulator (deletion set) of constant size to a graph that has no induced subgraph isomorphic to a fixed graph H, for most H. For some cases, we can also show one-pass, Ω (n log n) bits of memory lower bounds. We also prove a much stronger Ω (n 2 / p) lower bound for Diameter on bipartite graphs. Finally, using the insights we developed into streaming parameterized graph exploration algorithms, we show a new streaming kernelization algorithm for computing a vertex cover of size k. This yields a kernel of 2k vertices (with O (k 2) edges) produced as a stream in poly (k) passes and only O (k log n) bits of memory. [ABSTRACT FROM AUTHOR]

A permutation is happy, if it can be transformed into the identity permutation using as many short swaps as one third times the number of inversions in the permutation. The complexity of the decision version of sorting a permutation by short swaps, is still open. We present an O(n) time algorithm to decide whether it is true for a permutation to be happy, where n is the number of elements in the permutation. If a permutation is happy, we give an O (n 2) time algorithm to find a sequence of as many short swaps as one third times the number of its inversions, to transform it into the identity permutation. A permutation is lucky, if it can be transformed into the identity permutation using as many short swaps as one fourth times the length sum of the permutation's element vectors. We present an O(n) time algorithm to decide whether it is true for a permutation to be lucky, where n is the number of elements in the permutation. If a permutation is lucky, we give an O (n 2) time algorithm to find a sequence of as many short swaps as one fourth times the length sum of its element vectors to transform it into the identity permutation. This improves upon the O (n 2) time algorithm proposed by Heath and Vergara to decide whether a permutation is lucky. We show that there are at least 2 ⌈ n 2 ⌉ - 2 happy permutations as well as 2 n - 4 lucky permutations of n elements. [ABSTRACT FROM AUTHOR]

We study a continuous facility location problem on a graph where all edges have unit length and where the facilities may also be positioned in the interior of the edges. The goal is to position as many facilities as possible subject to the condition that any two facilities have at least distance δ from each other. We investigate the complexity of this problem in terms of the rational parameter δ . The problem is polynomially solvable, if the numerator of δ is 1 or 2, while all other cases turn out to be NP-hard. [ABSTRACT FROM AUTHOR]

Our input is a complete graph G on n vertices where each vertex has a strict ranking of all other vertices in G. The goal is to construct a matching in G that is popular. A matching M is popular if M does not lose a head-to-head election against any matching M ′ : here each vertex casts a vote for the matching in { M , M ′ } in which it gets a better assignment. Popular matchings need not exist in the given instance G and the popular matching problem is to decide whether one exists or not. The popular matching problem in G is easy to solve for odd n. Surprisingly, the problem becomes NP -complete for even n, as we show here. This is one of the few graph theoretic problems efficiently solvable when n has one parity and NP -complete when n has the other parity. [ABSTRACT FROM AUTHOR]

In the localization game, introduced by Seager in 2013, an invisible and immobile target is hidden at some vertex of a graph G. At every step, one vertex v of G can be probed which results in the knowledge of the distance between v and the secret location of the target. The objective of the game is to minimize the number of steps needed to locate the target whatever be its location. We address the generalization of this game where k ≥ 1 vertices can be probed at every step. Our game also generalizes the notion of the metric dimension of a graph. Precisely, given a graph G and two integers k , ℓ ≥ 1 , the Localization problem asks whether there exists a strategy to locate a target hidden in G in at most ℓ steps and probing at most k vertices per step. We first show that, in general, this problem is NP-complete for every fixed k ≥ 1 (resp., ℓ ≥ 1 ). We then focus on the class of trees. On the negative side, we prove that the Localization problem is NP-complete in trees when k and ℓ are part of the input. On the positive side, we design a (+ 1) -approximation algorithm for the problem in n-node trees, i.e., an algorithm that computes in time O (n log n) (independent of k) a strategy to locate the target in at most one more step than an optimal strategy. This algorithm can be used to solve the Localization problem in trees in polynomial time if k is fixed. We also consider some of these questions in the context where, upon probing the vertices, the relative distances to the target are retrieved. This variant of the problem generalizes the notion of the centroidal dimension of a graph. [ABSTRACT FROM AUTHOR]

The crossing number is the smallest number of pairwise edge crossings when drawing a graph into the plane. There are only very few graph classes for which the exact crossing number is known or for which there at least exist constant approximation ratios. Furthermore, up to now, general crossing number computations have never been successfully tackled using bounded width of graph decompositions, like treewidth or pathwidth. In this paper, we show that the crossing number is tractable (even in linear time) for maximal graphs of bounded pathwidth 3. The technique also shows that the crossing number and the rectilinear (a.k.a. straight-line) crossing number are identical for this graph class, and that we require only an O (n) × O (n) -grid to achieve such a drawing. Our techniques can further be extended to devise a 2-approximation for general graphs with pathwidth 3. One crucial ingredient here is that the crossing number of a graph with a separation pair can be lower-bounded using the crossing numbers of its cut-components, a result that may be interesting in its own right. Finally, we give a 4 w 3 -approximation of the crossing number for maximal graphs of pathwidth w . This is a constant approximation for bounded pathwidth. We complement this with an NP-hardness proof of the weighted crossing number already for pathwidth 3 graphs and bicliques K 3 , n . [ABSTRACT FROM AUTHOR]

This paper deals with fairness in stable marriage problems. The idea studied here is to achieve fairness thanks to a Generalized Gini Index (GGI), a well-known criterion in inequality measurement, that includes both the egalitarian and utilitarian criteria as special cases. We show that determining a stable marriage optimizing a GGI criterion of agents' disutilities is an NP-hard problem. We then provide a polynomial time 2-approximation algorithm in the general case, as well as an exact algorithm which is polynomial time in the case of a constant number of non-zero weights parametrizing the GGI criterion. [ABSTRACT FROM AUTHOR]

We consider a one-to-one assignment problem consisting of matching n objects with n agents. Any matching leads to a utility vector whose n components measure the satisfaction of the various agents. We want to find an assignment maximizing a global utility defined as an ordered weighted average (OWA) of the n individual utilities. OWA weights are assumed to be non-increasing with ranks of satisfaction so as to include an idea of fairness in the definition of social utility. We first prove that the problem is NP-hard; then we propose a polynomial algorithm under some restrictions on the set of admissible weight vectors, proving that the problem belongs to XP. [ABSTRACT FROM AUTHOR]

This paper is devoted to new results about the scaffolding problem, an integral problem of genome inference in bioinformatics. The problem consists in finding a collection of disjoint cycles and paths covering a particular graph called the “scaffold graph”. We examine the difficulty and the approximability of the scaffolding problem in special classes of graphs, either close to trees, or very dense. We propose negative and positive results, exploring the frontier between difficulty and tractability of computing and/or approximating a solution to the problem. Also, we explore a new direction through related problems consisting in finding a family of edges having a strong effect on solution weight. [ABSTRACT FROM AUTHOR]

We investigate the structural and algorithmic properties of 2-community structures in graphs introduced recently by Olsen (Math Soc Sci 66(3):331-336, 2013). A 2-community structure is a partition of a vertex set into two parts such that for each vertex the numbers of neighbours in/outside its own part and the sizes of the parts are correlated. We show that some well studied graph classes as graphs of maximum degree 3, minimum degree at least |V|-3, trees and also others, have always a 2-community structure. Furthermore, a 2-community structure can be found in polynomial time in all these classes, even with additional request of connectivity in both parts. We introduce a concept of a weak 2-community and prove that in general graphs it is NP-complete to find a balanced weak 2-community structure with or without request for connectivity in both parts. On the other hand, we present a polynomial-time algorithm to solve the problem (without the condition for connectivity of parts) in graphs of degree at most 3. [ABSTRACT FROM AUTHOR]

Motivated by routing in telecommunication network using Software Defined Network (SDN) technologies, we consider the following problem of finding short routing lists using aggregation rules. We are given a set of communications $$\mathcal {X}$$ , which are distinct pairs $$(s,t)\subseteq S\times T$$ , (typically S is the set of sources and T the set of destinations), and a port function $$\pi :\mathcal {X} \rightarrow P$$ where P is the set of ports. A routing list $$\mathcal {R}$$ is an ordered list of triples which are of the form ( s, t, p), $$(*,t,p)$$ , $$(s,*,p)$$ or $$(*,*,p)$$ with $$s\in S$$ , $$t\in T$$ and $$p\in P$$ . It routes the communication ( s, t) to the port $$r(s,t) =p$$ which appears on the first triple in the list $$\mathcal {R}$$ that is of the form ( s, t, p), $$(*,t,p)$$ , $$(s,*,p)$$ or $$(*,*,p)$$ . If $$r(s,t)=\pi (s,t)$$ , then we say that ( s, t) is properly routed by $$\mathcal {R}$$ and if all communications of $$\mathcal {X}$$ are properly routed, we say that $$\mathcal {R}$$ emulates $$(\mathcal {X}, \pi )$$ . The aim is to find a shortest routing list emulating $$(\mathcal {X}, \pi )$$ . In this paper, we carry out a study of the complexity of the two dual decision problems associated to it. Given a set of communication $$\mathcal {X}$$ , a port function $$\pi $$ and an integer k, the first one called Routing List (resp. the second one, called List Reduction) consists in deciding whether there is a routing list emulating $$(\mathcal {X}, \pi )$$ of size at most k (resp. $$|\mathcal {X}| -k$$ ). We prove that both problems are NP-complete. We then give a 3-approximation for List Reduction, which can be generalized to higher dimensions. We also give a 4-approximation for Routing List in the fundamental case when there are only two ports (i.e. $$|P|=2$$ ), $$\mathcal {X}=S\times T$$ and $$|S|=|T|$$ . [ABSTRACT FROM AUTHOR]

We consider the problems of finding optimal identifying codes, (open) locating-dominating sets and resolving sets (denoted Identifying Code, (Open) Open Locating-Dominating Set and Metric Dimension) of an interval or a permutation graph. In these problems, one asks to distinguish all vertices of a graph by a subset of the vertices, using either the neighbourhood within the solution set or the distances to the solution vertices. Using a general reduction for this class of problems, we prove that the decision problems associated to these four notions are NP-complete, even for interval graphs of diameter 2 and permutation graphs of diameter 2. While Identifying Code and (Open) Locating-Dominating Set are trivially fixed-parameter-tractable when parameterized by solution size, it is known that in the same setting Metric Dimension is W[2]-hard. We show that for interval graphs, this parameterization of Metric Dimension is fixed-parameter-tractable. [ABSTRACT FROM AUTHOR]

This paper deals with a matching game in which the nodes of a simple graph are independent agents who try to form pairs. If we let the agents make their decision without any central control then a possible outcome is a Nash equilibrium, that is a situation in which no unmatched player can change his strategy and find a partner. However, there can be a big difference between two possible outcomes of the same instance, in terms of number of matched nodes. A possible solution is to force all the nodes to follow a centrally computed maximum matching but it can be difficult to implement this approach. This article proposes a tradeoff between the total absence and the full presence of a central control. Concretely, we study the optimization problem where the action of a minimum number of agents is centrally fixed and any possible equilibrium of the modified game must be a maximum matching. In algorithmic game theory, this approach is known as the price of optimum of a game. For the price of optimum of the matching game, deciding whether a solution is feasible is not straightforward, but we prove that it can be done in polynomial time. In addition, the problem is shown APX-hard, since its restriction to graphs admitting a perfect matching is equivalent, from the approximability point of view, to vertex cover. Finally we prove that this problem admits a polynomial 6-approximation algorithm in general graphs. [ABSTRACT FROM AUTHOR]

The Weighted Vertex Integrity (wVI) problem takes as input an n-vertex graph G, a weight function $$w:V(G)\rightarrow {\mathbb {N}}$$ , and an integer p. The task is to decide if there exists a set $$X\subseteq V(G)$$ such that the weight of X plus the weight of a heaviest component of $$G-X$$ is at most p. Among other results, we prove that: Result (1) refutes a conjecture by Ray and Deogun (J Comb Math Comb Comput 16:65-73, 1994) and answers an open question by Ray et al. (Ars Comb 79:77-95, 2006). It also complements a result by Kratsch et al. (Discret Appl Math 77(3):259-270, 1997), stating that the unweighted version of the problem can be solved in polynomial time on co-comparability graphs of bounded dimension, provided that an intersection model of the input graph is given as part of the input. An instance of the Weighted Component Order Connectivity (wCOC) problem consists of an n-vertex graph G, a weight function $$w:V(G)\rightarrow {\mathbb {N}}$$ , and two integers k and $$\ell $$ , and the task is to decide if there exists a set $$X\subseteq V(G)$$ such that the weight of X is at most k and the weight of a heaviest component of $$G-X$$ is at most $$\ell $$ . In some sense, the wCOC problem can be seen as a refined version of the wVI problem. We obtain several classical and parameterized complexity results on the wCOC problem, uncovering interesting similarities and differences between wCOC and wVI. We prove, among other results, that: We also show that result (6) is essentially tight by proving that wCOC cannot be solved in $$2^{o(k \log \ell )}n^{O(1)}$$ time, even when restricted to split graphs, unless the Exponential Time Hypothesis fails. [ABSTRACT FROM AUTHOR]

We consider systems of small, cheap, simple sensors that are organized in a distributed network and used for estimating and tracking the locations of targets. The objective is to assign sensors to targets such that the overall expected error of the sensors' estimates of the target locations is minimized. The so-called focus of attention problem (FOA) deals with the special case where every target is tracked by one pair of range sensors. The resulting computational problem is a special case of the axial three-index assignment problem, a well-known fundamental problem in combinatorial optimization. We provide a complete complexity and approximability analysis of the FOA problem: we establish strong NP-hardness and the unlikeliness of an FPTAS, we identify polynomially solvable special cases, and we construct a sophisticated polynomial time approximation scheme for it. [ABSTRACT FROM AUTHOR]

The scaffold filling problem aims to set up the whole genomes by filling those missing genes into the scaffolds to optimize a similarity measure of genomes. A typical and frequently used measure for the similarity of two genomes is the number of common adjacencies. One-sided scaffold filling is given by a scaffold and a whole genome, and asks to fill the missing genes into that scaffold to result in such a genome that the number of common adjacencies between it and the given genome is maximized. Two-sided scaffold filling is given by two scaffolds, and asks to fill the missing genes into those two scaffolds respectively to result in such two genomes that the number of common adjacencies between them is maximized. One-sided scaffold filling can be approximated to $$\frac{5}{4}$$ by now. However, the algorithmic progress for two-sided scaffold filling seems rare. What we know for two-sided scaffold filling is a 2-approximation algorithm by now. In this paper, we propose a new algorithm for two-sided scaffold filling which can achieve a performance ratio of $$\frac{3}{2}$$ in $$O(N^3)$$ time, where $$N$$ is the number of genes in an output genome. An example can be given to show that the performance ratio $$\frac{3}{2}$$ for this algorithm is actually tight. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of augmenting a planar graph such that it becomes $$k$$ -regular, $$c$$ -connected and remains planar, either in the sense that the augmented graph is planar, or in the sense that the input graph has a fixed (topological) planar embedding that can be extended to a planar embedding of the augmented graph. We fully classify the complexity of this problem for all values of $$k$$ and $$c$$ in both, the variable embedding and the fixed embedding case. For $$k \le 2$$ all problems are simple and for $$k \ge 4$$ all problems are NP-complete. Our main results are efficient algorithms (with running time $$O(n^{1.5}))$$ for deciding the existence of a $$c$$ -connected, 3-regular augmentation of a graph with a fixed planar embedding for $$c=0,1,2$$ and a corresponding hardness result for $$c=3$$ . The algorithms are such that for yes-instances a corresponding augmentation can be constructed in the same running time. [ABSTRACT FROM AUTHOR]

Given a matrix A∈ℝ ( n vectors in m dimensions), and a positive integer k< n, we consider the problem of selecting k column vectors from A such that the volume of the parallelepiped they define is maximum over all possible choices. We prove that there exists δ<1 and c>0 such that this problem is not approximable within 2 for k= δn, unless P= NP. [ABSTRACT FROM AUTHOR]

The longest path problem is the problem of finding a path of maximum length in a graph. As a generalization of the Hamiltonian path problem, it is NP-complete on general graphs and, in fact, on every class of graphs that the Hamiltonian path problem is NP-complete. Polynomial solutions for the longest path problem have recently been proposed for weighted trees, Ptolemaic graphs, bipartite permutation graphs, interval graphs, and some small classes of graphs. Although the Hamiltonian path problem on cocomparability graphs was proved to be polynomial almost two decades ago, the complexity status of the longest path problem on cocomparability graphs has remained open; actually, the complexity status of the problem has remained open even on the smaller class of permutation graphs. In this paper, we present a polynomial-time algorithm for solving the longest path problem on the class of cocomparability graphs. Our result resolves the open question for the complexity of the problem on such graphs, and since cocomparability graphs form a superclass of both interval and permutation graphs, extends the polynomial solution of the longest path problem on interval graphs and provides polynomial solution to the class of permutation graphs. [ABSTRACT FROM AUTHOR]

We initiate the study of the algorithmic foundations of games in which a set of cops has to guard a region in a graph (or digraph) against a robber. The robber and the cops are placed on vertices of the graph; they take turns in moving to adjacent vertices (or staying). The goal of the robber is to enter the guarded region at a vertex with no cop on it. The problem is to find the minimum number of cops needed to prevent the robber from entering the guarded region. The problem is highly non-trivial even if the robber's or the cops' regions are restricted to very simple graphs. The computational complexity of the problem depends heavily on the chosen restriction. In particular, if the robber's region is only a path, then the problem can be solved in polynomial time. When the robber moves in a tree (or even in a star), then the decision version of the problem is NP-complete. Furthermore, if the robber is moving in a directed acyclic graph, the problem becomes PSPACE-complete. [ABSTRACT FROM AUTHOR]

The longest path problem is the problem of finding a path of maximum length in a graph. Polynomial solutions for this problem are known only for small classes of graphs, while it is NP-hard on general graphs, as it is a generalization of the Hamiltonian path problem. Motivated by the work of Uehara and Uno (Proc. of the 15th Annual International Symp. on Algorithms and Computation (ISAAC), LNCS, vol. 3341, pp. 871-883, ), where they left the longest path problem open for the class of interval graphs, in this paper we show that the problem can be solved in polynomial time on interval graphs. The proposed algorithm uses a dynamic programming approach and runs in O( n) time, where n is the number of vertices of the input graph. [ABSTRACT FROM AUTHOR]

We study a set of problems related to efficient battery energy utilization for monitoring applications in a wireless sensor network with the goal to increase the sensor network lifetime. We study several generalizations of a basic problem called Set k-Cover. The problem can be described as follows: we are given a set of sensors, and a set of targets to be monitored. Each target can be monitored by a subset of the sensors. To increase the lifetime of the sensor network, we would like to partition the sensors into k sets (or time-slots), and activate each set of sensors in a different time-slot, thus extending the battery life of the sensors by a factor of k. The goal is to find a partitioning that maximizes the total coverage of the targets for a given k. This problem is known to be NP-hard. We develop an improved approximation algorithm for this problem using a reduction to Max k-Cut. Moreover, we are able to demonstrate that this algorithm is efficient, and yields almost optimal solutions in practice. We also consider generalizations of this problem in several different directions. First, we allow each sensor to be active in α different sets (time-slots). This means that the battery life is extended by a factor of $\frac{k}{\alpha}$, and allows for a richer space of solutions. We also consider different coverage requirements, such as requiring that all targets, or at least a certain number of targets, be covered in each time slot. In the Set k-Cover formulation, there is no requirement that a target be monitored at all, or in any number of time slots. We develop a randomized rounding algorithm for this problem. We also consider extensions where each sensor can monitor only a bounded number of targets in any time-slot, and not all the targets adjacent to it. This kind of problem may arise when a sensor has a directional camera, or some other physical constraint might prevent it from monitoring all adjacent targets even when it is active. We develop the first approximation algorithms for this problem. [ABSTRACT FROM AUTHOR]

We study the problem of non-preemptively scheduling n independent sequential jobs on a system of m identical parallel machines in the presence of reservations, where m is constant. This setting is practically relevant because for various reasons, some machines may not be available during specified time intervals. The objective is to minimize the makespan Cmax, which is the maximum completion time. The general case of the problem is inapproximable unless $\mathsf {P}=\mathsf {NP}$ ; hence, we study a suitable strongly $\mathsf {NP}$ -hard restriction, namely the case where at least one machine is always available. For this setting we contribute approximation schemes, complemented by inapproximability results. The approach is based on algorithms for multiple subset sum problems; our technique yields a PTAS which is best possible in the sense that an FPTAS is ruled out unless $\mathsf {P}=\mathsf {NP}$ . The PTAS presented here is the first one for the problem under consideration; so far, not even for well-known special cases approximation schemes have been proposed. Furthermore we derive a low cost algorithm with a constant approximation ratio and discuss FPTASes for special cases as well as the complexity of the problem if m is part of the input. [ABSTRACT FROM AUTHOR]

Abstract. Let P and Q be two disjoint convex polygons in the plane with m and n vertices, respectively. Given a point x in P , the aperture angle of x with respect to Q is defined as the angle of the cone that: (1) contains Q , (2) has apex at x and (3) has its two rays emanating from x tangent to Q . We present algorithms with complexities O(n log m) , O(n + n log (m/n)) and O(n + m) for computing the maximum aperture angle with respect to Q when x is allowed to vary in P . To compute the minimum aperture angle we modify the latter algorithm obtaining an O(n + m) algorithm. Finally, we establish an Ω(n + n log (m/n)) time lower bound for the maximization problem and an Ω(m + n) bound for the minimization problem thereby proving the optimality of our algorithms. [ABSTRACT FROM AUTHOR]

Much research has been devoted to system-level diagnosis—SLD. Two issues have been addressed. The first of these is diagnosability, i.e., provide necessary and sufficient conditions for a system of n units to be diagnosable provided that the number of faulty units does not exceed τ . The second is the design of fault identification algorithms, assuming that the system being considered is diagnosable. This paper focuses on the second of these concerns, discussing several algorithms of which the most efficient runs in O(n 2.5 ) . By considering a logical framework, this paper investigates the process of fault identification and proposes a fault identification algorithm which runs in O( n 2 \sqrt τ / \sqrt log n ) , τ < n/2 . [ABSTRACT FROM AUTHOR]

Abstract. A subset A of the vertices of a graph G is an asteroidal set if for each vertex a ∈ A a connected component of G-N[a] exists containing A\backslash{a} . An asteroidal set of cardinality three is called asteriodal triple and graphs without an asteriodal triple are called AT-free . The maximum cardinality of an asteroidal set of G , denoted by \an(G) , is said to be the asteriodal number of G . We present a scheme for designing algorithms for triangulation problems on graphs. As a consequence, we obtain algorithms to compute graph parameters such as treewidth, minimum fill-in and vertex ranking number. The running time of these algorithms is a polynomial (of degree asteriodal number plus a small constant) in the number of vertices and the number of minimal separators of the input graph. [ABSTRACT FROM AUTHOR]

In this paper we analyze the complexity of the Temporal Precedence Problem on pointer machines. The problem is to support efficiently two operations: insert and precedes. The operation insert (a) introduces a new element a , while precedes (a,b) returns true iff element a was temporally inserted before element b . We provide a solution to the problem with worst-case time complexity O( lg lg n) per operation, where n is the number of elements inserted. We also demonstrate that the problem has a lower bound of Ω( lg lg n) on pointer machines. Thus the proposed scheme is optimal on pointer machines. [ABSTRACT FROM AUTHOR]

In many assembly tasks it is necessary to ensure the stability of a subcollection of contacting objects. To achieve stability, it is often necessary to introduce fixture elements (also called ``fingers'' in some work) to help hold objects in place. In this paper the complexity of stabilizing multiple contacting bodies with the fewest number of fixture elements possible is considered. Standard fixture elements of the type explored in previous single-object grasping work are considered, along with a generalized variant of fixture elements. Both form-closure (complete immobility of the assembly), and first-order stability (stability of an assembly in the neighborhood of a specific external force and torque on each body) are considered. The major result is that for three of the four combinations of fixture element varieties and stability considered, achieving an optimal solution (that is, finding a smallest set of fixture elements yielding stability) is NP-hard. However, for many fixturing problems it seems likely that suboptimal, yet acceptably small solutions can be found in polynomial time, and some candidate algorithms are presented. [ABSTRACT FROM AUTHOR]

The 'bidirectional edges problem' is to find an edge-labeling of an undirected network, G=(V, E), with a source and a sink, such that an edge [ u, v] ∈ E is labeled ( u, v) or ( v, u) (or both) depending on the existence of a (simple) path from the source to sink that visits the vertices u and v, in the order u, v or v, u, respectively. We provide several algorithms for this problem in the current paper and the sequel. In this paper we show the relation between this problem and the classical two-vertex-disjoint-paths problem and then devise a simple algorithm with a time complexity of O(| E|·| V|). In the sequel we improve the time complexity to O(| E|·| V|). The main technique exploits aclever partition of the graph into a set of paths and bridges which are then analyzed recursively. The bidirectional edges problem arises naturally in the context of the simulation of an MOS transistor network, in which a transistor may operate as a unilateral or a bilateral device, depending on the voltages at its source and drain nodes. For efficient simulation, it is required to detect the set of transistors that may operate as bilateral devices. Also, sometimes it is intended to propagate information in one direction only, and propagation in the wrong direction (resulting in a sneak path) can cause functional error. Our algorithms can be used to detect all the sneak paths. [ABSTRACT FROM AUTHOR]

Given a natural language cleartext and a ciphertext obtained by Huffman coding, the problem of guessing the code is shown to be NP-complete for various variants of the encoding process. [ABSTRACT FROM AUTHOR]

We study the maximum-flow algorithm of Goldberg and Tarjan and show that the largest-label implementation runs in O(n √m) time. We give a new proof of this fact. We compare our proof with the earlier work by Cheriyan and Maheswari who showed that the largest-label implementation of the preflow-push algorithm of Goldberg and Tarjan runs in O(n √m) time when implemented with current edges. Our proof that the number of nonsaturating pushes is O(n √m), does not rely on implementing pushes with current edges, therefore it is true for a much larger family of largest-label implementation of the preflow-push algorithms. [ABSTRACT FROM AUTHOR]

We prove that a robot hand whose fingers make frictionless contact with a convex polyhedral object will be able to find a grasp where the hand can exert any desired force-torque on the object provided the hand has seven fingers. We present an algorithm for grasping any convex polyhedron and we prove rigorously that it works for any convex polyhedron. The algorithm requires O( n√log n) steps (in the worst case) where n is the number of vertices. [ABSTRACT FROM AUTHOR]

An integrative overview of the algorithmic characteristics of three well-known polynomialtime heuristics for the undirected Steiner minimum tree problem: shortest path heuristic (SPH), distance network heuristic (DNH), and average distance heuristic (ADH) is given. The performance of these single-pass heuristics (and some variants) is compared and contrasted with several heuristics based on repetitive applications of the SPH. It is shown that two of these repetitive SPH variants generate solutions that in general are better than solutions obtained by any single-pass heuristic. The worst-case time complexity of the two new variants is O( pn ) and O( p n ), while the worst-case time complexity of the SPH, DNH, and ADH is respectively O( pn ), O( m + n log n), and O( n ) where p is the number of vertices to be spanned, n is the total number of vertices, and m is the total number of edges. However, use of few simple tests is shown to provide large reductions of problem instances (both in terms of vertices and in term of edges). As a consequence, a substantial speed-up is obtained so that the repetitive variants are also competitive with respect to running times. [ABSTRACT FROM AUTHOR]

This paper determines upper bounds on the expected time complexity for a variety of parallel algorithms for undirected and directed random graph problems. For connectivity, biconnectivity, transitive closure, minimum spanning trees, and all pairs minimum cost paths, we prove the expected time to be O(log log n) for the CRCW PRAM (this parallel RAM machine allows resolution of write conflicts) and O(log n · log log n) for the CREW PRAM (which allows simultaneous reads but not simultaneous writes). We also show that the problem of graph isomorphism has expected parallel time O(log log n) for the CRCW PRAM and O(log n) for the CREW PRAM. Most of these results follow because of upper bounds on the mean depth of a graph, derived in this paper, for more general graphs than was known before. For undirected connectivity especially, we present a new probabilistic algorithm which runs on a randomized input and has an expected running time of O(log log n) on the CRCW PRAM, with O( n) expected number of processors only. Our results also improve known upper bounds on the expected space required for sequential graph algorithms. For example, we show that the problems of finding connected components, transitive closure, minimum spanning trees, and minimum cost paths have expected sequential space O(log n · log log n) on a deterministic Turing Machine. We use a simulation of the CRCW PRAM to get these expected sequential space bounds. [ABSTRACT FROM AUTHOR]

This paper presents a parallel algorithm for sorting on any graph with a Hamiltonian path and 1-factorization. For an n-cube the algorithm is equivalent to the sequential balanced sorting network of Dowd, Perl, Rudolph, and Saks. The application of this algorithm to other networks is discussed. [ABSTRACT FROM AUTHOR]

Let W ( n) be the minimax complexity of selecting the k largest elements of n numbers x , x ,..., x by pairwise comparisons x : x . It is well known that W ( n) = n−2+ [lg n], and W ( n) = n + ( k−1)lg n + O(1) for all fixed k ≥ 3. In this paper we study W′( n), the minimax complexity of selecting the k largest, when tests of the form 'Is x the median of { x , x , x }?' are also allowed. It is proved that W′( n) = n−2+ [lg n], and W′( n) = n + ( k−1)lg n + O(1) for all fixed k≥3. [ABSTRACT FROM AUTHOR]

We consider the parallel time complexity of logic programs without function symbols, called logical query programs, or Datalog programs. We give a PRAM algorithm for computing the minimum model of a logical query program, and show that for programs with the 'polynomial fringe property,' this algorithm runs in time that is logarithmic in the input size, assuming that concurrent writes are allowed if they are consistent. As a result, the 'linear' and 'piecewise linear' classes of logic programs are in N C. Then we examine several nonlinear classes in which the program has a single recursive rule that is an 'elementary chain.' We show that certain nonlinear programs are related to GSM mappings of a balanced parentheses language, and that this relationship implies the 'polynomial fringe property;' hence such programs are in N C Finally, we describe an approach for demonstrating that certain logical query programs are log space complete for P, and apply it to both elementary single rule programs and nonelementary programs. [ABSTRACT FROM AUTHOR]

We develop an O( n) algorithm to construct a rectangular dual of an n-vertex planar triangulated graph. [ABSTRACT FROM AUTHOR]

We examine a version of the dynamic dictionary problem in which stored items have expiration times and can be removed from the dictionary once they have expired. We show that under several reasonable assumptions about the distribution of the items, hashing with lazy deletion uses little more space than methods that use eager deletion. The simple algorithm suggested by this observation was used in a program for analyzing integrated circuit artwork. [ABSTRACT FROM AUTHOR]