Search

In this paper, we focus on Hitting-Set , a fundamental problem in combinatorial optimization, through the lens of sublinear time algorithms. Given access to the hypergraph through a subset query oracle in the query model, we give sublinear time algorithms for Hitting-Set with almost tight parameterized query complexity. In parameterized query complexity , we estimate the number of queries to the oracle based on the parameter k , the size of the Hitting-Set. The subset query oracle we use in this paper is called Generalized d -partite Independent Set query oracle (GPIS) and it was introduced by Bishnu et al. (ISAAC'18). GPIS is a generalization to hypergraphs of the Bipartite Independent Set query oracle (BIS) introduced by Beame et al. (ITCS'18 and TALG'20) for estimating the number of edges in graphs. Since its introduction GPIS query oracle has been used for estimating the number of hyperedges independently by Dell et al. (SODA'20 and SICOMP'22) and Bhattacharya et al. (STACS'22), and for estimating the number of triangles in a graph by Bhattacharya et al. (ISAAC'19 and TOCS'21). Formally, GPIS is defined as follows: GPIS oracle for a d-uniform hypergraph H takes as input d pairwise disjoint non-empty subsets A 1 , ... , A d of vertices in H and answers whether there is a hyperedge in H that intersects each set A i , where i ∈ { 1 , 2 , ... , d }. For d = 2 , the GPIS oracle is nothing but BIS oracle. We show that d - Hitting-Set , the hitting set problem for d -uniform hypergraphs, can be solved using O ˜ d (k d log ⁡ n) GPIS queries. Additionally, we also showed that d - Decision-Hitting-Set , the decision version of d - Hitting-Set can be solved with O ˜ d (min ⁡ { k d log ⁡ n , k 2 d 2 }) GPIS queries. We complement these parameterized upper bounds with an almost matching parameterized lower bound that states that any algorithm that solves d - Decision-Hitting-Set requires Ω (( k + d d )) GPIS queries. [ABSTRACT FROM AUTHOR]

Unambiguous automata are nondeterministic automata in which every word has at most one accepting run. In this paper we give a polynomial-time algorithm for model checking discrete-time Markov chains against ω -regular specifications represented as unambiguous automata. We furthermore show that the complexity of this model checking problem lies in NC: the subclass of P comprising those problems solvable in poly-logarithmic parallel time. These complexity bounds match the known bounds for model checking Markov chains against specifications given as deterministic automata, notwithstanding the fact that unambiguous automata can be exponentially more succinct than deterministic automata. We report on an implementation of our procedure, including an experiment in which the implementation is used to model check LTL formulas on Markov chains. [ABSTRACT FROM AUTHOR]

The problem of deletion of vertices to a hereditary graph class is a well-studied problem in parameterized complexity. Recently, a natural extension of the problem was initiated where we are given a finite set of hereditary graph classes and we determine whether k vertices can be deleted from a given graph so that the connected components of the resulting graph belong to one of the given hereditary graph classes. The problem is shown to be fixed parameter tractable (FPT) when the deletion problem to each of the given hereditary graph classes is fixed-parameter tractable, and the property of being in any of the graph classes is expressible in the counting monodic second order (CMSO) logic. This paper focuses on pairs of specific graph classes (Π 1 , Π 2) in which we would like the connected components of the resulting graph to belong to, and design simpler and more efficient FPT algorithms. [ABSTRACT FROM AUTHOR]

Over the past few decades, a large body of works studied the (in)tractability of various computational problems on grid graphs, which often yield substantially faster algorithms than general graphs. Unfortunately, the recognition of a grid graph is hard—it was shown to be NP-hard already in 1987. In this paper, we provide several positive results in this regard in the framework of parameterized complexity. Specifically, our contribution is threefold. First, we show that the problem is FPT parameterized by k + mcc where mcc is the maximum size of a connected component of G. Second, we present a new parameterization, denoted a G , relating graph distance to geometric distance. We show that the problem is para-NP-hard parameterized by a G , but FPT parameterized by a G on trees, as well as FPT parameterized by k + a G. Third, we show that the recognition of k × r grid graphs is NP-hard on graphs of pathwidth 2 where k = 3. [ABSTRACT FROM AUTHOR]

We consider the circular pattern matching with k mismatches (k -CPM) problem in which one is to compute the minimal Hamming distance of every length- m substring of T and any cyclic rotation of P , if this distance is no more than k. It is a variation of the well-studied k -mismatch problem. A multitude of papers has been devoted to solving the k -CPM problem, but only average-case upper bounds are known. In this paper, we present the first non-trivial worst-case upper bounds for this problem. Specifically, we show an O (n k) -time algorithm and an O (n + n m k 4) -time algorithm. The latter algorithm applies in an extended way a technique that was very recently developed for the k -mismatch problem Bringmann et al. (2019) [10]. A preliminary version of this work appeared at FCT 2019 [35]. In this version we improve the time complexity of the second algorithm from O (n + n m k 5) to O (n + n m k 4). [ABSTRACT FROM AUTHOR]

The median of a set of vertices P of a graph G is the set of all vertices x of G minimizing the sum of distances from x to all vertices of P. In this paper, we present a linear time algorithm to compute medians in median graphs. We also present a linear time algorithm to compute medians in the associated ℓ 1 -cube complexes. Our algorithm is based on the majority rule characterization of medians in median graphs and on a fast computation of parallelism classes of edges (Θ-classes) via Lexicographic Breadth First Search (LexBFS). We show that any LexBFS ordering of the vertices of a median graph satisfies the following fellow traveler property : the parents of any two adjacent vertices are also adjacent. Using the fast computation of the Θ-classes, we also compute the Wiener index (total distance) in linear time and the distance matrix in optimal quadratic time. [ABSTRACT FROM AUTHOR]

Satisfiability of word equations problem is: Given two sequences consisting of letters and variables decide whether there is a substitution for the variables that turns this equation into true equality. The exact computational complexity of this problem remains unknown, with the best lower and upper bounds being, respectively, NP and PSPACE. Recently, the novel technique of recompression was applied to this problem, simplifying the known proofs and lowering the space complexity to (non-deterministic) O (n log ⁡ n). In this paper we show that satisfiability of word equations is in non-deterministic linear space, thus the language of satisfiable word equations is context-sensitive. We use the known recompression-based algorithm and additionally employ Huffman coding for letters. The proof, however, uses analysis of how the fragments of the equation depend on each other as well as a new strategy for non-deterministic choices of the algorithm. [ABSTRACT FROM AUTHOR]

Read-only memory (ROM) model is a classical model of computation to study time-space tradeoffs of algorithms. More recently, several graph algorithms have been studied under ROM model. In this paper, we study graph algorithms under two different relaxations of ROM model, referred to as the implicit and rotate models, and show that these simple relaxations allow us to implement fundamental graph search methods like BFS and DFS more space efficiently than in ROM model. All our algorithms are simple but quite subtle, and we believe that these models are practical enough to spur interest for other graph problems in these models. [ABSTRACT FROM AUTHOR]

In the Graph bipartization (or Odd Cycle Transversal) problem, the objective is to decide whether a given graph G can be made bipartite by the deletion of k vertices for some given k. The parameterized complexity of Odd Cycle Transversal was resolved in the breakthrough paper of Reed, Smith and Vetta [Operations Research Letters, 2004], who developed an algorithm running in time O (3 k k m n). The question of improving the dependence on the input size to linear, which was another long standing open problem in the area, was resolved by Iwata et al. [SICOMP 2016] and Ramanujan and Saurabh [TALG 2017], who presented O (4 k (m + n)) and 4 k k O (1) (m + n) algorithms respectively. In this paper, we obtain a faster algorithm that runs in time 3 k k O (1) (m + n) and hence preserves the linear dependence on the input size while nearly matching the dependence on k incurred by the algorithm of Reed, Smith and Vetta. [ABSTRACT FROM AUTHOR]

In this paper, we study the Maximum Internal Spanning Tree Problem (MIST). Given an undirected simple graph G , the task for the Maximum Internal Spanning Tree problem is to find a spanning tree of G with maximum number of internal vertices. We present an approximation algorithm with performance ratio 4 3 , which improves upon the best known performance ratio 3 2. Our algorithm benefits from a new observation for bounding the number of internal vertices of a spanning tree. We can also give an example to show that the performance ratio 4 3 is actually tight for this algorithm. Finally, we show that MIST is Max-SNP-hard. [ABSTRACT FROM AUTHOR]

This paper studies the problem of finding a path center on a tree in which vertex weights are uncertain and the uncertainty is described by given intervals. It is required to find a minmax regret solution, which minimizes the worst-case loss in the objective function. An O (n log n)-time algorithm is presented, improving the previous upper bound of O (n 2). [ABSTRACT FROM AUTHOR]

In public key encryption with keyword search (PEKS), a secure channel is required in order to send trapdoors to the server, whereas in secure-channel free PEKS (SCF-PEKS), no such secure channel is required. In this paper, we propose a generic construction of SCF-PEKS with multiple keywords (SCF-MPEKS) from hidden vector encryption, tag-based encryption, and a one-time signature. Our generic construction provides adaptive security, where the test queries are allowed in the security model, and does not require random oracles. In addition to providing an instantiation of our generic construction, which is the first adaptive secure SCF-MPEKS scheme in the standard model, we implement the SCF-MPEKS scheme by using the PBC library. Moreover, we extend the Boneh-Waters range search technique, and show that the running time of our encryption algorithm is approximately twice as fast as that of the Boneh-Waters encryption algorithm. [ABSTRACT FROM AUTHOR]

Translocation has been long learned as a basic operation to rearrange the structure of a genome. Translocation sorting asks to find a shortest sequence of translocations that transforms one genome into another, which has attracted attention of many scientists in algorithm design. Signed translocation sorting can be solved in polynomial time. Unsigned translocation sorting turns out to be NP-Hard and Max-SNP-Hard. The best known approximation algorithm by now for unsigned translocation sorting can achieve a performance ratio 1.408. In this paper, we propose a new approximation algorithm for unsigned translocation sorting which can achieve a asymptotic performance ratio 1.375. [ABSTRACT FROM AUTHOR]

Similar to the satisfiability (SAT) problem, which can be seen to be the archetypical problem for NP, the quantified Boolean formula problem (QBF) is the archetypical problem for PSPACE. Recently, Atserias and Oliva (2014) showed that, unlike for SAT, many of the well-known decompositional parameters (such as treewidth and pathwidth) do not allow efficient algorithms for QBF. The main reason for this seems to be the lack of awareness of these parameters towards the dependencies between variables of a QBF formula. In this paper we extend the ordinary pathwidth to the QBF-setting by introducing prefix pathwidth, which takes into account the dependencies between variables in a QBF, and show that it leads to an efficient algorithm for QBF. We hope that our approach will help to initiate the study of novel tailor-made decompositional parameters for QBF and thereby help to lift the success of these decompositional parameters from SAT to QBF. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the problem of dominant point detection on digital curves which consists in finding points with local maximum curvature. Thanks to previous studies of the decomposition of curves into sequence of discrete structures [1–3] , namely maximal blurred segments of width ν [4] , an initial algorithm has been proposed in [5] to detect dominant points. However, an heuristic strategy is used to identify the dominant points. We now propose a modified algorithm without heuristics but a simple measure of angle. In addition, two applications are as well presented: (1) polygonal simplification to reduce the number of detected dominant points by associating a weight to each of them, and (2) classification using the polygon issued from the reduced dominant points. The experimental results demonstrate the efficiency and robustness of the proposed method. [ABSTRACT FROM AUTHOR]

Markov chains have been widely employed as a fundamental model in the studies of probabilistic and stochastic communicating and concurrent systems. It is well-understood that decomposition techniques play a key role in reachability analysis and model-checking of Markov chains. (Discrete-time) quantum Markov chains have been introduced as a model of quantum communicating systems [1] and also a semantic model of quantum programs [2] . The BSCC (Bottom Strongly Connected Component) and stationary coherence decompositions of quantum Markov chains were introduced in [3–5] . This paper presents a new decomposition technique, namely periodic decomposition, for quantum Markov chains. We further establish a limit theorem for them. As an application, an algorithm to find a maximum dimensional noiseless subsystem of a quantum communicating system is given using decomposition techniques of quantum Markov chains. [ABSTRACT FROM AUTHOR]

Taking as input a time-varying sequence of 2D binary digital images, we develop an algorithm for encoding, in the so-called spatiotemporal barcode, lifetime of connected components that are moving in the sequence over time. Given a connected component in a specific time in the sequence, we can track it backwards, by what we call a spatiotemporal path. The main contribution of this paper lies in a new algorithm that computes spatiotemporal paths valid for both foreground and background and developed in a general context, setting the ground for tracking higher dimensional topological features in nD. [ABSTRACT FROM AUTHOR]

This paper presents a method for fitting digital hyperspheres to a given set of n D points in an image in the presence of noise by maximizing the number of inliers, namely the consensus set. The digital Hyperspheres are defined using the k -Flake Digitization models [25] . We present an algorithm, that provides optimal fitting solutions for digital k -Flake hyperspheres within a time complexity O ( ( ( n k ) 2 n − k ) n N n + 1 log ⁡ N ) for dimension n , N being the number of points. We have implemented this algorithm for the particular case of 3D 2-Flake spheres that corresponds to the classical so called Naive digital spheres. [ABSTRACT FROM AUTHOR]

This paper presents a study on the set of the digitizations generated by all the translations of a planar body on a square grid. First the translation vector set is reduced to a bounded subset, then the dual introduced in [1] linking the translation vector to the corresponding digitization is proved to be piecewise constant. Finally, a new algorithm is proposed to compute the digitization set using the dual. [ABSTRACT FROM AUTHOR]

Reading more and more bits from an infinite binary sequence that is random for a Bernoulli measure with parameter p , we can get better and better approximations of p using the strong law of large numbers. In this paper, we study a similar situation from the viewpoint of inductive inference. Assume that p is a computable real, and we have to eventually guess the program that computes p . We show that this cannot be done computably, and extend this result to more general computable distributions. We also provide a weak positive result showing that looking at a sequence X generated according to some computable probability measure, we can guess a sequence of algorithms that, starting from some point, compute a measure that makes X Martin-Löf random. [ABSTRACT FROM AUTHOR]

Many problems on graphs can be expressed in the following language: given a graph G = ( V , E ) and a terminal set T ⊆ V , find a minimum size set S ⊆ V which intersects all “structures” (such as cycles or paths) passing through the vertices in T . We refer to this class of problems as terminal set problems. In this paper, we introduce a general method to obtain faster exact exponential time algorithms for several terminal set problems. In the process, we break the O ⁎ ( 2 n ) barrier for the classic Node Multiway Cut , Directed Unrestricted Node Multiway Cut and Directed Subset Feedback Vertex Set problems. [ABSTRACT FROM AUTHOR]

We study a decision problem, that emerges from the area of spatial reasoning. This decision problem concerns the description of polylines in the plane by means of their double-cross matrix . In such a matrix, the relative position of each pair of line segments in a polyline is expressed by means of a 4-tuple over { − , 0 , + } . However, not any such matrix of 4-tuples is the double-cross matrix of a polyline. This gives rise to the decision problem: given a matrix of such 4-tuples, decide whether it is the double-cross matrix of a polyline. This problem is decidable, but it is NP -hard. In this paper, we give polynomial-time algorithms for the cases where consecutive line segments in a polyline make angles that are multiples of 90° or 45° and for the case where, apart from an input matrix, the successive angles of a polyline are also given as input. [ABSTRACT FROM AUTHOR]

In this paper we introduce a general framework that exponentially improves the space, degree of independence, and time needed by min-wise-based algorithms. The authors, in SODA '11 [1] , introduced an exponential time improvement for min-wise-based algorithms. Here we develop an alternative approach that achieves both exponential time and exponential space improvement. The new approach relaxes the need for approximately min-wise hash functions, hence getting around the Ω ( log ⁡ 1 ϵ ) independence lower bound, by defining and constructing a d-k-min-wise independent family of hash functions; surprisingly, for most cases, only 8-wise independence is needed for the additional improvement. Furthermore, we discuss how this construction can be used to improve many min-wise-based algorithms. To our knowledge such definitions, for hash functions, were never previously studied or constructed. Finally, we show how to apply it for similarity and rarity estimation over data streams; other min-wise-based algorithms can be adjusted in the same way. [ABSTRACT FROM AUTHOR]

This paper presents improved algorithms for the round-trip single-facility location problem on a general graph, in which a set A of collection depots is given and the service distance of a customer is defined to be the distance from the server, to the customer, then to a depot, and back to the server. Each customer i is associated with a subset A i ⊆ A of depots that i can potentially select from and use. When A i = A for each customer i , the problem is unrestricted; otherwise it is restricted. For the restricted round-trip 1-center problem, we give an O ( m n lg ⁡ n ) -time algorithm. For the restricted 1-median problem, we give an O ( m n lg ⁡ ( | A | / m ) + n 2 lg ⁡ n ) -time algorithm. For the unrestricted 1-median problem, we give an O ( m n + n 2 lg ⁡ lg ⁡ n ) -time algorithm. [ABSTRACT FROM AUTHOR]

Abstract: Learning regular languages from queries was introduced by Angluin in a seminal paper that also provides the algorithm. This algorithm, as well as other existing inference methods, finds the exact language accepted by the automaton. However, when only finite languages are used, the construction of a deterministic finite cover automaton (DFCA) is sufficient. A DFCA of a finite language U is a finite automaton that accepts all sequences in U and possibly other sequences that are longer than any sequence in U. This paper presents an algorithm, called , that finds a minimal DFCA of an unknown finite language in polynomial time using membership and language queries, a non-trivial adaptation of Angluinʼs algorithm. As the size of a minimal DFCA of a finite language U may be much smaller than the size of the minimal automaton that accepts exactly U, can provide substantial savings over existing automata inference methods. [Copyright &y& Elsevier]

Abstract: One major area of difficulty in developing an algorithm for embedding a graph on a surface is handling bridges which have more than one possible placement. This paper addresses a number of published algorithms where this has not been handled correctly. This problem arises in certain presentations of the Demoucron, Malgrange and Pertuiset planarity testing algorithm. It also occurs in an algorithm of Filotti for embedding 3-regular graphs on the torus. The same error appears in an algorithm for embedding graphs of arbitrary genus by Filotti, Miller and Reif. It is also present in an algorithm for embedding graphs of arbitrary genus by Djidjev and Reif. The omission regarding the Demoucron, Malgrange and Pertuiset planarity testing algorithm is easily remedied. However there appears to be no way of correcting the algorithms of the other papers without making the algorithms take exponential time. [ABSTRACT FROM AUTHOR]

Abstract: This paper is composed of two parts. In the first part, an improved algorithm is presented for the problem of finding length-bounded two vertex-disjoint paths in an undirected planar graph. The presented algorithm requires time and space, where is the smaller of the two given length bounds. In the second part of this paper, we consider the minmax k vertex-disjoint paths problem on a directed acyclic graph, where is a constant. An improved algorithm and a faster approximation scheme are presented. The presented algorithm requires time and space, and the presented approximation scheme requires time and space, where ϵ is the given approximation parameter and M is the length of the longest path in an optimal solution. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we investigate algorithms for some related graph parameters. Each of these asks for a linear ordering of the vertices of the graph (or can be formulated as such), and constructive linear time algorithms for the fixed parameter versions of the problems have been published for several of these. Examples are cutwidth, pathwidth, and directed or weighted variants of these. However, these algorithms have complicated technical details. This paper attempts to present ideas in these algorithms in a different more easily accessible manner, by showing that the algorithms can be obtained by a stepwise modification of a trivial hypothetical non-deterministic algorithm. The methodology is applied to rederive known results for the cutwidth and the pathwidth problem, and obtain new results for several variants of these problems, like directed and weighted variants of cutwidth and modified cutwidth. [Copyright &y& Elsevier]

Abstract: This paper investigates a graph enumeration problem, called the maximal -subgraphs problem, where is a hereditary or connected-hereditary graph property. Formally, given a graph G, the maximal -subgraphs problem is to generate all maximal induced subgraphs of G that satisfy . This problem differs from the well-known node-deletion problem, studied by Yannakakis and Lewis [J. Lewis, On the complexity of the maximum subgraph problem, in: Proc. 10th Annual ACM Symposium on Theory of Computing, ACM Press, New York, USA, 1978, pp. 265–274; M. Yannakakis, Node- and edge-deletion NP-complete problems, in: Proc. 10th Annual ACM Symposium on Theory of Computing, ACM Press, New York, USA, 1978, pp. 253–264; J. Lewis, M. Yannakakis, The node-deletion problem for hereditary properties is NP-complete, J. Comput. System Sci. 20 (2) (1980) 219–230]. In the maximal -subgraphs problem, the goal is to produce all (locally) maximal subgraphs of a graph that have property , whereas in the node-deletion problem, the goal is to find a single (globally) maximum size subgraph with property . Algorithms are presented that reduce the maximal -subgraphs problem to an input-restricted version of this problem. These algorithms imply that when attempting to efficiently solve the maximal -subgraphs problem for a specific , it is sufficient to solve the restricted case. The main contributions of this paper are characterizations of when the maximal -subgraphs problem is in a complexity class C (e.g., polynomial delay, total polynomial time). [Copyright &y& Elsevier]

Abstract: We consider the problem of periodic exploration of all nodes in undirected graphs by using a finite state automaton called later a robot. The robot, using a constant number of states (memory bits), must be able to explore any unknown anonymous graph. The nodes in the graph are neither labelled nor coloured. However, while visiting a node v the robot can distinguish between edges incident to it. The edges are ordered and labelled by consecutive integers called port numbers, where is the degree of v. Periodic graph exploration requires that the automaton has to visit every node infinitely many times in a periodic manner. In this paper, we are interested in minimisation of the length of the exploration period. In other words, we want to minimise the maximum number of edge traversals performed by the robot between two consecutive visits of a generic node, in the same state and entering the node by the same port. Note that the problem is unsolvable if the local port numbers are set arbitrarily, see [L. Budach, Automata and labyrinths, Math. Nachr. 86 (1978) 195–282]. In this context, we are looking for the minimum function , such that, there exists an efficient deterministic algorithm for setting the local port numbers allowing the robot to explore all graphs of size n along a traversal route with the period . Dobrev et al. proved in [S. Dobrev, J. Jansson, K. Sadakane, W.-K. Sung, Finding short right-hand-on-the-wall walks in graphs, in: Proc. 12th Colloquium on Structural Information and Communication Complexity, SIROCCO 2005, in: Lecture Notes in Comput. Sci., vol. 3499, Springer, Berlin, 2005, pp. 127–139] that for oblivious robots . Recently Ilcinkas proposed another port labelling algorithm for robots equipped with two extra memory bits, see [D. Ilcinkas, Setting port numbers for fast graph exploration, in: Proc. 13th Colloquium on Structural Information and Communication Complexity, SIROCCO 2006, in: Lecture Notes in Comput. Sci., vol. 4056, Springer, Berlin, 2006, pp. 59–69], where the exploration period . In the same paper, it is conjectured that the bound is tight even if the use of larger memory is allowed. In this paper, we disprove this conjecture presenting an efficient deterministic algorithm arranging the port numbers, such that, the robot equipped with a constant number of bits is able to complete the traversal period in steps hence decreasing the existing upper bound. This reduces the gap with the lower bound of holding for any robot. [Copyright &y& Elsevier]

Abstract: This paper studies the problem of constructing a minimum-weight spanning tree (MST) in a distributed network. This is one of the most important problems in the area of distributed computing. There is a long line of gradually improving protocols for this problem, and the state of the art today is a protocol with running time due to Kutten and Peleg [S. Kutten, D. Peleg, Fast distributed construction of k-dominating sets and applications, J. Algorithms 28 (1998) 40–66; preliminary version appeared in: Proc. of 14th ACM Symp. on Principles of Distributed Computing, Ottawa, Canada, August 1995, pp. 20–27], where denotes the diameter of the graph G. Peleg and Rubinovich [D. Peleg, V. Rubinovich, A near-tight lower bound on the time complexity of distributed MST construction, in: Proc. 40th IEEE Symp. on Foundations of Computer Science, 1999, pp. 253–261] have shown that time is required for constructing MST even on graphs of small diameter, and claimed that their result “establishes the asymptotic near-optimality” of the protocol of [S. Kutten, D. Peleg, Fast distributed construction of k-dominating sets and applications, J. Algorithms 28 (1998) 40–66; preliminary version appeared in: Proc. of 14th ACM Symp. on Principles of Distributed Computing, Ottawa, Canada, August 1995, pp. 20–27]. In this paper we refine this claim, and devise a protocol that constructs the MST in rounds, where is the MST-radius of the graph. The ratio between the diameter and the MST-radius may be as large as , and, consequently, on some inputs our protocol is faster than the protocol of [S. Kutten, D. Peleg, Fast distributed construction of k-dominating sets and applications, J. Algorithms 28 (1998) 40–66; preliminary version appeared in: Proc. of 14th ACM Symp. on Principles of Distributed Computing, Ottawa, Canada, August 1995, pp. 20–27] by a factor of . Also, on every input, the running time of our protocol is never greater than twice the running time of the protocol of [S. Kutten, D. Peleg, Fast distributed construction of k-dominating sets and applications, J. Algorithms 28 (1998) 40–66; preliminary version appeared in: Proc. of 14th ACM Symp. on Principles of Distributed Computing, Ottawa, Canada, August 1995, pp. 20–27]. As part of our protocol for constructing an MST, we develop a protocol for constructing neighborhood covers with a drastically improved running time. The latter result may be of independent interest. [Copyright &y& Elsevier]

Abstract: Shortest path finding has a variety of applications in the areas of transportation and communication in distributed systems. In this paper, we design and prove the correctness of a self-stabilizing algorithm that solves the single-source shortest path problem for a distributed system. Unlike all previous works on this topic, the model of computation employed by the system in this paper assumes the separate read/write atomicity introduced by Dolev et al. instead of the commonly used composite read/write atomicity introduced by Dijkstra. [Copyright &y& Elsevier]

Abstract: We prove two lower bounds in the statistical query (SQ) learning model. The first lower bound is on weak-learning. We prove that for a concept class of SQ-dimension d, a running time of is needed. The SQ-dimension of a concept class is defined to be the maximum number of concepts that are “uniformly correlated”, in that each of their pair has nearly the same correlation. This lower bound matches the upper bound in Blum et al. (Weakly Learning DNF and Characterizing Statistical Query Learning using Fourier Analysis, STOC 1994, pp. 253–262), up to a logarithmic factor. We prove this lower bound against an “honest SQ-oracle”, which gives a stronger result than the ones against the more frequently used “adversarial SQ-oracles”. The second lower bound is more general. It gives a continuous trade-off between the “advantage” of an algorithm in learning the target function and the number of queries it needs to make, where the advantage of an algorithm is the probability it succeeds in predicting a label minus the probability it does not. Both lower bounds extend and/or strengthen previous results, and solve an open problem left in previous papers. An earlier version of this paper [K. Yang, New lower bounds for statistical query learning, in: The Proceedings of the 15th Annual Conference on Computational Learning Theory, COLT 2002, Sydney, Australia, July 8–10, Lecture Notes in Computer Science, vol. 2375, 2002, pp. 229–243.] appeared in the proceedings of the 15th Annual Conference on Computational Learning Theory (COLT 2002). [Copyright &y& Elsevier]

In this paper, we solve a long-standing problem that has been of interest since about 1988. The problem in general is to decide whether or not it is possible to partition the vertices of a graph into k distinct non-empty sets A0,A1,…,Ak−1, such that the vertices in Ai are independent and there is at least one edge between the pair of sets Ai and A(i+1) mod k, for all i=0,1,2,…,k−1, k>2, and there is no edge between any other pair of sets. Determining the computational complexity of this problem, for any value of even k⩾6, has been of interest since about 1988 to various people, including Pavol Hell and Jaroslav Nesetril. We show in this paper that the problem is NP-complete, for all even k⩾6. We study the problem as the compaction problem for an irreflexive k-cycle. [Copyright &y& Elsevier]

This paper considers a modification of a PAC learning theory problem in which each instance of the training data is supplemented with side information. In this case, a transformation, given by a side-information map, of the training instance is also classified. However, the learning algorithm needs only to classify a new instance, not the instance and its value under the side information map. Side information can improve general learning rates, but not always. This paper shows that side information leads to the improvement of standard PAC learning theory rate bounds, under restrictions on the probable overlap between concepts and their images under the side information map. [Copyright &y& Elsevier]

A number of recent papers on approximation algorithms have used the square roots of unity, −1 and 1, to represent binary decision variables for problems in combinatorial optimization, and have relaxed these to unit vectors in real space using semidefinite programming in order to obtain near optimum solutions to these problems. In this paper, we consider using the cube roots of unity, 1, ei2π/3, and ei4π/3, to represent ternary decision variables for problems in combinatorial optimization. Here the natural relaxation is that of unit vectors in complex space. We use an extension of semidefinite programming to complex space to solve the natural relaxation, and use a natural extension of the random hyperplane technique introduced by the authors in Goemans and Williamson (J. ACM 42 (1995) 1115–1145) to obtain near-optimum solutions to the problems. In particular, we consider the problem of maximizing the total weight of satisfied equations xu−xv≡c (mod 3) and inequations xu−xv≢c (mod 3), where xu∈{0,1,2} for all u. This problem can be used to model the Max-3-Cut problem and a directed variant we call Max-3-Dicut. For the general problem, we obtain a 0.793733-approximation algorithm. If the instance contains only inequations (as it does for Max-3-Cut), we obtain a performance guarantee of 7/12+3/4π2arccos2(−1/4)−ϵ>0.836008. This compares with proven performance guarantees of 0.800217 for Max-3-Cut (by Frieze and Jerrum (Algorithmica 18 (1997) 67–81) and 1/3+3/4π2arccos2(−1/4)−ϵ>0.836008. This compares with proven performance guarantees of 0.800217 for Max-3-Cut (by Frieze and Jerrum (Algorithmica 18 (1997) 67–81) and 1/3 arccos2(−1/4)−ϵ>0.836008. This compares with proven performance guarantees of 0.800217 for Max-3-Cut (by Frieze and Jerrum (Algorithmica 18 (1997) 67–81) and 1/3+10−8 for the general problem (by Andersson et al. (J. Algorithms 39 (2001) 162–204)). It matches the guarantee of 0.836008 for Max-3-Cut found independently by de Klerk et al. (On approximate graph colouring and Max-k-Cut algorithms based on the ϑ-function, Manuscript, October 2000). We show that all these algorithms are in fact equivalent in the case of Max-3-Cut, and that our algorithm is the same as that of Andersson et al. in the more general case. [Copyright &y& Elsevier]

Motivated by the research in reconfigurable memory array structures, this paper studies the complexity and algorithms for the constrained minimum vertex cover problem on bipartite graphs (min-cvcb) defined as follows: given a bipartite graph G=(V,E) with vertex bipartition V=U∪L and two integers ku and kl, decide whether there is a minimum vertex cover in G with at most ku vertices in U and at most kl vertices in L. It is proved in this paper that the min-cvcb problem is NP-complete. This answers a question posed by Hasan and Liu. A parameterized algorithm is developed for the problem, in which classical results in matching theory and recently developed techniques in parameterized computation theory are nicely combined and extended. The algorithm runs in time O(1.26ku+kl+(ku+kl)|G|) and significantly improves previous algorithms for the problem. [Copyright &y& Elsevier]

This paper treats polynomial-time algorithms for reconstruction of phylogenetic trees. The disc-covering method (DCM) presented by Huson et al. (J. Comput. Biol. 6 (3/4) (1999) 369) is a method that boosts the performance of phylogenetic tree construction algorithms. Actually, they gave two variations of DCM-Buneman. The first variation was guaranteed to recover the true tree with high probability from polynomial-length sequences (i.e. polynomial in the number of given taxa), but it was not proven to run in polynomial time. The second variation was guaranteed to run in polynomial time. However, it is a heuristic in the sense that it was not proven to recover the true tree with high probability from polynomial-length sequences.We present an improved DCM. The difference between our improved DCM and the heuristic variation of the original DCM is marginal. The main contribution of this paper is the analysis of the algorithm. Our analysis shows that the improved DCM combines the desirable properties of the two variations of the original DCM. That is, it runs in polynomial time and it recovers the true tree with high probability from polynomial-length sequences. Moreover, this is true when the improved DCM is applied to the Neighbor-Joining, the Buneman, as well as the Agarwala algorithm. A key observation for the result of Huson et al. was that threshold graphs of additive distance functions are chordal. We prove a chordal graph theorem concerning minimal triangulations of threshold graphs constructed from distance functions which are close to being additive. This theorem is the key observation behind our improved DCM and it may be interesting in its own right. [Copyright &y& Elsevier]

Kernelization algorithms in the context of Parameterized Complexity are often based on a combination of data reduction rules and combinatorial insights. We will expose in this paper a similar strategy for obtaining polynomial-time approximation algorithms. Our method features the use of approximation-preserving reductions, akin to the notion of parameterized reductions. We exemplify this method to obtain the currently best approximation algorithms for Harmless Set , Differential and Multiple Nonblocker , all of them can be considered in the context of securing networks or information propagation. [ABSTRACT FROM AUTHOR]

Abstract: Minimum Fill-in is a fundamental and classical problem arising in sparse matrix computations. In terms of graphs it can be formulated as a problem of finding a triangulation of a given graph with the minimum number of edges. In this paper, we study the parameterized complexity of local search for the Minimum Fill-in problem in the following form: Given a triangulation H of a graph G, is there a better triangulation, i.e. triangulation with less edges than H, within a given distance from H? We prove that this problem is fixed-parameter tractable (FPT) being parameterized by the distance from the initial triangulation, by providing an algorithm that in time decides if a better triangulation of G can be obtained by swapping at most k edges of H. Our result adds Minimum Fill-in to the list of very few problems for which local search is known to be FPT. [Copyright &y& Elsevier]

Abstract: The Firefighter problem is to place firefighters on the vertices of a graph to prevent a fire with known starting point from lighting up the entire graph. In each time step, a firefighter may be placed on an unburned vertex, permanently protecting it, and the fire spreads to all neighboring unprotected vertices of burning vertices. The goal is to let as few vertices burn as possible. In this paper, we consider a generalization of this problem, where at each time step firefighters can be deployed. Our results answer several open questions raised by Cai et al. [8]. We show that this problem is W[1]-hard when parameterized by the number of saved vertices, protected vertices, and burned vertices. We also investigate several combined parameterizations for which the problem is fixed-parameter tractable. Some of our algorithms improve on previously known algorithms. We also establish lower bounds to polynomial kernelization. [Copyright &y& Elsevier]

Abstract: In this paper, we define the Range LCP problem as follows. Preprocess a string S, of length n, to enable efficient solutions of the following query: Given , , compute , where is the length of the longest common prefix of the suffixes of S starting at locations ℓ and k. This is a natural generalization of the classical LCP problem. We provide algorithms with the following complexities: [1.] Preprocessing Time: , Space: , Query Time: . [2.] Preprocessing Time: none, Space: , Query Time: . However, the query just gives the pairs with the longest LCP, not the LCP itself. [3.] Preprocessing Time: , Space: for arbitrary small constant ε, Query Time: . [Copyright &y& Elsevier]

Abstract: Efficient system management requires continuous knowledge about the state of system and application resources that are typically represented through time series obtained by monitors. Capacity planning studies, forecasting, state aggregation, anomaly and event detection would be facilitated by evidence of data correlations. Unfortunately, the high variability characterizing most monitored time series affects the accuracy and robustness of existing correlation solutions. This paper proposes an innovative approach that is especially tailored to detect linear and non-linear correlation between time series characterized by high variability. We compare the proposed solution and existing algorithms in terms of accuracy and robustness for several synthetic and real settings characterized by low and high variability, linear and non-linear correlation. The results show that our proposal guarantees analogous performance for low variable time series, and improves state of the art in finding correlations in highly variable domains that are of interest for the application context. [Copyright &y& Elsevier]

Abstract: Cloud computing provides massive computation power and storage capacity which enable users to deploy applications without infrastructure investment. Many privacy-sensitive applications like health services are built on cloud for economic benefits and operational convenience. Usually, data sets in these applications are anonymized to ensure data ownersʼ privacy, but the privacy requirements can be potentially violated when new data join over time. Most existing approaches address this problem via re-anonymizing all data sets from scratch after update or via anonymizing the new data incrementally according to the already anonymized data sets. However, privacy preservation over incremental data sets is still challenging in the context of cloud because most data sets are of huge volume and distributed across multiple storage nodes. Existing approaches suffer from poor scalability and inefficiency because they are centralized and access all data frequently when update occurs. In this paper, we propose an efficient quasi-identifier index based approach to ensure privacy preservation and achieve high data utility over incremental and distributed data sets on cloud. Quasi-identifiers, which represent the groups of anonymized data, are indexed for efficiency. An algorithm is designed to fulfil our approach accordingly. Evaluation results demonstrate that with our approach, the efficiency of privacy preservation on large-volume incremental data sets can be improved significantly over existing approaches. [Copyright &y& Elsevier]

Abstract: Cluster analysis plays a critical role in a wide variety of applications; but it is now facing the computational challenge due to the continuously increasing data volume. Parallel computing is one of the most promising solutions to overcoming the computational challenge. In this paper, we target at parallelizing k-Means, which is one of the most popular clustering algorithms, by using the widely available Graphics Processing Units (GPUs). Different from existing GPU-based k-Means algorithms, we observe that data dimensionality is an important factor that should be taken into consideration when parallelizing k-Means on GPUs. In particular, we use two different strategies for low-dimensional data sets and high-dimensional data sets respectively, in order to make the best use of GPU computing horsepower. For low-dimensional data sets, we design an algorithm that exploits GPU on-chip registers to significantly decrease the data access latency. For high-dimensional data sets, we design another novel algorithm that simulates matrix multiplication and exploits GPU on-chip shared memory to achieve high compute-to-memory-access ratio. Our experimental results show that our GPU-based k-Means algorithms are three to eight times faster than the best reported GPU-based algorithms. [Copyright &y& Elsevier]

Abstract: Traffic classification in the Internet is a crucial mechanism necessary to support network services. Using Ternary Content-Addressable Memories (TCAMs) to perform high-speed packet classification has become the de facto standard in industry. TCAMs concurrently match the packet headers against the rules in a classification database providing high throughput unparalleled by software-based solutions. The complexity of packet classification policies has been growing rapidly as the number of Internet services continues to increase. Many complex classification policies are naturally represented in a hierarchical fashion, where different layers perform classification based on the administrative domain and the traffic QoS parameters. However, multiple levels of classification hierarchy incur high lookup latency while high TCAM memory requirements of flattened classification policies is a major issue since TCAMs have very limited capacity. In this paper we focus on the fundamental tradeoff between the TCAM space and the number of lookups in the TCAM classification policies. We consider two optimization problems of dual nature: the first problem is to minimize the number of TCAM entries subject to the constraint on the maximum number of levels in the policy hierarchy; the second problem is to minimize the number of levels in the policy hierarchy subject to the constraint on the maximum number of TCAM entries. We propose efficient algorithms for these problems, which do not require any hardware changes. To the best of our knowledge, this is the first work to study these problems. We also show experimental results that support our findings. [Copyright &y& Elsevier]

Abstract: With the advent of new sequencing technologies able to produce an enormous quantity of short genomic sequences, new tools able to search for them inside a genomic reference sequence have emerged. Because of chemical reading errors or of the variability between organisms, one is interested in finding not only exact occurrences, but also occurrences with up to k mismatches. The contribution of this paper is twofold. On the one hand, we present a generalization of the classical Rabin–Karp string matching algorithm to solve the k-mismatch problem, with average complexity (n text and m pattern lengths, respectively). On the other hand, we show how to employ this idea in conjunction with an index over the text, allowing to search a pattern, with up to k mismatches, in time proportional to its length. This novel tool—rNA (randomized Numerical Aligner)—is in general faster and more accurate than other available tools like SOAP2, BWA, and BOWTIE. rNA executables and source code are freely available at http://iga-rna.sourceforge.net/ . [Copyright &y& Elsevier]

Abstract: Given a pattern string P and a text string T, the one-dimensional real-scale pattern matching problem is to ask for all matched positions in T at which P occurs for some real scales ⩾1. The real-scale indexing problem, which is derived from the real-scale matching problem, aims to preprocess T, so that all positions of scaled P in T can be answered efficiently. In this paper, we propose an improved algorithm for the real-scale indexing problem. For constant-sized alphabets, our preprocessing takes time and space, achieving the answering time , where denotes the number of matched positions and . For the case of large-sized alphabets, our preprocessing can still be implemented with time and space, while the answering time is slightly increased to . Compared to Wangʼs preprocessing algorithm with time, our new indexing algorithm is a significant improvement. [Copyright &y& Elsevier]

Abstract: In this paper we introduce “hybrid” Max 2-CSP formulas consisting of “simple clauses”, namely conjunctions and disjunctions of pairs of variables, and general 2-variable clauses, which can be any integer-valued functions of pairs of boolean variables. This allows an algorithm to use both efficient reductions specific to AND and OR clauses, and other powerful reductions that require the general CSP setting. We use new reductions introduced here, and recent reductions such as “clause-learning” and “2-reductions” generalized to our settingʼs mixture of simple and general clauses. We parametrize a hybrid instance by the fraction p of non-simple clauses. We give an exact, exponential-time but polynomial-space algorithm that is the fastest known for , which includes the well-studied Max 2-Sat problem but also instances with arbitrary mixtures of AND and OR clauses; for an m-clause instance it runs in time . The same algorithm is tied for fastest for general Max 2-CSP (), with running time . The algorithm is the only one to treat mixtures of AND, OR, and general integer-valued clauses more efficiently than the general case, with intermediate running time bounds depending on the value of p. Since even a pure Max 2-Sat input instance may be transformed to a hybrid instance in the course of solving it, the algorithmʼs efficiency and generality go hand in hand. Our algorithm analysis and optimization use the familiar measure-and-conquer approach, but in a variation resulting in mathematical programs that are convex rather than quasi-convex, and can be solved efficiently and with a certificate of optimality. We produce a family of running-time upper-bound formulas, each optimized for instances with a particular value of p but valid for all instances. [Copyright &y& Elsevier]