A note on maximum independent set and related problems on box graphs

A box graph is the intersection graph of orthogonal rectangles in the plane. We show that maximum independent set and minimum vertex cover on box graphs can be solved in subexponential time, more precisely, in time , by applying Miller's simple cycle planar separator theorem [J. Comput. System Sci. 32 (1986) 265-279] (in spite of the fact that the input box graph might be strongly non-planar).     

Note on the Homogeneous Set Sandwich Problem

A homogeneous set is a non-trivial module of a graph, i.e., a non-unitary, proper subset H of a graph's vertices such that all vertices in H have the same neighbors outside H. Given two graphs G₁(V,E₁), G₂(V,E₂), the Homogeneous Set Sandwich Problem asks whether there exists a sandwich graph GS(V,ES), E₁⊆ES⊆E₂, which has a homogeneous set. Recently, Tang et al. [Inform. Process. Lett. 77 (2001) 17-22] proposed an interesting O(_?1⋅n²) algorithm for this problem, which has been considered its most efficient algorithm since. We show the incorrectness of their algorithm by presenting three counterexamples.     

Maximum weight k-independent set problem on permutation graphs

Based on a Directed Acyclic Graph approach, an O(kn ²) time sequential algorithm is presented to solve the maximum weight k-independent set problem on weighted-permutation graphs. The weights considered here are all non-negative and associated with each of the n vertices of the graph. This problem has many applications in practical problems like k-machines job scheduling problem, k-colourable subgraph problem, VLSI design and routing problem.     

A note on the search for k elements via quantum walk

In this paper we use the quantum walk search scheme by Magniez et al. (2007) [13] to find k solutions of a search problem. We show that the quantum query complexity is at most of order times the number of queries to find one solution.     

A note on the online First-Fit algorithm for coloring k-inductive graphs

In a FOCS 1990 paper, S. Irani proved that the First-Fit online algorithm for coloring a graph uses at most O(klogn) colors for k-inductive graphs. In this note we provide a very short proof of this fact.     

A note on compressed sensing and the complexity of matrix multiplication

We consider the conjectured O(N2+?) time complexity of multiplying any two N×N matrices A and B. Our main result is a deterministic Compressed Sensing (CS) algorithm that both rapidly and accurately computes A⋅B provided that the resulting matrix product is sparse/compressible. As a consequence of our main result we increase the class of matrices A, for any given N×N matrix B, which allows the exact computation of A⋅B to be carried out using the conjectured O(N2+?) operations. Additionally, in the process of developing our matrix multiplication procedure, we present a modified version of Indyk's recently proposed extractor-based CS algorithm [P. Indyk, Explicit constructions for compressed sensing of sparse signals, in: SODA, 2008] which is resilient to noise.     

A note on computing set overlap classes

Let V be a finite set of n elements and F={X₁,X₂,…,Xm} a family of m subsets of V. Two sets Xi and Xj of F overlap if Xi∩Xj≠∅, Xj?Xi≠∅, and Xi?Xj≠∅. Two sets X,Y∈F are in the same overlap class if there is a series X=X₁,X₂,…,Xk=Y of sets of F in which each XiXi+1 overlaps. In this note, we focus on efficiently identifying all overlap classes in time. We thus revisit the clever algorithm of Dahlhaus [E. Dahlhaus, Parallel algorithms for hierarchical clustering and applications to split decomposition and parity graph recognition, J. Algorithms 36 (2) (2000) 205-240] of which we give a clear presentation and that we simplify to make it practical and implementable in its real worst case complexity. An useful variant of Dahlhaus's approach is also explained.     

A note on the query complexity of the Condorcet winner problem

Given an unknown tournament over {1,…,n}, we show that the query complexity of the question “Is there a vertex with outdegree n−1?” (known as a Condorcet winner in social choice theory) is exactly 2n−⌊log(n)⌋−2. This stands in stark contrast to the evasiveness of this property in general digraphs.     

Erratum and addendum to “A linear time algorithm for finding all hinge vertices of a permutation graph” [Information Processing Letters 59 (2) (1996) 103-107]

This note points out and corrects an error in the algorithm proposed in [Ting-Yem Ho, Yue-Li Wang and Ming-Tsan Juan, A linear time algorithm for finding all hinge vertices of a permutation graph, Information Processing Letters 59 (2) (1996) 103-107].     

Parallel and serial heuristics for the minimum set cover problem

We present a theoretical analysis and an experimental evaluation of four serial heuristics and four parallel heuristics for the minimum set cover problem. The serial heuristics trade off run time with the quality of the solution. The parallel heuristics are derived from one of the serial heuristics. These heuristics show considerable speedup when the number of processors is increased. The quality of the solution computed by the heuristics does not degrade with an increase in the number of processors.Research of both authors was supported by NSF Grant No. MIP-8807540.     

A faster parameterized algorithm for set packing

We present an efficient parameterized algorithm for the (k,t)-set packing problem, in which we are looking for a collection of k disjoint sets whose union consists of t elements. The complexity of the algorithm is O(²O(t)nNlogN). For the special case of sets of bounded size, this improves the O(k(ck)n) algorithm of Jia et al. [J. Algorithms 50 (1) (2004) 106].     

A note concerning the closest point pair algorithm

An algorithm, described by Sedgewick, finds the distance between the closest pair of n given points in a plane using a variant of mergesort. This takes O(nlogn) time. To prove this it is necessary to show that, in the merge phase of the algorithm, no more than a constant number of distances need to be checked for each point considered. Cormen, Leiserson and Rivest show that checking seven distances is sufficient while Sedgewick suggests that this should be four. This paper shows that checking three distances is sufficient and that a slight modification of the algorithm reduces the number to two.     

A note on maximizing the spread of influence in social networks

We consider the spread maximization problem that was defined by Domingos and Richardson (2001, 2002) [7] and [22]. In this problem, we are given a social network represented as a graph and are required to find the set of the most “influential” individuals that by introducing them with a new technology, we maximize the expected number of individuals in the network, later in time, that adopt the new technology. This problem has applications in viral marketing, where a company may wish to spread the rumor of a new product via the most influential individuals in popular social networks such as Myspace and Blogsphere.The spread maximization problem was recently studied in several models of social networks (Kempe et al. (2003, 2005) [14] and [15], Mossel and Roch (2007) [20]). In this short paper we study this problem in the context of the well studied probabilistic voter model. We provide very simple and efficient algorithms for solving this problem. An interesting special case of our result is that the most natural heuristic solution, which picks the nodes in the network with the highest degree, is indeed the optimal solution.     

Solving a system of difference constraints with variables restricted to a finite set

An algorithm is given for the solution of a system of difference constraints where the variables must take on values from a given finite set of real numbers.     

A k-server problem with parallel requests and unit distances

In this paper we consider k-server problems with parallel requests where several servers can also be located on one point. We will distinguish the surplus-situation where the request can be completely fulfilled by means of the k servers and the scarcity-situation where the request cannot be completely met. We use the method of the potential function by Bartal and Grove [2] in order to prove that a corresponding Harmonic algorithm is competitive for the more general k-server problem in the case of unit distances. For this purpose we partition the set of points in relation to the online and offline servers? positions and then use detailed considerations related to sets of certain partitions.     

Efficient parallel algorithms for computing all pair shortest paths in directed graphs

We present parallel algorithms for computing all pair shortest paths in directed graphs. Our algorithm has time complexityO(f(n)/p+I(n)logn) on the PRAM usingp processors, whereI(n) is logn on the EREW PRAM, log logn on the CCRW PRAM,f(n) iso(n ³). On the randomized CRCW PRAM we are able to achieve time complexityO(n ³/p+logn) usingp processors. A preliminary version of this paper was presented at the 4th Annual ACM Symposium on Parallel Algorithms and Architectures, June 1992. Support by NSF Grant CCR 90-20690 and PSC CUNY Awards #661340 and #662478.