conference program

The final program (in pdf) is now available.

List of accepted papers

  1. Margareta Ackerman and Erkki Mäkinen. More Efficient Algorithms for Regular Language Enumeration

    Abstract: We present new and more efficient algorithms for regular language enumeration problems. The min-word problem is to find the lexicographically minimal word of length n accepted by a given NFA, the cross-section problem is to list all words of length n accepted by an NFA in lexicographical order, and the enumeration problem is to list the first m words accepted by an NFA according to radix order. For the min-word and cross-section problems, we present algorithms with better asymptotic running times than previously known algorithms. Additionally, for each problem, we present algorithms with better practical running times than previously known algorithms.

  2. Xiang-Yang Li, YaJun Wang and WangSeng Feng. Random Deployment of Wireless Sensor Networks: Power of Second Chance

    Abstract: In a pioneering work, Gupta and Kumar \cite{GK98} studied the critical transmission range needed for the connectivity of random wireless networks. Their result implies that, given a square region of ${\sqrt n} \times {\sqrt n}$, the asymptotic number of random nodes (each with transmission range $1$) needed to form a connected network is $\Theta(n \ln n)$ with high probability. This result has been used as cornerstones in deriving a number of asymptotic bounds for random multi-hop wireless networks, such as network capacity \cite{gupta99capacity,KV-mobicom05,Srikant-mobihoc07,LTF-Mobicom07}. In this paper we show that the asymptotic number of nodes needed for connectivity can be significantly reduced to $\Theta(n \ln \ln n)$ if we are given a ``second chance'' to deploy nodes. More generally, under some deployment assumption, if we can randomly deploy nodes in $k$ rounds (for a constant $k$) and the random deployment of the $i$th round can utilize the information gathered from the previous $i-1$ rounds, we show that the number of nodes needed to provide a connected network with high probability is $\Theta(n \lln{k} n)$. (See Eq~(\ref{eq:lln}) for the definition of $\lln{k}n.$) Similar results hold when we need deploy sensors such that the sensing regions of all sensors cover the region of interest.

  3. Kazushige Sato and Takeshi Tokuyama. Directional Geometric Routing on Mobile Ad Hoc Networks

    Abstract: We consider the geometric routing problem on mobile adhoc wireless networks such that we can send packets by only using local information at each node. We design a novel routing algorithm named {\em directional routing algorithm} by using random local neighbors such that the information can be efficiently maintained if each node dynamically changes its position. We show the effectiveness of our method both theoretically and experimentally. In our scheme, the number of hops and the number of transmissions issued during the routing process are both very small. No centralized control is necessary: The network is implicitly stored and maintained in a distributed fashion at each node using $O(1)$ space, and constructed only using local information in transmission disk of each node.

  4. Akiyoshi Shioura and Mutsunori Yagiura. A Fast Algorithm for Computing a Nearly Equitable Edge Coloring with Balanced Conditions

    Abstract: We discuss the nearly equitable edge coloring problem on a multigraph and propose an efficient algorithm for solving the problem, which has a better time complexity than the previous algorithms. The coloring computed by our algorithm satisfies additional balanced conditions on the number of edges used in each color class, where conditions are imposed on the balance among all edges in the multigraph as well as the balance among parallel edges between each vertex pair. None of the previous algorithms are guaranteed to satisfy these balanced conditions simultaneously. To achieve these improvements, we propose a new recoloring procedure, which is based on a set of edge-disjoint alternating walks, while the existing algorithms are based on an Eulerian circuit or a single alternating walk. This new recoloring procedure makes it possible to reduce the time complexity of the algorithm.

  5. Masashi Kiyomi, Toshiki Saitoh and Ryuhei Uehara. Reconstruction of Interval Graphs

    Abstract: The graph reconstruction conjecture is a long-standing open problem in graph theory. There are many algorithmic studies related it besides mathematical studies, such as DECK CHECKING, LEGITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE COUNTING. We study these algorithmic problems limiting the graph class to interval graphs. Since we can solve GRAPH ISOMORPHISM for interval graphs in polynomial time, DECK CHECKING for interval graphs is easily done in polynomial time. We present in this paper that the other three problems above are solvable in polynomial time on interval graphs.

  6. Debajyoti Bera, Stephen Fenner, Steve Homer and Frederic Green. Efficient Universal Quantum Circuits

    Abstract: We define and construct efficient depth-universal and almost-size-universal quantum circuits. Such circuits can be viewed as general-purpose simulators for central classes of quantum circuits and can be used to capture the computational power of the circuit class being simulated. For depth we construct universal circuits whose depth is the same order as the circuits being simulated. For size, there is a log factor blow-up in the universal circuits constructed here which is nearly optimal.

  7. Iyad Kanj and Dieter Kratsch. Convex Recoloring Revisited: Complexity and Exact Algorithms

    Abstract: We take a new look at the {\sc convex path recoloring} ({\sc CPR}), {\sc convex tree recoloring} ({\sc CTR}), and {\sc convex leaf recoloring} ({\sc CLR}) problems through the eyes of the {\sc independent set} problem. This connection allows us to give a complete characterization of the complexity of all these problems in terms of the number of occurrences of each color in the input instance, and consequently, to present simpler NP-hardness proofs for them than those given earlier. For example, we show that the {\sc CLR} problem on instances in which the number of leaves of each color is at most 3, is solvable in polynomial time, by reducing it to the {\sc independent set} problem on chordal graphs, and becomes NP-complete on instances in which the number of leaves of each color is at most 4. This connection also allows us to develop improved exact algorithms for the problems under consideration. For instance, we show that the {\sc CPR} problem on instances in which the number of vertices of each color is at most 2, denoted {\sc 2-CPR}, proved to be NP-complete in the current paper, is solvable in time $2^{n/4}n^{O(1)}$ ($n$ is the number of vertices on the path) by reducing it after $2^{n/4}$ enumerations to the weighted independent set problem on interval graphs, which is solvable in polynomial time. Then, using an exponential-time reduction from {\sc CPR} to {\sc 2-CPR}, we show that {\sc CPR} is solvable in time $2^{4n/9}n^{O(1)}$. We also present exact algorithms for {\sc CTR} and {\sc CLR} running in time $2^{0.454n}n^{O(1)}$ and $2^{n/3}n^{O(1)}$, respectively. Our algorithms improve the previous algorithms for these problems.

  8. George Karakostas, Stavros Kolliopoulos and Jing Wang. An FPTAS for the minimum total weighted tardiness problem with a fixed number of distinct due dates

    Abstract: Given a sequencing of jobs on a single machine, each one with a weight, processing time, and a due date, the tardiness of a job is the time needed for its completion beyond its due date. We present an FPTAS for the basic scheduling problem of minimizing the total weighted tardiness when the number of distinct due dates is fixed. Previously, an FPTAS was known only for the case where all jobs have a common due date.

  9. Therese Biedl and Michal Stern. Edge-intersection graphs of k-bend paths in grids

    Abstract: Edge-intersection graphs of paths in grids are graphs that can be represented with vertices as paths in grids and edges exist whenever two grid paths share an edge. This type of graphs is motivated by applications in conflict resolution of paths in grid networks. In this paper, we continue the study of edge-intersection graphs of paths in a grid, which was initiated by Golumbic, Lipshteyn and Stern. We show that for any $k$, if the number of bends in each path is restricted to be at most $k$, then not all graphs can be represented. Then we study some graph classes that can be represented with $k$-bend paths, for small values of $k$. We show that every planar graph has a representation with 5-bend paths, every outerplanar graph has a representation with 3-bend paths, and every bipartite planar graph has a representation with 2-bend paths.

  10. Atri Rudra. Limits to List Decoding Random Codes

    Abstract: It has been known since [Zyablov and Pinsker 1982] that a random $q$-ary code of rate $1-H_q(\rho)-\eps$ (where $0<\rho<1-1/q$, $\eps>0$ and $H_q(\cdot)$ is the $q$-ary entropy function) with high probability is a $(\rho,1/\eps)$-list decodable code. (That is, every Hamming ball of radius at most $\rho n$ has at most $1/\eps$ codewords in it.) In this paper we prove the ``converse" result. In particular, we prove that for \emph{every} $0<\rho<1-1/q$, a random code of rate $1-H_q(\rho)-\eps$, with high probability, is not a $(\rho,L)$-list decodable code for any $L\le \frac{c}{\eps}$, where $c$ is a constant that depends only on $\rho$ and $q$. We also prove a similar lower bound for random linear codes. Previously, such a tight lower bound on the list size was only known for the case when $\rho\ge 1-1/q-O(\sqrt{\eps})$ [Guruswami and Vadhan, 2005]. For binary codes a lower bound is known for all $0<\rho<1/2$, though the lower bound is asymptotically weaker than our bound [Blinovsky, 1986]. These results however are not subsumed by ours as they hold for arbitrary codes of rate $1-H_q(\rho)-\eps$.

  11. Chia-Jung Lee, Chi-Jen Lu and Shi-Chun Tsai. Extracting Computational Entropy and Learning Noisy Linear Functions

    Abstract: We study the task of deterministically extracting randomness from sources containing computational entropy. The sources we consider have the form of a conditional distribution $(f(\X)|\X)$, for some function $f$ and some distribution $\X$, and we say that such a source has computational min-entropy $k$ if any circuit of size $2^k$ can only predict $f(x)$ correctly with probability at most $2^{-k}$ given input $x$ sampled from $\X$. We first show that it is impossible to have a seedless extractor to extract from one single source of this kind. Then we show that it becomes possible if we are allowed a seed which is weakly random (instead of perfectly random) but contains some statistical min-entropy, or even a seed which is not random at all but contains some computational min-entropy. This can be seen as a step toward extending the study of multi-source extractors from the traditional, statistical setting to a computational setting. We reduce the task of constructing such extractors to a problem in learning theory: learning linear functions under arbitrary distribution with adversarial noise. For this problem, we provide a learning algorithm, which may have interest of its own.

  12. Petra Berenbrink and Thomas Sauerwald. The Weighted Coupon Collector's Problem and Applications

    Abstract: In the classical coupon collector's problem and coupons are given. In every step one out of the coupons is drawn uniformly at random (with replacement) and the goal is to obtain a copy of all the coupons. It is a well-known fact that in expectation $n \sum_{k=1}^n 1/k \approx n \ln n$ steps are needed to obtain all coupons. In this paper we show two results. First we revisit the weighted coupon collector case where in each step every coupon $i$ is drawn with probability $p_i$. Let $\p=(p_1,\ldots, p_n)$. In this setting exact but unfortunately rather complicated bounds are known to calculate \Ex{ \mathcal{C} (\p) }, which is defined as the expected time to obtain all n coupons for a given probability vector $p$. Here we suggest the following rather simple way to approximate \Ex{ \mathcal{C} (\p) }. Assume $p_1\le p_2\le\cdots\le p_n$ and take $\sum_{i=1}^n 1/(i p_i)$ as an approximation. We prove that, rather unexpectedly, this expression approximates \Ex{ \mathcal{C} (\p) } by a factor of $\Theta(\log \log n)$. We also present an another approximation that achieves an approximation factor of $\Oh(\log \log \log n)$. In the second part of the paper we derive some combinatorial properties of the coupon collecting processes. We apply these properties to show results for the following simple randomized broadcast algorithm. A graph $G$ is given and every node of $G$ is allowed to communicate in every step with a randomly chosen neighbour. In this paper we restrict $G$ to the class of trees and we show that the expected broadcast time is \emph{maximized} if and only if $G$ is the star graph. Besides being the first rigorous extremal result, our finding nicely contrasts with a previous result by Brightwell and Winkler \cite{BW90} showing that for the star graph the cover time of a random walk is \emph{minimized} among all trees.

  13. Sebastian Böcker, Birte Kehr and Florian Rasche. Determination of glycan structure from tandem mass spectra

    Abstract: Glycans are molecules made from simple sugars that form complex tree structures. Glycans constitute one of the most important protein modifications, and identification of glycans remains a pressing problem in biology. Unfortunately, the structure of glycans is hard to predict from the genome sequence of an organism. In this paper, we consider the problem of deriving the topology of a glycan solely from tandem mass spectrometry data. First, we show how to compute the number of glycan topologies, and see that this number usually prohibits to enumerate all glycan topologies in applications. To avoid this combinatorial explosion, we study how to generate glycan tree candidates that sufficiently match the sample mass spectrum. Unfortunately, the resulting problem is known to be computationally hard. We present an efficient exact algorithm for this problem based on fixed-parameter algorithmics, that can process a spectrum in a matter of seconds. We also report some preliminary results of our method on experimental data. We show that our approach is fast enough in applications, and that we can reach very good de novo identification results.

  14. Anton Pervukhin and Sebastian Böcker. Inferring peptide composition from molecular formulas

    Abstract: With the advent of novel mass spectrometry techniques such as Orbitrap MS, it is possible to determine the exact molecular formula of an unknown molecule solely from its isotope pattern. But for protein mass spectrometry, one is facing the problem that many peptides have exactly the same molecular formula even when ignoring the order of amino acids. In this work, we present an efficient method to determine the amino acid composition of an unknown peptide solely from its molecular formula. Our solution is based on efficiently enumerating all solutions of the multi-dimensional integer knapsack problem.

  15. Jin-Yi Cai, Vinod Yegneswaran, Chris Alfeld and Paul Barford. An Attacker-Defender Game for Honeynets

    Abstract: A honeynet is a portion of routed but otherwise unused address space that is instrumented for network traffic monitoring. It is an invaluable tool for understanding unwanted Internet traffic and malicious attacks. We formalize the problem of defending honeynets from systematic mapping (a serious threat to their viability) as a simple two-person game. The objective of the Attacker is to identify a honeynet with a minimum number of probes. The objective of the Defender is to maintain a honeynet for as long as possible before moving it to a new location within a larger address space. Using this game theoretic framework, we describe and prove optimal or near-optimal strategies for both the Attacker and the Defender. This is the first mathematically rigorous study of this increasingly important problem on honeynet defense. Our theoretical ideas provide the first formalism of the honeynet monitoring problem, illustrate the viability of network address shuffling, and inform the design of next generation honeynet defense systems.

  16. Masaki Yamamoto, Shuji Kijima and Yasuko Matsui. A polynomial-time perfect sampler for the Q-Ising with a vertex-independent noise

    Abstract: We present a polynomial-time perfect sampler for the Q-Ising with a vertex-independent noise. The Q-Ising arose in the context of Bayesian image restoration in statistical mechanics. We study the Q-Ising on a two-dimensional square lattice over n vertices, that is, we deal with a discrete state space {1,...,Q}^n for a positive integer Q. Employing the Q-Ising (having a parameter \beta) as a prior distribution, and assuming a Gaussian noise (having another parameter \alpha), a posterior is obtained from the Bayes' formula. Furthermore, we generalize it: the distribution of noise is not necessarily a Gaussian, but any vertex-independent noise. We present a perfect sampler by defning a coupling via a monotone update function. Then, we show O(n log n) mixing time of the Gibbs sampler for the generalized model under a condition that \beta is sufficiently small (whatever the distribution of noise is). In case of a Gaussian, we obtain another more natural condition for rapid mixing that \alpha is sufficiently larger than \beta. Thereby, we show that the expected running time of our sampler is O(n log n).

  17. Jan Manuch, Murray Patterson and Arvind Gupta. The Generalised Character Compatibility Problem for Non-Branching Character Trees

    Abstract: In [Benham, et al, 1995], the authors introduced the Generalised Character Compatibility Problem as a generalisation of the Perfect Phylogeny Problem for a set of species. This generalised problem takes into account the fact that while a species may not be expressing a certain trait, i.e., having teeth, its DNA may contain data for this trait in a non-functional region. The authors show that the Generalised Character Compatibility Problem is NP-complete, by showing NP-completeness for an instance of the problem involving five states, where the characters' state transition tree is branching. They also present a special case of the problem that is polynomial-time solvable. The authors posed an open problem about the complexity of this problem when no branching is allowed in the character trees. We extend these results by showing NP-completeness for an instance of the Generalised Character Compatibility Problem in which each character's state transition tree is 0->1->2 (no branching). This, however, does not provide an answer to the exact question posed in [Benham, et al, 1995], which allows only one type of generalised state: {0,2}. On the other hand, we show that in this case the problem is polynomial when the phylogeny tree of species is allowed to have only one branch by unveiling a surprising connection to C1P matrices used in gene clustering.

  18. Nathann Cohen, Fedor Fomin, Gregory Gutin, EUN JUNG KIM, Saket Saurabh and Anders Yeo. Algorithm for Finding $k$-Vertex Out-trees and its Application to $k$-Internal Out-branching Problem

    Abstract: An out-tree $T$ is an oriented tree with only one vertex of in-degree zero. A vertex $x$ of $T$ is internal if its out-degree is positive. We design randomized and deterministic algorithms for deciding whether an input digraph contains a given out-tree with $k$ vertices. The algorithms are of runtime $O^*(5.704^k)$ and $O^*(5.704^{k(1+o(1))})$, respectively. We apply the deterministic algorithm to obtain a deterministic algorithm of runtime $O^*(c^k)$, where $c$ is a constant, for deciding whether an input digraph contains a spanning out-tree with at least $k$ internal vertices. This answers in affirmative a question of Gutin, Razgon and Kim (Proc. AAIM'08).

  19. Pinar Heggernes, Federico Mancini, Charis Papadopoulos and R. Sritharan. Strongly chordal and chordal bipartite graphs are sandwich monotone

    Abstract: A graph class is sandwich monotone if, for every pair of its graphs $G_1=(V,E_1)$ and $G_2=(V,E_2)$ with $E_1 \subset E_2$, there is an ordering $e_1, \ldots, e_k$ of the edges in $E_2 \setminus E_1$ such that $G=(V, E_1 \cup \{e_1, \ldots, e_i\})$ belongs to the class for every $i$ between $1$ and $k$. In this paper we show that strongly chordal graphs and chordal bipartite graphs are sandwich monotone, answering an open question by Bakonyi and Bono from 1997. So far, very few classes have been proved to be sandwich monotone, and the most famous of these are chordal graphs. Sandwich monotonicity of a graph class implies that minimal completions of arbitrary graphs into that class can be recognized and computed in polynomial time. For minimal completions into strongly chordal or chordal bipartite graphs no polynomial-time algorithm has been known. With our results such algorithms follow for both classes. In addition, from our results it follows that all strongly chordal graphs and all chordal bipartite graphs with edge constraints can be listed efficiently.

  20. Eric J Mc Dermid and Robert Irving. Popular Matchings: Structure and Algorithms

    Abstract: An instance of the popular matching problem (POP-M) consists of a set of applicants and a set of posts. Each applicant has a preference list that strictly ranks a subset of the posts. A matching M of applicants to posts is popular if there is no other matching M' such that more applicants prefer M' to M than prefer M to M'. Abraham et al described a linear time algorithm to determine whether a popular matching exists for a given instance of POP-M, and if so to find a largest such matching. A number of variants and extensions of POP-M have recently been studied. This paper provides a characterization of the set of popular matchings for an arbitrary POP-M instance in terms of a structure called the switching graph, a directed graph computable in linear time from the preference lists. We show that the switching graph can be exploited to yield efficient algorithms for a range of associated problems, including the counting and enumeration of the set of popular matchings, generation of a popular matching uniformly at random, finding all applicant-post pairs that can occur in a popular matching, and computing popular matchings that satisfy various additional optimality criteria. Our algorithms for computing such optimal popular matchings improve those described in a recent paper by Kavitha and Nasre.

  21. Scott Diehl, Dieter van Melkebeek and Ryan Williams. An Improved Time-Space Lower Bound for Tautologies

    Abstract: We show that for all reals $c$ and $d$ such that $c^2d<4$ there exists a positive real $e$ such that tautologies of length $n$ cannot be decided by both a nondeterministic algorithm that runs in time $n^c$, and a nondeterministic algorithm that runs in time $n^d$ and space $n^e$. In particular, for every $d < \sqrt[3]{4}$ there exists a positive $e$ such that tautologies cannot be decided by a nondeterministic algorithm that runs in time $n^d$ and space $n^e$.

  22. Shuji Kijima and Toshio Nemoto. Finding a Level Ideal of a Poset

    Abstract: This paper is concerned with finding a level ideal (LI) of a partially ordered set (poset): given a finite poset P, a level of each element p in P is defined as the number of ideals which do not include p, then the problem is to find an ideal consisting of elements whose levels are less than a given integer i. We call the ideal as the i-th LI. The concept of the level ideal is naturally derived from the generalized median stable matching, that is a fair stable marriage introduced by Teo and Sethuraman (1998). Cheng (2008) showed that finding the i-th LI is #P-hard when i=O(N), where N is the total number of ideals of P. This paper shows that finding the i-th LI is #P-hard even if i=O(N^{1/c}) where c \geq 1 is an arbitrary constant. Meanwhile, we give a polynomial time exact algorithm when i=O((log N)^{c'}) where c' is an arbitrary positive constant. We also devise two randomized approximation schemes using an oracle of almost uniform sampler for ideals of a poset. This is the first result on randomized approximation schemes for the LI, and for the generalized median stable matching.

  23. Mahmoud Fouz, Manfred Kufleitner, Bodo Manthey and Nima Zeini Jahromi. On Smoothed Analysis of Quicksort and Hoare's Find

    Abstract: We provide a smoothed analysis of Hoare's find algorithm and we revisit the smoothed analysis of quicksort. Hoare's find algorithm - often called quickselect - is an easy-to-implement algorithm for finding the k-th smallest element of a sequence. While the worst-case number of comparisons that Hoare's find needs is $\Theta(n^2)$, the average-case number is $\Theta(n)$. We analyze what happens between these two extremes by providing a smoothed analysis of the algorithm in terms of two different perturbation models: additive noise and partial permutations. In the first model, an adversary specifies a sequence of $n$ numbers of $[0,1]$, and then each number is perturbed by adding a random number drawn from the interval $[0,d]$. We prove that Hoare's find needs $\Theta(\frac{n}{d+1} \sqrt{n/d} + n)$ comparisons in expectation if the adversary may also specify the element that we would like to find. Furthermore, we show that, for finding the median of a sequence, Hoare's find needs $\Omega(n \sqrt{n/d} (1-\sqrt{d/2}))$ comparisons for $d < 2$, it needs $\Theta(n \log n)$ comparisons for $d = 2$, and $O(\frac{d}{d-2} n)$ for $d > 2$. All these bounds are tight. In the second model, each element is marked with probability p and then a random permutation is applied to the marked elements. We prove that the expected number of comparisons to find the median is $\Omega\bigl((1-p) \frac np \log n\bigr)$, which is again tight. Finally, we provide lower bounds for the smoothed number of comparisons of quicksort and Hoare's find for the median-of-three pivot rule, which usually yields faster algorithms than always selecting the first element: The pivot is the median of the first, middle, and last element of the sequence. We show that median-of-three does not yield a significant improvement over the classic rule: the lower bounds for the classic rule carry over to median-of-three.

  24. Tamara Mchedlidze and Antonios Symvonis. Crossing-optimal acyclic HP-completion for outerplanar st-digraphs

    Abstract: Given an embedded planar acyclic digraph G, the "acyclic hamiltonian path completion with crossing minimization (Acyclic-HPCCM)" problem is to determine a hamiltonian path completion set of edges such that, when these edges are embedded on G, they create the smallest possible number of edge crossings and turn G to a hamiltonian acyclic digraph. In this paper, we present a linear time algorithm which solves the Acyclic-HPCCM problem on any outerplanar st-digraph G. The algorithm is based on properties of the optimal solution and an "st-polygon decomposition of G". As a consequence of our result, we can obtain for the class of outerplanar st-digraphs upward topological 2-page book embeddings with minimum number of spine crossings.

  25. Tsz Hon Yuen, Qiong Huang, Yi Mu, Willy Susilo, Duncan S. Wong and Guomin Yang. Efficient Non-Interactive Range Proof

    Abstract: We propose the first non-interactive range proof which is not based on the heuristic Fiat-Shamir transformation and whose security does not rely on the random oracle assumption. It is also more efficient than the existing ones. Compared with the most efficient constant-size range proof available in the literature, our scheme has the proof size reduced by at least 40%. We also extend our range proof techniques to the construction of a non-interactive set membership proof. In addition, our set membership proof also supports set non-membership proof, that is, given a commitment to a secret $w$, the proof can show, in zero-knowledge, that $w$ belongs to some discrete set $\Phi$ (set membership proof); or does not belong to some discrete set $\Phi'$ (set non-membership proof).

  26. Kenneth Berman and Chad Yoshikawa. Why Locally-Fair Maximal Flows in Client-Server Networks Perform Well

    Abstract: Maximal flows reach at least a 1/2 approximation of the maximum flow in client-server networks. In this paper we show that by adding only 1 additional time round to any distributed maximal flow algorithm this 1/2-approximation can be improved on bounded-degree networks. We call these modified maximal flows `locally fair' since there is a measure of fairness prescribed to each client and server in the network. Let N=(U,V,E,b) represent a client-server network with clients U, servers V, network links E, and node capacities b, where we assume that each capacity is at least one unit. Let d(u) denote the b-weighted degree of any node u, Delta = max (d(u) | u in U) and delta = min (d(v) | v in V). We show that a locally-fair maximal flow f achieves an approximation to the maximum flow of min (1, (Delta^2 - delta)/(2 Delta^2 - delta*Delta - Delta) ) and this result is sharp for any given integers delta and Delta. This results are of practical importance since local-fairness loosely models the steady-state behavior of TCP/IP and these types of degree-bounds often occur naturally (or are easy to enforce) in real client-server systems.

  27. Carsten Gutwenger, Petra Mutzel and Bernd Zey. On the Hardness and Approximability of Planar Biconnectivity Augmentation

    Abstract: Given a planar graph G=(V,E), the planar biconnectivity augmentation problem (PBA) asks for an edge set E'\subseteq V\times V such that G+E' is planar and biconnected. This problem is known to be NP-hard in general; see [Kant, Bodlaender 1991]. We show that PBA is already NP-hard if all cutvertices of G belong to a common biconnected component B^*, and even remains NP-hard if the SPQR-tree of B^* (excluding Q-nodes) has a diameter of at most two. For the latter case, we present a new 5/3-approximation algorithm with runtime O(|V|^{2.5}). Though a 5/3-approximation of PBA has already been presented [Fialko, Mutzel 1998], we give a family of counter-examples showing that this algorithm cannot achieve an approximation ratio better than 2, thus the best known approximation ratio for PBA is 2.

  28. Sebastian Böcker, Quang Bao Anh Bui, Patrick Seeber and Anke Truss. Computing Bond Types in Molecule Graphs

    Abstract: In this paper we deal with restoring missing information in molecule databases: Some data formats only store the atoms’ configuration but omit bond multiplicities. As this information is essential for various applications in chemistry, we consider the problem of recovering bond type information using a scoring function for the possible valences of each atom—the Bond Type Assignment problem. We prove the NP-hardness of Bond Type Assignment and give an exact fixed-parameter algorithm for the problem where bond types are computed via dynamic programming on a tree decomposition of the molecule graph. We evaluate our algorithm on a set of real molecule graphs and find that it works fast and accurately.

  29. Christian Bachmaier, Franz Josef Brandenburg, Wolfgang Brunner and Raymund Fülöp. Coordinate Assignment for Cyclic Level Graphs

    Abstract: The Sugiyama framework is the most commonly used concept for visualizing directed graphs. It draws them in a hierarchical way and operates in four phases: cycle removal, leveling, crossing reduction, and coordinate assignment. However, there are situations where cycles must be displayed as such, e. g., distinguished cycles in the biosciences and scheduling processes which repeat in a daily or weekly turn. This excludes the removal of cycles. In their seminal paper Sugiyama et al. introduced recurrent hierarchies as a concept to draw graphs with cycles. However, this concept has not received much attention in the following years. In this paper we supplement our cyclic Sugiyama framework and investigate the coordinate assignment phase. We provide an algorithm which runs in linear time and constructs drawings which have at most two bends per edge and use quadratic area.

  30. Chih-Chiang Yu, Wing-Kai Hon and Biing-Feng Wang. Efficient Data Structures for the Orthogonal Range Successor Problem

    Abstract: This paper considers a type of orthogonal range query, called orthogonal range successor query, which is defined as follows: Let P be a set of n points that lie on an n × n grid. Then, for any given rectangle R, our target is to report, among all points of P ∩ R, the point which has the smallest y-coordinate. We propose two indexing data structures for P so that online orthogonal range successor queries are supported efficiently. The first one is a succinct index where only O(n) words are allowed for the index space. We show that each query can be answered in O(log n / loglog n) time, thus improving the best-known O(log n) time by Mäkinen and Navarro. The improvement stems from the design of an index with O(1) query time when the points are restricted to lie on a narrow grid, which in turn extends the recent wavelet tree technique to support the desired query. Our second result is a general framework for indexing points in the d-dimensional grids. We show an O(n{1+eps})-space index that supports each d-dimensional query in optimal O(1) time. Our second index is very simple and when d = 2, it is as efficient as the existing index by Crochemore et al.

  31. Joseph Chan, Francis Chin, Hing-Fung Ting and Yong Zhang. Online Tree Node Assignment with Resource Augmentation

    Abstract: Given a complete binary tree of height~$h$, the \textit{online tree node assignment problem} is to serve a sequence of assignment/release requests, where an \textit{assignment request}, with an integer parameter~$0 \le i \le h$, is served by assigning a (tree) node of level (or height)~$i$ and a \textit{release request} is served by releasing a specified assigned node. The node assignments have to guarantee that no node is assigned to two assignment requests unreleased, and every leaf-to-root of the tree contains at most one assigned node. With assigned node reassignments allowed, the target of the problem is to minimize the number of assignment/reassigment, i.e., the cost, to serve the whole sequence of requests. This online tree node assignment problem is fundamental to many applications, including OVSF code assignment in WCDMA networks, buddy memory allocation and hypercube subcube allocation. Most of the previous results focus on how to achieve good performance when the same amount of resource is given to both the online and the optimal offline algorithms, i.e., one tree. In this paper, we consider resource augmentation, where the online algorithm is allowed to use more trees than the optimal offline algorithm. By using different approaches, we give (1) a $1$-competitive online algorithm, which uses $(h+1)/2$ trees, and is optimal because $(h+1)/2$ trees are required by any online algorithm to match the cost of the optimal offline algorithm with one tree. (2) a $2$-competitive algorithm with $3h/8+3$ trees. (3) an amortized $8/3$-competitive algorithm with $11/4$ trees. (4) a general amortized $(4/3 + \alpha)$-competitive algorithm with $(11/4 + 4/(3\alpha))$ trees, for any $\alpha$ where $0 < \alpha \le 4/3$.

  32. Alexander Souza and Axel Simroth. On an Online Traveling Repairman Problem with Flowtimes: Worst-Case and Average-Case Analysis

    Abstract: We consider an online problem where a server operates on an edge-weighted graph $G$ and an adversarial sequence of requests to vertices is released over time. Each request requires one unit of servicetime. The server is free to choose the ordering of service and intends to minimize the total flowtime of the requests. A natural class of algorithms for this problem are \alg{Ignore} algorithms. These wait and gather several arriving requests that are then served within one tour. The requests arriving in the meantime are also gathered, i.e., ignored, and served in the next tour. From worst-case perspective, we show that, \alg{Ignore} algorithms are not competitive for flowtime minimization. From an average-case point of view, we obtain a more detailed picture. In our model, the adversary may still choose the vertices of the requests arbitrarily. But the arrival times are according to a stochastic process (with some rate $\lambda > 0$), chosen by the adversary out of a natural class of processes. The class contains the Poisson-process and (some) deterministic arrivals as special cases. We then show that there is an \alg{Ignore} algorithm that is competitive if and only if $\lambda \not = 1$. Specifically, for $\lambda \not = 1$, the expected competitive ratio of the algorithm is within a constant of $\ham(G)$, where $\ham(G)$ is the length of a shortest cycle that visits all vertices of $G$. The reason for this is that if $\lambda \not = 1$ the requests either arrive slow enough for our algorithm or too fast even for an offline optimal algorithm. For $\lambda = 1$ the routing-mistakes of the online algorithm accumulate just as in the worst case. As an additional result, we show how \alg{Ignore} tours are constructed optimally in polynomial time, if the underlying graph $G$ is a line.

  33. Toshihiko Takahashi, Ryo Fujimaki and Youhei Inoue. A (4n -4)-bit representation of a rectangular drawing or floorplan

    Abstract: A subdivision of a rectangle into rectangular faces with horizontal and vertical line segments is called a rectangular drawing or floorplan. Yamanaka and Nakano published a (5n-5)-bit representation of a rectangular drawing, where n is the number of inner rectangles. In this paper, a (4n-4)-bit representation of rectangular drawing is introduced. Moreover, this representation gives an alternative proof that the number of rectangles with n rectangles is at most 13.5^{n-1}.

  34. Enoch Peserico and Luca Pretto. HITS can converge slowly, but not too slowly, in score and rank

    Abstract: This paper explores the fundamental question of how many iterations the celebrated HITS algorithm requires on a general graph to converge in score and, perhaps more importantly, in rank (i.e. to "get right" the order of the nodes). We prove upper and almost matching lower bounds. We also extend our results to weighted graphs.

  35. Marek Karpinski and Yakov Nekrich. Space-Efficient Multi-Dimensional Range Reporting

    Abstract: We present a data structure that supports three-dimensional range reporting queries in $O(\log \log U + (\log \log n)^3+k)$ time and uses $O(n\log^{1+\eps} n)$ space, where $U$ is the size of the universe, $k$ is the number of points in the answer, and $\eps$ is an arbitrary constant. This result improves over the data structure of Alstrup, Brodal, and Rauhe (FOCS 2000) that uses $O(n\log^{1+\eps} n)$ space and supports queries in $O(\log n+k)$ time and the data structure of Nekrich (SoCG'07) that uses $O(n\log^{4} n)$ space and supports queries in $O(\log \log U + (\log \log n)^2 + k)$ time. Our result allows us to significantly reduce the space usage of the fastest previously known static and incremental $d$-dimensional data structures, $d\geq 3$, at a cost of increasing the query time by a negligible $O(\log \log n)$ factor.

  36. Michael Fellows, Jiong Guo, Christian Komusiewicz, Rolf Niedermeier and Johannes Uhlmann. Graph-Based Data Clustering with Overlaps

    Abstract: We introduce overlap cluster graph modification problems where, other than in most of previous work, the clusters of the goal graph may overlap. More precisely, the studied graph problems ask for a minimum number of edge modifications such that the resulting graph consists of clusters (that is, maximal cliques) that may overlap up to a certain amount specified by the overlap number s: In the case of s-vertex overlap, each vertex may be part of at most s maximal cliques; s-edge overlap is analogously defined in terms of edges. We provide a complete complexity dichotomy (polynomial-time solvable vs NP-complete) for the underlying edge modification problems, develop forbidden subgraph characterizations of ``cluster graphs with overlaps'', and study the parameterized complexity in terms of the number of allowed edge modifications, achieving both parameterized hardness (in case of unbounded s-values) as well as fixed-parameter tractability results (in case of constant s-values).

  37. Khaled Elbassioni, Kazuhisa Makino and Imran Rauf. On the Readability of Monotone Boolean Formulae

    Abstract: Golumbic et al. [Discrete Applied Mathematics 154(2006) 1465-1477] defined the \emph{readability} of a monotone Boolean function $f$ to be the minimum integer $k$ such that there exists an $\wedge-\vee$-formula equivalent to $f$ in which each variable appears at most $k$ times. They asked whether there exists a polynomial-time algorithm, which given a monotone Boolean function $f$, in CNF or DNF form, checks whether $f$ is a read-$k$ function, for a fixed $k$. In this paper, we partially answer this question already for $k=2$ by showing that it is NP-hard to decide if a given monotone formula represents a read-twice function. It follows also from our reduction that it is NP-hard to approximate the readability of a given monotone Boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$ within a factor of $\cO(n)$. We also give tight sublinear upper bounds on the readability of a monotone Boolean function given in CNF (or DNF) form, parameterized by the number of terms in the CNF and the maximum size in each term, or more generally the maximum number of variables in the intersection of any constant number of terms. When the variables of the DNF can be ordered so that each term consists of a set of consecutive variables, we give much tighter polylogarithmic bounds on the readability.

  38. Lars Nagel, Stefan Dantchev and Tom Friedetzky. Sublinear-time Algorithms for Tournament Graphs

    Abstract: We show that a random walk on a tournament on n vertices finds either a sink or a 3-cycle in expected time O(sqrt(n) log(n) sqrt(log*(n))). This result is motivated by the search of a generic algorithm for solving a large class of search problems called Local Search, LS. LS is defined by us as a generalisation of the well-known class PLS.

  39. Marwan Al-Jubeh, Michael Hoffmann, Mashhood Ishaque, Diane Souvaine and Csaba Toth. Convex Partitions with 2-Edge Connected Dual Graphs

    Abstract: It is shown that for every finite set of disjoint convex polygonal obstacles in the plane, with a total of $n$ vertices, the free space around the obstacles can be partitioned into open convex cells whose dual graph (defined below) is 2-edge connected. Intuitively, every edge of the dual graph corresponds to a pair of adjacent cells that are both incident to the same vertex. Aichholzer {\it et al.} recently conjectured that given an even number of line-segment obstacles, one can construct a convex partition by successively extending the segments along their supporting lines such that the dual graph is the union of two edge-disjoint spanning trees. Here we present a counterexample to this conjecture, which consists of 16 disjoint line segments, such that the dual graph of any convex partition constructed by this method has a {\em bridge} edge, and thus the dual graph cannot be partitioned into two spanning trees. Counterexamples of arbitrarily larger sizes can be constructed similarly. Questions about the dual graph of a convex partition are motivated by the still unresolved conjecture about disjoint compatible geometric matchings by Aichholzer {\it et al.}. It has application in the design of fault-tolerant wireless networks in the presence of obstacles (e.g. tall buildings in a city).

  40. Michael Kowalczyk. Classification of a Class of Counting Problems using Holographic Reductions

    Abstract: The purpose of this work is to prove a generalization of an existing dichotomy theorem, extending the result to a larger class of counting problems. This is achieved through the use of interpolation and holographic reductions. We also use holographic reductions to establish a close connection between a class of problems which are solvable using Fibonacci gates and the class of problems which can be solved by applying a particular kind of counting argument.

  41. Rastislav Sramek, Bernd Fischer, Elias Vicari and Peter Widmayer. Optimal Transition Selection for Targeted Protein Quantification

    Abstract: Multiple reaction monitoring (MRM) is a mass spectrometric method to quantify a specified set of proteins. In this paper we identify an important problem related to MRM peptide quantification accuracy and propose a mathematical formulation. We show the general mathematical formulation to be NP-complete. We propose a greedy algorithm towards the optimizing of the proposed objective function. Our numerical experiments show the proposed algorithm to be orders of magnitude superior over the currently used methods.

  42. Isabelle Fagnot, Guillaume Fertin and Stéphane Vialette. On finding small 2-generating sets

    Abstract: Given a set of positive integers $S$, we consider the problem of finding a minimum cardinality set of positive integers $X$ (called a {\em minimum $2$-generating set of $S$}) such that every element of $S$ is an element of $X$ or is the the sum of two (non-necessarily distinct) elements of $X$. We give some elementary properties of $2$-generating sets and prove that finding a minimum cardinality $2$-generating set is hard to approximate within ratio $1+\varepsilon$ for any $\varepsilon > 0$. We then prove our main result, which consists in a standard representation lemma for minimum cardinality $2$-generating sets.

  43. Oscar Ibarra and Omer Egecioglu. Hierarchies and Characterizations of Stateless Multicounter Machines

    Abstract: We investigate the computing power of stateless multicounter machines with reversal-bounded counters. Such a machine can be deterministic, nondeterministic, realtime (the input head moves right at every step), or non-realtime. The deterministic realtime stateless multicounter machines has been studied [1]. Here we investigate non-realtime machines in both deterministic and nondeterministic cases with respect to the number of counters and reversals. We also consider closure properties and relate the models to stateless multihead automata and show that the bounded languages accepted correspond exactly to semilinear languages.

  44. Kerui Min, Ming-Yang Kao and Hong Zhu. The Closest Pair Problem Under the Hamming Metric

    Abstract: Finding the closest pair among a given set of points under Hamming Metric is a fundamental problem with many applications. Let $n$ be the number of points and $D$ the dimensionality of all points. We show that for $0< D \le n$, it can be solved within time complexity $O(n^{1.843} D^{0.533})$. We also provide an alternative approach not involving algebraic matrix multiplication, which has the time complexity $O(n^2D/\log^2 D)$ with small constant, and is effective for practical use. Moreover, for arbitrary large alphabet set, an algorithm with the time complexity $O(n^2\sqrt{D})$ is obtained for $0< D \le n$. In addition, the algorithms propose in this paper provides a solution to the open problem stated by Kao et al.

  45. Agnes Chan, Rajmohan Rajaraman, Zhifeng Sun and Feng Zhu. Approximation Algorithms for Key Management in Secure Multicast

    Abstract: A number of data dissemination systems, such as interactive gaming, stock data distribution, video conferencing, and publish-subscribe systems need to guarantee the privacy and authenticity of the participants. Many such systems rely on symmetric key cryptography, whereby all legitimate group members share a common key for group communication. An important problem in such a system is to maintain the shared group key as the group membership changes. The focus of this paper is on a well-studied key management approach that uses a hierarchy of auxiliary keys to update the shared group key and maintain the desired security properties. In this key hierarchy scheme, a group controller distributes auxiliary keys to subgroups of members; when the group membership changes, an appropriate subset of the keys are updated and multicast to the relevant subgroups. We consider the problem of determining a key hierarchy that minimizes the average communication cost of an update, given update frequencies of the group members and an edge-weighted undirected graph that captures routing costs. We first consider the objective of minimizing the average number of multicast messages needed for an update (thus ignoring the underlying routing graph), for which we present polynomial-time approximation scheme (PTAS). We next show that when routing costs are considered, the problem is NP-hard even when the underlying routing network is a tree network or even when every group member has the same update frequency. Our main result is a polynomial time constant-factor approximation algorithm for the general case where the routing network is an arbitrary weighted graph and group members have nonuniform update frequencies. We obtain improved constant approximation factors for the special cases where the routing network is a tree and when the update frequencies are uniform.

  46. Vittorio Bilo', Michele Flammini, Gianpiero Monaco and Luca Moscardelli. On the performances of Nash Equilibria in Isolation Games

    Abstract: We study the performances of Nash equilibria in isolation games, a class of competitive location games recently introduced in \cite{ZCT08}. For all the cases in which the existence of Nash equilibria has been shown, we give tight or asymptotically tight bounds on the prices of anarchy and stability under the two classical social functions mostly investigated in the scientific literature, namely, the minimum utility per player and the sum of the players' utilities. Moreover, we prove that the convergence to Nash equilibria is not guaranteed in some of the not yet analyzed cases.

  47. Bin Fu, Angsheng Li and Liyu Zhang. Separating NE from Some Nonuniform Nondeterministic Complexity Classes

    Abstract: We investigate the question whether NE can be separated from the reduction closures of tally sets, sparse sets and NP. We show that (1) there exist sets in NE that are not nondeterministically polynomial-time Turing reducible to tally sets with $n^{o(1)}$ queries, which implies that NE contains languages that are not nondeterministically polynomial-time many-one reducible to tally sets; (2)there exist sets in NE that are not strongly nondeterministically polynomial-time many-one reducible to sparse sets; (3)there exist sets in NE that are not polynomial-time Turing reducible to NP sets via reductions that make $n^k$ queries and use $n^{k'}$ advice bits for any fixed $k,k'>0$. Result (3) extends a previous result by Mocas to nonuniform reductions. We also investigate how different an NE-hard set is from an NP-set. We show that for any NP subset $A$ of a many-one-hard set $H$ for NE, there exists another NP subset $A'$ of $H$ such that $A'\supseteq A$ and $A'-A$ is not of sub-exponential density. For many-one-hard sets for coNE, we strengthen the result such that $A'-A$ is in NP and has exponential density.

  48. Ivona Bezakova, Nayantara Bhatnagar and Dana Randall. On the Diaconis-Gangolli Markov Chain for Sampling Contingency Tables with Cell-Bounded Entries

    Abstract: A contingency table is a non-negative integer matrix satisfying given row and column sums. More generally, a cell-bounded contingency table is a table that additionally satisfies upper bounds on the value of each entry in the matrix. The problem of uniformly sampling and approximately counting contingency tables in the cell-bounded or standard versions has attracted a lot of interest, but efficient solutions are only known when the row and column sums are all large, when there are only a constant number of rows, or when the cell bounds are all zeroes or ones, as this last case is equivalent to computing the permanent of a matrix. One approach to the sampling and counting problems that has received a lot of attention, but so far has resisted analysis in most instances, is the Markov chain of Diaconis and Gangolli. In each step of the chain the entries in a random 2x2 submatrix are updated by adding an integer to two diagonal entries and subtracting the same amount from the other two. For cell-bounded tables, this chain is only known to be rapidly mixing when the cell bounds are all 1 and the row and column sums are regular while it is rapidly mixing for standard tables when the entries are large or there are a constant number of rows. We show here that the chain can require exponential time to mix in the cell-bounded case, even if we restrict to instances for which the state space is connected. Moreover, we show that the chain can be slowly mixing even if we restrict to natural classes of problem instances, including regular instances with cell bounds of either 0 or 1 everywhere, and dense instances where at least a linear number of cells in each row or column have non-zero cell-bounds.

  49. Tomoko Izumi, Taisuke Izumi, Hirotaka Ono and Koichi Wada. Relationship between Approximability and Request Structures in the Minimum Certificate Dispersal Problem

    Abstract: Given a graph $G=(V,E)$ and a set $R \subseteq V\times V$ of requests, we consider to assign a set of edges to each node in $G$ such that for every request $(u, v)$ in $R$ the union of the edge sets assigned to $u$ and $v$ contains a path from $u$ to $v$. {\em The Minimum Certificate Dispersal Problem} (MCD) is defined as one to find the assignment that minimizes the sum of the cardinality of the edge set assigned to each node. This problem has been shown to be NP-hard in general, though it is polynomially solvable for some restricted classes of graphs, such as bidirectional trees. In this paper, we give an advanced investigation about the difficulty of MCD by focusing on the relationship between its (in)approximability and request structures. We first show that MCD with general $R$ has $\Theta (\log n)$ lower and upper bounds on approximation ratio under the assumption $P\neq NP$, where $n$ is the number of nodes in $G$. We then assume $R$ forms a clique structure, called {\em Subset-Full}, which is a natural setting in the context of security systems. Interestingly, under this natural setting, MCD becomes to be $2$-approximable, though it has still no polynomial time approximation algorithm whose factor better than $391/390$ unless $P=NP$. Finally, we show that this approximation ratio can be improved to 3/2 for undirected variant of MCD with Subset-Full.

  50. Giovanni Di Crescenzo. Minimal Assumptions and Round Complexity for Concurrent Zero-Knowledge in the Bare Public-Key Model

    Abstract: Zero-knowledge proofs are of great interest for both their importance in computational complexity and their applications to cryptographic protocols. One major challenge in their design is preserving their properties under advanced attack types, such as concurrent attacks, which can be run in practical settings like the Internet. It has been proved that achieving concurrent security for (black-box-simulation) zero-knowledge protocols in standard models requires a non-constant number of rounds, thus severely limiting efficiency. As a result, a few models with additional setup or network assumptions have been introduced to present constant-round concurrently-secure zero-knowledge protocols for all languages in NP. Under the (minimal) assumption of the existence of one-way functions, we show that every language in NP has 4-message argument systems in the bare public key (BPK) model of [CGGM-Stoc00], which are sound (i.e., a cheating prover cannot prove that x is not in L) and (black-box) zero-knowledge (i.e., a cheating verifier does not obtain any additional information other than x is in L) even in the presence of concurrent attacks (i.e., even if the cheating prover or verifier are allowed to arbitrarily interleave several executions of the same protocol). This improves over the previous best result [DV-Icalp05], which obtained such a protocol using a stronger assumption (the existence of one-way permutations) or a higher round complexity (5 messages). We also show how to directly obtain an efficient implementation of our protocol based on the strong RSA assumption.

  51. Binay Bhattacharya, Yuzhuang Hu and Qiaosheng Shi. Approximation Algorithms for a Network Design Problem

    Abstract: A downwards monotone function f: 2^V -> {0,1} has the property that 1) f(V)=0; 2) f(A)>=f(B), if and only if A is a subset of B. A class of network design problems, including the k-path/tree/cycle covering problems and some location-routing problems, can be modeled by downwards monotone functions. Goemans et al. gave a simple and fast 2-approximation algorithm for these problems. In this paper we consider a network design problem (called the p-constrained path/tree/cycle covering problems) obtained by introducing an additional constraint to these problems. Under this constraint we require that the number of connected components in the optimal solution should be no more than p for some integer p. The p-constrained path/tree/cycle covering problems cannot be modeled by downwards monotone functions. In this paper, we present a different analysis for the performance guarantee of the algorithm by Goemans et al. As a result of the analysis, we are able to tackle the p-constrained path/tree/cycle covering problems, and show the performance bound of 2 for the p-constrained tree/cycle covering problems and the performance bound of 4 for the p-constrained path covering problem. We assumed that for the p-constrained path/cycle covering problems the graph G satisfies the triangle inequality property.