Conference Programs

The final program (in pdf) can be found here.

List of accepted papers

• Mark de Berg and AmirAli Khosravi. Optimal Binary Space Partitions in the Plane.

  Abstract: An optimal bsp for a set S of disjoint line segments in the plane is a bsp for S that produces the minimum number of cuts. We study optimal bsps for three classes of bsps, which differ in the splitting lines that can be used when partitioning a set of fragments in the recursive partitioning process: free bsps can use any splitting line, restricted bsps can only use splitting lines through pairs of fragment endpoints, and auto-partitions can only use splitting lines containing a fragment. We obtain the two following results: (1) It is np-hard to decide whether a given set of segments admits an auto-partition that does not make any cuts. (2) An optimal restricted bsp makes at most 2 times as many cuts as an optimal free bsp for the same set of segments.

• Piotr Berman, Marek Karpinski and Andrzej Lingas. Exact and approximation algorithms for geometric and capacitated set cover problems .

  Abstract: First, we study geometric variants of the standard set cover motivated by assignment of directional antenna and shipping with deadlines, providing the first known polynomial-time exact solutions. Next, we consider the following general (non-necessarily geometric) capacitated set cover problem. There is given a set of elements with real weights and a family of sets of the elements. One can use a set if it is a subset of one of the sets in the family and the sum of the weights of its elements is at most one. The goal is to cover all the elements with the allowed sets. We show that any polynomial-time algorithm that approximates the uncapacitated version of the set cover problem with ratio r can be converted to an approximation algorithm for the capacitated version with ratio r + 1.357. In particular, the composition of these two results yields a polynomialtime approximation algorithm for the problem of covering a set of customers represented by a weighted n-point set with a minimum number of antennas of variable angular range and fixed capacity with ratio 2.357. This substantially improves on the best known approximation ratio for the latter antenna problem equal to 3. Furthermore, we provide a PTAS for the dual problem where the number of sets (e.g., antennas) to use is fixed and the task is to minimize the maximum set load, in case the sets correspond to line intervals or arcs. Finally, we discuss the approximability of the generalization of the antenna problem to include several bas stations for antennas, and in particular show its APX-hardness already in the uncapacitated case.

• Abhijin Adiga, Sunil Chandran and Diptendu Bhowmick. Boxicity and Poset Dimension .

  Abstract: Let G be a simple, undirected, finite graph with vertex set V (G) and edge set E(G). A k-dimensional box is a Cartesian product of closed intervals [a1, b1] × [a2, b2] × · · · × [ak, bk]. The boxicity of G, box(G) is the minimum integer k such that G can be represented as the intersection graph of k-dimensional boxes, i.e. each vertex is mapped to a k-dimensional box and two vertices are adjacent in G if and only if their corresponding boxes intersect. Let P = (S, P) be a poset where S is the ground set and P is a reflexive, anti-symmetric and transitive binary relation on S. The dimension of P, dim(P) is the minimum integer t such that P can be expressed as the intersection of t total orders. Let GP be the underlying comparability graph of P, i.e. S is the vertex set and two vertices are adjacent if and only if they are comparable in P. It is a well-known fact that posets with the same underlying comparability graph have the same dimension. The first result of this paper links the dimension of a poset to the boxicity of its underlying comparability graph. In particular, we show that for any poset P, box(GP)/(χ(GP) − 1) ≤ dim(P) ≤ 2box(GP), where χ(GP) is the chromatic number of GP and χ(GP) 6= 1. It immediately follows that if P is a height-2 poset, then box(GP) ≤ dim(P) ≤ 2box(GP) since the underlying comparability graph of a height-2 poset is a bipartite graph. The second result of the paper relates the boxicity of a graph G with a natural partial order associated with the extended double cover of G, denoted as Gc: Note that Gc is a bipartite graph with partite sets A and B which are copies of V (G) such that corresponding to every u ∈ V (G), there are two vertices uA ∈ A and uB ∈ B and {uA, vB} is an edge in Gc if and only if either u = v or u is adjacent to v in G. Let Pc be the natural height-2 poset associated with Gc by making A the set of minimal elements and B the set of maximal elements. We show that box(G) 2 ≤ dim(Pc) ≤ 2box(G) + 4. These results have some immediate and significant consequences. The upper bound dim(P) ≤ 2box(GP) allows us to derive hitherto unknown upper bounds for poset dimension such as dim(P) ≤ 2 tree-width (GP)+ 4, since boxicity of any graph is known to be at most its tree-width + 2. In the other direction, using the already known bounds for partial order dimension we get the following: (1) The boxicity of any graph with maximum degree \Delta is O(\Delta log^2 \Delta) which is an improvement over the best known upper bound of \Delta^2 +2. (2) There exist graphs with boxicity \Omega(\Delta log\Delta). This disproves a conjecture that the boxicity of a graph is O(\Delta). (3) There exists no polynomial-time algorithm to approximate the boxicity of a bipartite graph on n vertices with a factor of O(n^{0.5−\epsilon}) for any \epsilon > 0, unless NP = ZPP.

• Andreas Krebs, Nutan Limaye and Meena Mahajan. Counting paths in VPA is complete for #NC^1 .

  Abstract: We give a #NC^1 upper bound for the problem of counting accepting paths in any fixed visibly pushdown automaton. Our algorithm involves a non-trivial adaptation of the arithmetic formula evaluation algorithm of Buss, Cook, Gupta, Ramachandran ([9]). We also show that the problem is #NC1 hard. Our results show that the difference between #BWBP and #NC^1 is captured exactly by the addition of a visible stack to a nondeterministic finite-state automata.

• Rahul Jain, Hartmut Klauck and Shengyu Zhang. Depth-Independent Lower bounds on the Communication Complexity of Read-Once Boolean Formulas .

  Abstract: We show lower bounds of \Omega(\sqrt{n}) and \Omega(n^{1/4}) on the randomized and quantum communication complexity, respectively, of all n-variable read-once Boolean formulas. Our results complement the recent lower bound of \Omega(n/8^d) by Leonardos and Saks [LS09] and \Omega(n/2^{\Omega(d log d)}) by Jayram, Kopparty and Raghavendra [JKR09] for randomized communication complexity of read-once Boolean formulas with depth d. We obtain our result by "embedding" either the Disjointness problem or its complement in any given read-once Boolean formula.

• Yunlong Liu and Xiaodong Wu. Fast Coupled Path Planning: from Pseudo-Polynomial to Polynomial .

  Abstract: The coupled path planning (CPP) problem models the motion paths of the leaves of a multileaf collimator for optimally reproducing the prescribed dose in intensity-modulated radiation therapy (IMRT). Two versions of the CPP problem, unconstrained and constrained CPPs, are studied based on wether specifying the starting and ending positions of the leave paths. By exploring the underlying properties of the problem such as submodularity and L^{\natrual}-convexity, we solve both CPP problems in polynomial time using the path-end hopping, local searching and proximity scaling techniques, improving current best known pseudo-polynomial time algorithms. Our algorithms are simple and easy to be implemented. Experimental results on real medical data showed that our CPP algorithms outperformed previous best-known algorithm by at least two orders of magnitude.

• Hsin-Lung Wu and Chi-Jen Lu. On the hardness against constant-depth linear-size circuit .

  Abstract: The notion of average-case hardness is a fundamental one in complexity theory. In particular, it plays an important role in the research on derandomization, as there are general derandomization results which are based on the assumption that average-case hard functions exist. However, to achieve a complete derandomization, one usually needs a function which is extremely hard against a complexity class, in the sense that any algorithm in the class fails to compute the function on 1/2-2^{-\Omega(n)} fraction of its n-bit inputs. Unfortunately, lower bound results are very rare and they are only known for very restricted complexity classes, and achiev- ing such extreme hardness seems even more difficult. Motivated by this, we study the hardness against linear-size circuits of constant depth in this paper. We show that the parity function is extremely hard for them: any such circuit must fail to compute the parity function on at least 1/2-2^{-\Omega(n)} fraction of inputs.

• Aimal Rextin and Patrick Healy. Maximum Upward Planar Subgraph of a Single-Source Embedded Digraph .

  Abstract: We show how to compute a maximum upward planar single-source subgraph of a single-source embedded DAG G_\phi. We first show that finding a maximum upward planar subgraph of a single-source embedded digraph is NP-complete. We then give a new characterization of upward planar single-source digraphs. We use this characterization to present an algorithm that computes a maximum upward planar single-source subgraph of a single-source embedded DAG. This algorithm takes O(n^4) time in the worst case and O(n^3) time on average.

• Yu-Hsuan Su, Ching-Chi Lin and Der-Tsai Lee. Broadcasting in Heterogeneous Tree Networks .

  Abstract: We consider the broadcasting problem in heterogeneous tree networks. A heterogeneous tree network is represented by a weighted tree T = (V,E) such that the weight of each edge denotes the communication time between the two end vertices. The broadcasting problem is to find a broadcast center such that the maximum communication time from the broadcast center to all vertices is minimized. In this paper, we propose a linear time algorithm for the broadcasting problem in a heterogeneous tree network following the postal model. As a byproduct of the algorithm, we can compute in linear time the broadcasting time of any vertex in the tree, i.e., the maximum time required to transmit messages from the vertex to every other vertex in the tree. Furthermore, an optimal sequence by which the broadcast center broadcasts its messages to all vertices in T can also be determined in linear time.

• Sherman S.M. Chow, Changshe Ma and Jian Weng. Zero-Knowledge Argument for Simultaneous Discrete Logarithms and its Application .

  Abstract: In Crypto’92, Chaum and Pedersen introduced a widely-used protocol (CP protocol for short) for proving the equality of two discrete logarithms (EQDL) with unconditional soundness, which plays a central role in DL-based cryptography. Somewhat surprisingly, the CP protocol has never been improved for nearly two decades since its advent. We note that the CP protocol is usually used as a non-interactive proof by using the Fiat- Shamir heuristic, which inevitably relies on the random oracle model (ROM) and assumes that the adversary is computationally bounded. In this paper, we present an EQDL protocol in the ROM which saves approx. 40% of the computational cost and approx.33% of the prover’s uploading bandwidth. Our idea can be naturally extended for simultaneously showing the equality of n discrete logarithms with O(1)-size commitment, in contrast to the n-element adaption of the CP protocol which requires O(n)-size. This improvement benefits a variety of interesting cryptosystems, ranging from signatures and anonymous credential systems, to verifiable secret sharing and threshold cryptosystems. As an example, we discuss a signature scheme that only takes one (off-line) exponentiation to sign, without utilizing pairing, relying on the standard decisional Diffie-Hellman assumption.

• Frank Ruskey and Aaron Williams. Faster Generation of Shorthand Universal Cycles for Permutations .

  Abstract: A universal cycle for the k-permutations of [n] = {1, 2, ..., n} is a circular string of length n_k that contains each k-permutation exactly once as a substring. Jackson (Discrete Mathematics, 149 (1996) 123–129) proved their existence for all k ≤ n − 1. Knuth (The Art of Computer Programming, Volume 4, Fascicle 2, Addison-Wesley, 2005) pointed out the importance of the k = n − 1 case, where each (n − 1)-permutation is “shorthand” for exactly one permutation of hni. Ruskey-Williams (ACM Transactions on Algorithms, in press) answered Knuth’s request for an explicit construction of a shorthand universal cycle for permutations, and gave an algorithm that creates successive symbols in worst-case O(1)-time. This paper provides two new algorithmic constructions that create successive blocks of n symbols in O(1) amortized time within an array of length n. The constructions are based on a 300 year-old bell-ringer pattern, and the recent shift Gray code by Williams (SODA, (2009) 987-996) and are both implemented in C. For the bell-ringers algorithm, we show that the majority of changes between successive permutations are full rotations; asymptotically, the ratio of them is (n − 2)/n.

• Sudip Biswas, Debajyoti Mondal, Rahnuma Islam Nishat and Md. Saidur Rahman. Minimum-Segment Convex Drawings of 3-Connected Cubic Plane Graphs .

  Abstract: A convex drawing of a plane graph G is a plane drawing of G, where each vertex is drawn as a point, each edge is drawn as a straight line segment and each face is drawn as a convex polygon. A maximal segment is a drawing of a maximal set of edges that form a straight line segment. A minimum-segment convex drawing of G is a convex drawing of G where the number of maximal segments is the minimum among all possible convex drawings of G. In this paper, we present a lineartime algorithm to obtain a minimum-segment convex drawing \Gamma of a 3-connected cubic plane graph G, where the drawing is not a grid drawing. We also give a linear-time algorithm to obtain a convex grid drawing of G on an (n/2 + 1) × (n/2 + 2) grid with at most s_m + 2 maximal segments, where s_m is the lower bound on the number of maximal segments in a convex drawing of G.

• Anke van Zuylen. Multiplying Pessimistic Estimators: Deterministic Approximation of Max TSP and Maximum Triangle Packing .

  Abstract: We give a generalization of the method of pessimistic estimators [14], in which we compose estimators by multiplying them. We give conditions on the pessimistic estimators of two expectations, under which the product of the pessimistic estimators is a pessimistic estimator of the product of the two expectations. We apply this method to give derandomizations of all known approximation algorithms for the maximum traveling salesman problem and the maximum triangle packing problem: we define simple pessimistic estimators based on the analysis of known randomized algorithms and show that we can multiply them to obtain pessimistic estimators for the expected weight of the solution. This gives better and simpler deterministic algorithms than what was previously known.

• Ricky Rosen. A k-Provers Parallel Repetition Theorem for a version of No-Signaling Model .

  Abstract: The parallel repetition theorem states that for any two provers one round game with value at most 1-\epsilon (for \epsilon< 1/2), the value of the game repeated n times in parallel is at most (1-\epsilon^3)^{\Omega(n/log s)} where s is the size of the answers set [Raz98], [Hol07]. It is not known how the value of the game decreases when there are three or more players. In this paper we address the problem of the error decrease of parallel repetition game for k-provers where k > 2. We consider a special case of the No-Signaling model and show that the error of the parallel repetition of k provers one round game, for k > 2, in this model, decreases exponentially depending only on the error of the original game and on the number of repetitions. There were no prior results for k-provers parallel repetition for k > 2 in any model.

• Lei Zhang, Qianhong Wu, Bo Qin and Josep Domingo-Ferrer. Identity-Based Authenticated Asymmetric Group Key Agreement Protocol .

  Abstract: In identity-based public key cryptography, an entity's public key can be easily derived from its identity. The direct derivation of public keys in identity-based public key cryptography eliminates the need for certificates and solves certain public key management problems in traditional public-key cryptosystems. Recently, the notion of asymmetric group key agreement was introduced, in which the group members merely negotiate a common encryption key which is accessible to any entity, but they hold respective secret decryption keys. In this paper, we first propose a security model for identity-based authenticated asymmetric group key agreement (IB-AAGKA) protocols. By exploiting bilinear maps, we then propose an IB-AAGKA protocol which is proven to secure under the Bilinear Diffie-Hellman Exponent (BDHE) assumption. Our protocol is also efficient, and readily adaptable to provide broadcast encryption.

• Doron Nussbaum, Shuye Pu, Jörg-Rüdiger Sack, Takeaki Uno and Hamid Zarrabi-Zadeh Finding Maximum Edge Bicliques in Convex Bipartite Graphs .

  Abstract: A bipartite graph G = (A,B,E) is convex on B if there exists an ordering of the vertices of B such that for any vertex v \in A, vertices adjacent to v are consecutive in B. A complete bipartite subgraph of a graph G is called a biclique of G. Motivated by an application to analyzing DNA microarray data, we study the problem of fnding the maximum edge-cardinality biclique in convex bipartite graphs. Given a bipartite graph G = (A,B,E) which is convex on B, we present a new algorithm that computes the maximum edge-cardinality biclique of G in O(nlog^3n loglog n) time and O(n) space, where n = |A|. This improves the current O(n^2) time bound available for the problem.

• Tobias Friedrich and Thomas Sauerwald. The Cover Time of Deterministic Random Walks .

  Abstract: The rotor router model is a popular deterministic analogue of a random walk on a graph. Instead of moving to a random neighbor, the neighbors are served in a fixed order. We examine how fast this “deterministic random walk” covers all vertices (or all edges). We present general techniques to derive upper bounds for the vertex and edge cover time and derive matching lower bounds for several important graph classes. Depending on the topology, the deterministic random walk can be asymptotically faster, slower or equally fast as the classic random walk. We also examine the short term behavior of deterministic random walks, that is, the time to visit a fixed small number of vertices or edges.

• Sylvain Lazard, Christophe Weibel, Sue Whitesides and Linqiao Zhang. On the Computation of the 3D Visibility Skeleton .

  Abstract: The 3D visibility skeleton is a data structure that encodes the global visibility information of a set of 3D objects. While it is useful in answering global visibility queries, its large size often limits its practical use. In this paper, we address this issue by proposing a subset of the visibility skeleton, which is about 25% to 50% of the whole set. We show that the rest of the data structure can be recovered from the subset as needed, partially or completely. Our recovery method is efficient in the sense that it is output-dependent. We also prove that this subset is minimal for the complexity of our recovery method.

• Lusheng Wang. Near Optimal Solutions for Maximum Quasi-bicliques .

  Abstract: The maximum quasi-biclique problem has been proposed for finding interacting protein group pairs from large protein-protein interaction (PPI) networks. The problem is defined as follows: The Maximum Quasi-biclique Problem: Given a bipartite graph G = (X \cup Y, E) and a number 0 <\delta<= 0.5, find a subset Xopt of X and a subset Yopt of Y such that any vertex x \in Xopt is incident to at least (1-\delta)|Yopt| vertices in Yopt, any vertex y \in Yopt is incident to at least (1-\delta)|Xopt| vertices in Xopt and |Xopt| + |Yopt| is maximized. The problem was proved to be NP-hard [2]. We design a polynomial time approximation scheme to give a quasi-biclique (Xa, Ya) for Xa \subseteq X and Ya \subseteq Y with |Xa|\ge(1-\epsilon)|Xopt| and |Ya|\ge(1-\epsilon)|Yopt| such that any vertex x\in Xa is incident to at least (1-\delta-\epsilon)|Ya| vertices in Ya and any vertex y\in Ya is incident to at least (1-\delta\epsilon)|XA| vertices in Xa for any \epsilon> 0, where Xopt and Yopt form the optimal solution.

• Zhi-Zhong Chen, Bin Ma and Lusheng Wang. A Three-String Approach to the Closest String Problem .

  Abstract: Given a set of n strings of length L and a radius d, the closest string problem (CSP for short) asks for a string tsol that is within a Hamming distance of d to each of the given strings. It is known that the problem is NP-hard and its optimization version admits a polynomial time approximation scheme (PTAS). Parameterized algorithms have been then developed to solve the problem when d is small. In this paper, with a new approach (called the 3-string approach), we first design a parameterized algorithm for binary strings that runs in O(nL + nd^3 6.731^d) time, while the previous best runs in O(nL + nd8^d) time. We then extend the algorithm to arbitrary alphabet sizes, obtaining an algorithm that runs in O(nL + nd1.612^d (|\Sigma| + \beta^2 + \beta - 2)^d) time, where |\Sigma| is the alphabet size and \beta = \alpha^2 + 1-2\alpha^{-1}+\alpha^{-2} with \alpha = (\sqrt(|\Sigma|-1)+1)^{-3}. This new time bound is better than the previous best for small alphabets, including the very important case where |Sigma| = 4 (i.e., the case of DNA strings).

• Shinya Anzai, Jinhee Chun, Ryosei Kasai, Matias Korman and Takeshi Tokuyama. Effect of Corner Information in Simultaneous Placement of K Rectangles and Tableaux .

  Abstract: We consider the optimization problem of finding k nonintersecting rectangles and tableaux in n\times n pixel plane where each pixel has a real valued weight. We discuss existence of efficient algorithms if a corner point of each rectangle/tableau is specified.

• Xin Chen. On Sorting Permutations by Double-Cut-and-Joins .

  Abstract: The problem of sorting permutations by double-cut-and-joins (SBD) arises when we perform the double-cut-and-join (DCJ) operations on pairs of unichromosomal genomes without the gene strandedness information. In this paper we show it is a NP-hard problem by reduction to an equivalent previouslyknown problem, called breakpoint graph decomposition (BGD), which calls for a largest collection of edge-disjoint alternating cycles in a breakpoint graph. To obtain a better approximation algorithm for the SBD problem, we made a suitable modification to Lin and Jiang’s algorithm which was initially proposed to approximate the BGD problem, and then carried out a rigorous performance analysis via fractional linear programming. The approximation ratio thus achieved for the SBD problem is 17/12 +\epsilon = 1.4167+\epsilon, for any positive \epsilon.

• Frans Schalekamp, Michael Yu and Anke van Zuylen. Clustering with or without the Approximation .

  Abstract: We study algorithms for clustering data that were recently proposed by Balcan, Blum and Gupta in SODA’09 [5] and that have already given rise to two follow-up papers. The input for the clustering problem consists of points in a metric space and a number k, specifying the desired number of clusters. The algorithms find a clustering that is provably close to a target clustering, provided that the instance has the “(1 + \alpha, \epsilon)- property”, which means that the instance is such that all solutions to the k-median problem for which the objective value is at most (1 + \alpha) times the optimal objective value correspond to clusterings that misclassify at most an \epsilon fraction of the points with respect to the target clustering. We investigate the theoretical and practical implications of their results. Our main contributions are as follows. First, we show that instances that have the (1 + \alpha, \epsilon)-property and for which, additionally, the clusters in the target clustering are large, are easier than general instances: the algorithm proposed in [5] is a constant factor approximation algorithm with an approximation guarantee that is better than the known hardness of approximation for general instances. Further, we show that it is NP-hard to check if an instance satisfies the (1 + \alpha, \epsilon)-property for a given (\alpha, \epsilon); the algorithms in [5] need such \alpha and \epsilon as input parameters, however. We propose ways to use their algorithms even if we do not know values of \alpha and \epsilon for which the assumption holds. Finally, we implement these methods and other popular methods, and test them on real world data sets. We find that on these data sets there are no \alpha and \epsilon so that the dataset has both (1 + \alpha, \epsilon)-property and sufficiently large clusters in the target solution. For the general case, we show that on our data sets the performance guarantee proved by [5] is meaningless for the values of \alpha,\epsilon such that the data set has the (1 + \alpha, \epsilon)-property. The algorithm nonetheless gives reasonable results, although it is outperformed by other methods.

• Miklos Csuros. Approximate counting with a floating-point counter .

  Abstract: When many objects are counted simultaneously in large data streams, as in the course of network traffic monitoring, or Webgraph and molecular sequence analyses, memory becomes a limiting factor. Robert Morris [Communications of the ACM, 21:840-842, 1978] proposed a probabilistic technique for approximate counting that is extremely economical. The basic idea is to increment a counter containing the value X with probability 2^{-X}. As a result, the counter contains an approximation of lg n after n probabilistic updates, stored in \log\log n bits. Here we revisit the original idea of Morris. We introduce a binary floating-point counter that combines a d-bit significant with a binary exponent, stored together on d+\log\log n bits. The counter yields a simple formula for an unbiased estimation of n with a standard deviation of about 0.6n2^{-d/2}. We analyze the floating-point counter's performance in a general framework that applies to any probabilistic counter. In that framework, we provide practical formulas to construct unbiased estimates, and to assess the asymptotic accuracy of any counter.

• Xue Chen, Guangda Hu and Xiaoming Sun. The Complexity of Word Circuits .

  Abstract: A word circuit [1] is a directed acyclic graph in which each edge holds a w-bit word (i.e. some x\in {0,1}^w) and each node is a gate computing some binary function g:{0,1}^w×{0,1}^w->{0,1}^w. The following problem was studied in [1]: How many binary gates are needed to compute a ternary function f:({0,1}^w)^3->{0,1}^w. They proved that (2+ o(1))2^w binary gates are enough for any ternary functions, and there exists a ternary function which requires word circuits of size (1−o(1))2^w. One of the open problems in [1] is to get these bounds tight within a low order term. In this paper we solved this problem by constructing new word circuits for ternary functions of size (1+o(1))2^w.We investigate the problem in a general setting: How many k-input word gates are needed for computing an n-input word function f:({0, 1}^w)^n->{0,1}^w (here n>=k). We show that for any fixed n,(1−o(1))2^{(n−k)w} basic gates are necessary and (1+o(1))2^{(n−k)w} gates are sufficient (assume w is sufficiently large). Since word circuit is a natural generalization of boolean circuit, we also consider the case when w is a constant and the number of inputs n is sufficiently large. We show that (1±o(1))2^{wn}/((k−1)n) basic gates are necessary and sufficient in this case.

• Sayaka Kamei, Hirotsugu Kakugawa, Stephane Devismes and Sebastien Tixeuil. A Self-Stabilizing 3-Approximation for the Maximum Leaf Spanning Tree Problem in Arbitrary Networks .

  Abstract: The maximum leaf spanning tree (MLST) is a good candidate for constructing a virtual backbone in self-organized multihop wireless networks, but is practically intractable (NP-complete). Self-stabilization is a general technique that permits to recover fromcatastrophic transient failures in self-organized networks without human intervention. We propose a fully distributed self-stabilizing approximation algorithm for the MLST problem on arbitrary topology networks. Our algorithm is the first self-stabilizing protocol that is specifically designed for the construction of an MLST. It improves over previous selfstabilizing solutions both for generality (arbitrary topology graphs vs. unit disk graphs or generalized unit disk graphs, respectively) and for approximation ratio, as it guarantees the number of its leaves is at least 1/3 of the maximum one. The time complexity of our algorithm is O(n^2) rounds.

• Bojan Djordjevic and Joachim Gudmundsson. Detecting areas visited regularly .

  Abstract: We are given a trajectory T and an area A. T might intersect A several times, and our aim is to detect whether T visits A with some regularity, e.g. what is the longest time span that a GPS-GSM equipped elephant visited a specific lake on a daily (weekly or yearly) basis, where the elephant has to visit the lake most of the days (weeks or years), but not necessarily on every day (week or year). We call this a regular pattern with period of one day (week or year, respectively). We consider the most general version of the problem defined in [8], the case where we are not given the period length of the regular pattern but have to find the longest regular pattern over all possible period lengths. We give an exact algorithm with O(n^3.5 log^3 n) running time and an approximate algorithm with O(n^3 log^2 n/\epsilon) running time. We also consider the problem of finding a region that is visited regularly if one is not given. We give exact and approximate algorithms for this problem when the period length is fixed.

• Michael Hartwig. On the Density of Regular and Context-Free Languages .

  Abstract: The density of a language is defined as the function d_L(n) = |L\cap\Sigma^n| and counts the number of words of a certain length accepted by L. The study of the density of regular and context-free languages has attracted some attention culminating in the fact that such languages are either sparse, when the density can be bounded by a polynomial, or dense otherwise. We show that for all nonambiguous context-free languages the number of accepted words of a given length n can also be computed recursively using a finite combination of the number of accepted words smaller than n, or d_L =\sum_{j=1}^k u_jd_L(n-j). This extends an old result by Chomsky and provides us with a more expressive description and new insights into possible applications of the density function for such languages as well as possible characterizations of the density of higher languages.

• Marek Chrobak, Christoph Dürr, Flavio Guíñez, Antoni Lozano and Kim Thang Nguyen. Tile-Packing Tomography is NP-hard .

  Abstract: Discrete tomography deals with reconstructing finite spatial objects from their projections. The objects we study in this paper are called tilings or tile-packings, and they consist of a number of disjoint copies of a fixed tile, where a tile is defined as a connected set of grid points. A row projection specifies how many grid points are covered by tiles in a given row; column projections are defined analogously. For a fixed tile, is it possible to reconstruct its tilings from their projections in polynomial time? It is known that the answer to this question is affirmative if the tile is a bar (its width or height is 1), while for some other types of tiles NP-hardness results have been shown in the literature. In this paper we present a complete solution to this question by showing that the problem remains NP-hard for all tiles other than bars.

• John Augustine, David Eppstein and Kevin Wortman. Approximate Weighted Farthest Neighbors and Minimum Dilation Stars .

  Abstract: We provide an efficient reduction from the problem of querying approximate multiplicatively weighted farthest neighbors in a metric space to the unweighted problem. Combining our techniques with core-sets for approximate unweighted farthest neighbors, we show how to find approximate farthest neighbors that are farther than a factor (1-\epsilon) of optimal in time O(log n) per query in D-dimensional Euclidean space for any constants D and \epsilon. As an application, we find an O(nlog n) expected time algorithm for choosing the center of a star topology network connecting a given set of points, so as to approximately minimize the maximum dilation between any pair of points.

• Yong Zhang, Francis Chin and Hingfung Ting. Approximated Distributed Minimum Vertex Cover Algorithms for Bounded Degree Graphs .

  Abstract: In this paper, two distributed algorithms for the minimum vertex cover problem are given. In the unweighted case, we propose a 2.5-approximation algorithm with round complexity O(Δ), where Δ is the maximal degree of G, improving the previous 3-approximation result with the same round complexity O(Δ). For the weighted case, we give a 4-approximation algorithm with round complexity O(Δ).

• Maxim Babenko, Ilya Razenshteyn and Alexey Gusakov. Triangle-Free 2-Matchings Revisited .

  Abstract: A 2-matching in an undirected graph G = (VG,EG) is a function f:EG->{0,1,2} such that for each node v\in VG the sum of values f(e) on all edges e incident to v does not exceed 2. The size of f is the sum \sum_e f(e). If {e\in EG | f(e)\neq 0} contains no triangles then f is called triangle-free. Cornu´ejols and Pulleyblank devised a combinatorial O(mn)-algorithm that finds a triangle free 2-matching of maximum size (hereinafter n:=|VG|, m:=|EG|) and also established a min-max theorem. We claim that this approach is, in fact, superfluous by demonstrating how their results may be obtained directly from the Edmonds–Gallai decomposition. Applying the algorithm of Micali and Vazirani we are able to find a maximum triangle-free 2-matching in O(m\sqrt{n})-time. Also we give a short self-contained algorithmic proof of the min-max theorem. Next, we consider the case of regular graphs. It is well-known that every regular graph admits a perfect 2-matching. One can easily strengthen this result and prove that every d-regular graph (for d≥3) contains a perfect triangle-free 2-matching. We give the following algorithms for finding a perfect triangle-free 2-matching in a d-regular graph: an O(n)-algorithm for d=3, an O(m+n^{3/2})- algorithm for d=2k(k≥2), and an O(n^2)-algorithm for d=2k+1(k≥2). We also prove that there exists a constant c>1 such that every 3-regular graph contains at least c^n perfect triangle-free 2-matchings.

• Eric Bach, Shuchi Chawla and William Umboh. Threshold rules for online sample selection .

  Abstract: We consider the following sample selection problem. We observe in an online fashion a sequence of samples, each endowed by a quality. Our goal is to either select or reject each sample, so as to maximize the aggregate quality of the subsample selected so far. There is a natural trade-off here between the rate of selection and the aggregate quality of the subsample. We show that for a number of such problems extremely simple and oblivious “threshold rules” for selection achieve optimal tradeoffs between rate of selection and aggregate quality in a probabilistic sense. In some cases we show that the same threshold rule is optimal for a large class of quality distributions and is thus oblivious in a strong sense.

• Josef Cibulka, Jan Kyncl, Viola Meszaros, Rudolf Stolar and Pavel Valtr. On three parameters of invisibility graphs .

  Abstract: The invisibility graph I(X) of a set X\subseteq R^d is a graph whose vertices are the points of X and two vertices are connected by an edge if and only if the straight-line segment connecting the two cor- responding points is not fully contained in X. We settle a conjecture of Matousek and Valtr claiming that for invisibility graphs of planar sets, the chromatic number cannot be bounded in terms of the clique number.

• Bin Fu and Lusheng Wang. Constant Time Approximation Scheme for Largest Well Predicted Subset .

  Abstract: The largest well predicted subset problem is formulated for comparison of two predicted 3D protein structures from the same sequence. A 3D protein structure is represented by an ordered point set A={a_1,...,a_n}, where each ai is a point in 3D space. Given two ordered point sets A={a_1,...,a_n} and B={b_1,...,b_n} containing n points, and a threshold d, the largest well predicted subset problem is to find the rigid transformation T for a largest subset B_{opt} of B such that the distance between a_i and T(b_i) is at most d for every b_i in B_{opt}. A meaningful prediction requires that the size of B_{opt} is at least n\alpha for some constant \alpha [6]. We use LWPS(A,B,d,\alpha) to denote the largest well predicted subset problem with meaningful prediction. An (1+\delta_1, 1-\delta_2)-approximation for LWPS(A,B,d,\alpha) is to find a transformation T to bring a subset B'\subseteq B of size at least (1-\delta_2)|B_{opt}| such that for each b_i\in B', the Euclidean distance between the two points distance (a_i,T(b_i))\le(1+\delta_1)d. We develop a constant time (1+\delta_1,1-\delta_2)-approximation algorithm for LWPS(A,B,d,\alpha) for arbitrary positive constants \delta_1 and \delta_2. To our knowledge, this is the first constant time algorithm in this area. We also study a closely related problem, the bottleneck distance problem, where we are given two ordered point sets A={a_1,...,a_n} and B={b_1,...,b_n} containing n points and the problem is to find the smallest dopt such that there exists a rigid transformation T with distance (ai,T(b_i))\le d_{opt} for every point b_i\in B. A (1+\delta)-approximation for the bottleneck distance problem is to find a transformation T, such that for each bi\in B, distance (ai,T(b_i))\le(1+\delta)d_{opt}, where \delta is a constant. For an arbitrary constant \delta, we obtain a linear O(n/\delta^6) time (1+\delta)-algorithm for the bottleneck distance problem. The best known algorithms for both problems require super-linear time [6].

• Amr Elmasry. The Violation Heap: A Relaxed Fibonacci-Like Heap .

  Abstract: We give a priority queue that achieves the same amortized bounds as Fibonacci heaps. Namely, find-min requires O(1) worst-case time, insert, meld and decrease-key require O(1) amortized time, and delete-min requires O(log n) amortized time. Our structure is simple and promises an efficient practical behavior when compared to other known Fibonacci-like heaps. The main idea behind our construction is to propagate rank updates instead of performing cascaded cuts following a decrease-key operation, allowing for a relaxed structure.

• Michał Kolarz. Directed Figure Codes: Decidability Frontier .

  Abstract: We consider directed figures defined as labelled polyominoes with designated start and end points, with a partial catenation. As we are interested in codicity verification for sets of figures, we show that it is decidable for sets of figures with parallel translation vectors, which is one of the decidability border cases in this setting. We give a constructive proof which leads to a straightforward algorithm.

• Stanley Fung. Online Preemptive Scheduling with Immediate Decision or Notification and Penalties .

  Abstract: We consider online preemptive scheduling problems where jobs have deadlines and the objective is to maximize the total value of jobs completed before their deadlines. In the first problem, preemptions are not free but incur a penalty. In the second problem, a job has to be accepted or rejected immediately upon arrival, and possibly allocated a fixed scheduling interval as well; if these accepted jobs are eventually not completed they incur a penalty (on top of not getting the value of the job). We give an optimal algorithm for the first problem, and new and improved algorithms for the second problem. Our results show how the competitive ratio of online algorithms are affected by such penalty factors.

• Vlad Estivill-Castro, Apichat Heednacram and Francis Suraweera. The Rectilinear k-Bends TSP .

  Abstract: We study a hard geometric problem. Given n points in the plane and a positive integer k, the Rectilinear k-BENDS Traveling Salesman Problem asks if there is a piecewise linear tour through the n points with at most k bends where every line-segment in the path is either horizontal or vertical. The problem has applications in VLSI design. We prove that this problem belongs to the class FPT (fixed-parameter tractable). We give an algorithm that runs in O(kn^2 + k^{4k}n) time by kernelization. We present two variations on the main result. These variations are derived from the distinction between line-segments and lines. Note that a rectilinear tour with k bends is a cover with k line-segments, and therefore a cover by lines. We derive FPT-algorithms using bounded-search-tree techniques and improve the time complexity for these variants.

• Muhammad Nur Yanhaona, Md. Shamsuzzoha Bayzid and Md. Saidur Rahman. Discovering Pairwise Compatibility Graphs .

  Abstract: Given an edge weighted tree T and two non-negative real numbers d_{min} and d_{max}, a pairwise compatibility graph (PCG) of T is a graph G = (V,E), where each vertex u\in V corresponds to a leaf u of T and an edge (u,v)\in E if and only if d_{min}\le d_T(u,v)\le d_max in T. Here, d_T (u, v) denotes the distance between u and v in T, which is the sum of the weights of the edges that comprises the path from u to v. We call T a pairwise compatibility tree of G. For a given graph G, there may be an exponential number of pairwise compatibility trees that generate G as a PCG for arbitrary values of d_{min} and d_{max}. This abundance of possibilities suggests that there is always an edge weighted tree that can generate any given graph G as its PCG, and the proponents of PCGs have conjectured accordingly [KMP03]. However, it is found quite difficult to construct a tree that can generate a particular graph as a PCG, and it remains an open problem whether or not all undirected graphs are PCGs. In this paper we have given a negative answer to that open problem by showing that not all undirected graphs are PCGs. Finding not all graphs are PCGs, we ventured to identify the graphs that are PCGs. We have discovered that the class of PCGs includes all tree power graphs and some of their extensions.

• Alain Bretto and Yannick Silvestre. Factorization of Cartesian products of hypergraphs .

  Abstract: In this article we present the L2-section, a tool used to rep- resent a hypergraph in terms of an "advanced graph" and results leading to first algorithm, in O(nm), for fixed rank and maximal degree, which factorizes a hypergraph in prime factors.

• Daniel Lokshtanov, Neeldhara Misra and Saket Saurabh. Imbalance is Fixed Parameter Tractable .

  Abstract: In the Imbalance Minimization problem we are given a graph G=(V,E) and an integer b and asked whether there is an ordering {v_1,...,v_n} of V such that the sum of the imbalance of all the vertices is at most b. The imbalance of a vertex v_i is the absolute value of the difference between the number of neighbors to the left and right of v_i. The problem is also known as the Balanced Vertex Ordering problem and it finds many applications in graph drawing. We show that this problem is fixed parameter tractable and provide an algorithm that runs in time 2^{O(b\log b)}n^{O(1)}. This resolves an open problem of Kara et al. [COCOON 2005].

• Henning Fernau, Fedor Fomin, Geevarghese Philip and Saket Saurabh. The Curse of Connectivity: t-Total Vertex(Edge) Cover .

  Abstract: We investigate the effect of certain natural connectivity constraints on the parameterized complexity of two fundamental graph covering problems, namely k-VERTEX COVER and k-EDGE COVER. Specifically, we impose the additional requirement that each connected component of a solution have at least t vertices (resp. edges from the solution), and call the problem t-TOTAL VERTEX COVER (resp. t-TOTAL EDGE COVER).We show that (1) both problems remain fixed-parameter tractable with these restrictions, with running times of the form O^{*}(c^k) for some constant c>0 in each case; (2) for every t\ge 2, t-TOTAL VERTEX COVER has no polynomial kernel unless the Polynomial Hierarchy collapses to the third level; (3) for every t\ge 2, t-TOTAL EDGE COVER has a linear vertex kernel of size (t+1)k/t. These results significantly improve earlier work on these problems. Our no-poly-kernel result for t-TOTAL VERTEX COVER, and the known NPhardness result for t-TOTAL EDGE COVER, are in stark contrast to the fact that k-VERTEX COVER has a 2k vertex kernel, and that k-EDGE COVER is solvable in polynomial time. This illustrates how even the slightest connectivity requirement results in a drastic change in the tractability of problems — the curse of connectivity!

• Amr Elmasry. The Longest Almost-Increasing Subsequence .

  Abstract: Given a sequence of n elements, we introduce the notion of an almost-increasing subsequence in two contexts. The first notion is the longest subsequence that can be converted to an increasing subsequence by possibly adding a value, that is at most a fixed constant c, to each of the elements. We show how to optimally construct such subsequence in O(n\log k) time, where k is the length of the output subsequence. As an exercise, we show how to produce in O(n^2\log k) time a special type of subsequences, that we call subsequences obeying the triangle inequality, by using as a subroutine our algorithm for the above case. The second notion is the longest subsequence where every element is at least the value of a monotonically non-decreasing function in terms of the r preceding elements (or even with respect to every r elements among those preceding it). We show how to construct such subsequence in O(n^r\log k) time.

• Rustem Takhanov. Extensions of the Minimum Cost Homomorphism Problem .

  Abstract: Assume D is a finite set and R is a finite set of functions from D to the natural numbers. An instance of the minimum R-cost homomorphism problem (MinHom_R) is a set of variables V subject to specified constraints together with a positive weight cvr for each combination of v\in V and r\in R. The aim is to find a function f:V->D such that f satisfies all constraints and \sum_{v\in V}\sum_{r\in R}c_{vr}r(f(v)) is maximized. This problem unifies well-known optimization problems such as the minimum cost homomorphism problem and the maximum solution problem, and this makes it a computationally interesting fragment of the valued CSP framework for optimization problems. We parameterize MinHom_R by constraint languages, i.e. sets \Gamma of relations that are allowed in constraints. A constraint language is called conservative if every unary relation is a member of it; such constraint languages play an important role in understanding the structure of constraint problems. The dichotomy conjecture for MinHom_R is the following statement: if \Gamma is a constraint language, then MinHom_R is either polynomial-time solvable or NPcomplete. For MinHom the dichotomy result has been recently obtained [Takhanov,STACS,2010] and the goal of this paper is to expand this result to the case of MinHom_R with conservative constraint language. For arbitrary R this problem is still open, but assuming certain restrictions on R we prove a dichotomy. As a consequence of this result we obtain a dichotomy for the conservative maximum solution problem.

• Meng-Tsung Tsai, Da-Wei Wang, Churn-Jung Liau and Tsan-sheng Hsu. Heterogeneous Subset Sampling .

  Abstract: In this paper, we consider the problem of heterogeneous subset sampling. Each element in a domain set has a different probability of being included in a sample, which is a subset of the domain set. Drawing a sample from a domain set of size n takes O(n) time if a Naive algorithm is employed. We propose a Hybrid algorithm that requires O(n) preprocessing time and O(n) extra space. On average, it draws a sample in O(n\sqrt{p^{*}}) time, where p^{*} is \min(p_μ, 1−p_μ) and p_μ denotes the mean of inclusion probabilities. In the worst case, it takes O(n) time to draw a sample. In addition to the theoretical analysis, we evaluate the performance of the Hybrid algorithm via experiments and present an application for particle-based simulations of the spread of a disease.

• Giorgio Ausiello, Paolo Giulio Franciosa, Giuseppe Francesco Italiano and Andrea Ribichini. Computing Graph Spanners in Small Memory: Fault-Tolerance and Streaming .

  Abstract: Let G be an undirected graph with m edges and n vertices. A spanner of G is a subgraph which preserves approximate distances between all pairs of vertices. An f-vertex fault-tolerant spanner is a subgraph which preserves approximate distances, under the failure of any set of at most f vertices. The contribution of this paper is twofold: we present algorithms for computing fault-tolerant spanners, and propose streaming algorithms for computing spanners in very small internal memory. In particular, we give algorithms for computing f-vertex fault-tolerant (3,2)- and (2,1)-spanners of G with the following bounds: our (3,2)-spanner contains O(f^{4/3}n^{4/3}) edges and can be computed in time \~{O}(f^2 m), while our (2,1)-spanner contains O(fn^{3/2}) edges and can be computed in time \~{O}(fm). Both algorithms improve significantly on previously known bounds. Assume that the graph G is presented as an input stream of edges, which may appear in any arbitrary order, and that we do not know in advance m and n. We show how to compute efficiently (3,2)- and (2,1)-spanners of G, using only very small internal memory and a slow access external memory device. Our spanners have asymptotically optimal size and the I/O complexity of our algorithms for computing such spanners is optimal up to a polylogarithmic factor. Our f-vertex fault-tolerant (3,2)- and (2,1)-spanners can also be computed efficiently in the same computational model described above.

• Oleksiy Busaryev, Tamal K. Dey and Yusu Wang. Tracking a Generator by Persistence .

  Abstract: The persistence homology provides a mathematical tool to describe “features” in a principled manner. The persistence algorithm proposed by Edelsbrunner, Letscher and Zomorodian [9] can compute not only the persistence homology for a filtered space, but also representative generating cycles for persistent homology groups. In particular, it can compute a set of essential generating cycles for the homology of the simplicial complex itself. However, if there are dynamic changes either in the filtration or in the underlying simplicial complex, the representative generating cycle can change wildly. In this paper, we consider the problem of tracking generating cycles with temporal coherence. Specifically, our goal is to track a chosen essential generating cycle with the help of the persistence algorithm so that the changes in the tracked cycle are “local”. This requires performing re-ordering operations that allow simplices to be moved from one location to another in the filtration. To handle re-ordering operations, we build upon the matrix framework proposed by Cohen-Steiner et al. [6] to swap two consecutive simplices, so that we can process a re-ordering directly. We present an application showing how our algorithm can track an input essential cycle in a complex constructed out of a point cloud data.

• Frank Ruskey, Alejandro Erickson, Mark Schurch and Jennifer Woodcock. Auspicious Tatami Mat Arrangements .

  Abstract: We introduce tatami tilings, and present some of the many interesting questions that arise when studying them. Roughly speaking, we are considering tilings of rectilinear regions with 1×2 dimer tiles and 1×1 monomer tiles, with the constraint that no four corners of the tiles meet. Typical problems are to minimize the number of monomers in a tiling, or to count the number of tilings in a particular shape. We determine the underlying structure of tatami tilings of rectangles and use this to prove that the number of tatami tilings of an n×n square with n monomers is n2^{n−1}. We also prove that, for fixed-height, the number of tatami tilings of a rectangle is a rational function and outline an algorithm that produces the coefficients of the two polynomials of the numerator and the denominator.

• Miguel A. Mosteiro and Antonio Fernandez Anta. Contention Resolution in Multiple-Access Channels: k-Selection in Radio Networks .

  Abstract: In this paper, contention resolution among k contenders on a multiple-access channel is explored. The problem studied has been modeled as a k-Selection in Radio Networks, in which every contender has to have exclusive access at least once to a shared communication channel. The randomized adaptive protocol presented shows that, for a probability of error 2\epsilon, all the contenders get access to the channel in time (e+1+\xi)k+ O(log^2(1/\epsilon)), where \epsilon\le 1/(n + 1), \xi > 0 is any constant arbitrarily close to 0, and n is the total number of potential contenders. The above time complexity is asymptotically optimal for any significant \epsilon. The protocol works even if the number of contenders k is unknown and collisions can not be detected.

• Jianer Chen and Jie Meng. A 2k Kernel for the Cluster Editing Problem .

  Abstract: The cluster editing problem for a given graph G and a given parameter k asks if one can apply at most k edge insertion/deletion operations on G so that the resulting graph is a union of disjoint cliques. The problem has attracted much attention recently because of its applications in bioinformatics. In this paper, we present a polynomial time kernelization algorithm for the problem that produces a kernel of size bounded by 2k, improving the previously best kernel of size 4k for the problem.

• I Wayan Sudarsana and Selvy Musdalifah. The Ramsey Numbers for a Linear Forest Versus Two Identical Copies of Complete Graphs .

  Abstract: For given graphs G and H, a graph F is called (G,H)-free if F contains no G and the complement of F, \bar{F}, contains no H. Any (G,H)-free graph on n vertices is denoted by (G,H,n)-free. The Ramsey number R(G,H) is defined as the largest natural number n such that no (G,H,n)-free graph exists. Let H be a graph with the chromatic number h and the chromatic surplus s. A connected graph G is called H-good if R(G,H)=(|G|-1)(h-1)+s. Let P_n and K_m be a path of order n and a complete graph of order m, respectively. In this paper, we show that Pn is 2K_m-good. Based on this result, we will able to determine the Ramsey number for a linear forest L versus 2K_m. In addition, we will also generalize the Ramsey number for kP_n versus H_m proposed by Ali et al. [1], where H_m is a cocktail party graph on 2m vertices.

• Satoshi Tayu, Shota Fukuyama and Shuichi Ueno. Universal Test Set for Reversible Circuits .

  Abstract: A set of test vectors is complete for a reversible circuit if it covers all stuck-at faults on the wires of the circuit. It has been known that any reversible circuit has a surprisingly small complete test set, while it is NP-hard to generate a minimum complete test set for a reversible circuit. A test set is universal for a family of reversible circuits if it is complete for any circuit in the family. We show minimum universal test sets for some families of CNOT circuits.

• Mingyu Xiao. A note on Vertex Cover in graphs with maximum degree 3 .

  Abstract: We show that the k-Vertex Cover problem in degree-3 graphs can be solved in O^{*}(1.1616^{k}) time, which improves previous results of O^{*}(1.1940^{k}) by Chen, Kanj and Xia and O^{*}(1.1864^{k}) by Razgon. In this paper, we will present a new way to analyze algorithms for the problem. We use r = k − 2n/5 to measure the size of the search tree, and then get a simple O(1.6651^{K−2n_0/5}-time algorithm, where n_0 is the number of vertices with degree ≥ 2 in the graph. Combining this result with fast algorithms for the Maximum Independent Set problem in degree-3 graphs, we improve the upper bound for the k-Vertex Cover problem in degree-3 graphs.