Organizers
BUET Publisher Journal Special Issues Sponsors Supported by IEICE Technical Committee on Theoretical Foundations of Computing (COMP) Special Interest Group for ALgorithms (SIGAL) of the Information Processing Society of Japan (IPSJ) News 11, Nov 2014 26, Sep 2014 16, Sep 2014 16, May 2014 17, Mar 2014 08, Mar 2014 08, Mar 2014 20, Feb 2014 20, Feb 2014

WALCOM 2015 Accepted Papers with AbstractsAn Improved Algorithm for Parameterized Edge Dominating Set Problem
Abstract: An edge dominating set of a graph G = (V, E) is a subset M of edges such that each edge in EM is incident to at least one edge in M. In this paper, we consider the parameterized edge dominating set problem which asks us to test whether a given graph has an edge dominating set with size bounded from above by an integer k or not, and we design an O^*(2.2351^k)time and polynomialspace algorithm. This is an improvement over the previous best time bound of O^*(2.3147^k). We also show that a related problem: the parameterized weighted edge dominating set problem can be solved in O^*(2.2351^k) time and polynomial space.
StraightPath Queries in Trajectory Data
Abstract: Inspired by sports analysis, we study data structures for storing a trajectory representing the movement of a player during a game,
such that the following queries can be answered: Given two positions $s$ and~$t$, report all subtrajectories in which the player moved in a more or less straight line from $s$~to~$t$. We consider two measures of straightness, namely \emph{dilation} and \emph{directedness}, and present efficient construction algorithms for our data structures, and analyze their performance. %We give efficient algorithms to construct our data structures, we analyze their performance from a theoretical point of view, and we compare their performance experimentally. We also present an $O(n^{1.5+\eps})$ algorithm for the following simplification problem: given a trajectory $\tr$ and a threshold~$\tau$, find a simplification of~$\tr$ with a minimum number of vertices such that each edge in the simplification replaces a subtrajectory whose length is at most $\tau$ times the length of the edge. This significantly improves the fastest known algorithm for the problem. The directed ring loading with penalty cost
Abstract: We study the directed ring loading problem with penalty cost, which is to select some of given multicast requests with different demands and embed them in a directed ring, such that the sum of the maximum congestion of the links on the ring and the total penalty cost of the unselected multicast requests is minimized. We prove that this problem is $NP$hard even if the demand is divisible, and design a 1.58approximation algorithm for the demand divisible case and a 3approximation algorithm for the demand indivisible case. As a consequence, for any $\varepsilon>0$, we present a ($1.58+\varepsilon$)approximation algorithm for the case where
every multicast request contains exactly one sink. On Triangle Cover Contact Graphs [Short Paper]
Abstract: Let $S=\{p_1,p_2,\ldots,p_n\}$ be a set of pairwise disjoint geometric objects of some type and $C=\{c_1,c_2,\ldots,c_n\}$ be a set of closed objects of some type with the property that each element in $C$ covers exactly one element in $S$ and any two elements in $C$ can intersect only on their boundaries. We call an element in $S$ a \textit{seed} and an element in $C$ a \textit{cover}. A \textit{cover contact graph ($CCG$)} consists of a set of vertices and a set of edges where each of the vertex corresponds to each of the covers and each edge corresponds to a connection between two covers if they touch at their boundaries. The problem of deciding whether a resulting $CCG$ is 1 or 2connected has already been solved but the problem of deciding whether a resulting $CCG$ is $k$connected for $k > 2$ is still unsolved where each cover element is a disk or a triangle. A \textit{triangle cover contact graph ($TCCG$)} is a cover contact graph whose cover elements are triangles. In this paper, we give algorithms to construct a 3connected $TCCG$ and 4connected $TCCG$ for a given set of seeds. Furthermore we also present an algorithm to show that a given outerplanar graph has a realization as a $TCCG$ on a given set of collinear seeds. Note that only trees and cycles are known to be realizable as $CCG$.
Dichotomy Theorems for Homomorphism Polynomials of Graph Classes
Abstract: In this paper, we will show dichotomy theorems for the computation of polynomials corresponding to evaluation of graph homomorphisms in Valiant's model. We are given a fixed graph $H$ and want to find all graphs, from some graph class, homomorphic to this $H$. These graphs will be encoded by a family of polynomials.
We give dichotomies for the polynomials for cycles, cliques, trees, outerplanar graphs, planar graphs and graphs of bounded genus. The impact of communication patterns on distributed locally selfadjusting binary search trees
Abstract: This paper introduces the problem of communication pattern adaption for a distributed selfadjusting binary search tree. We propose a simple local algorithm, which is closely related to the nearly thirtyyearold idea of splay trees and evaluate its adaption performance in the distributed scenario if different communication patterns are provided.
To do so, the process of selfadjustment is modeled similarly to a basic network creation game, in which the nodes want to communicate with only a certain subset of all nodes. We show that, in general, the game (i.e., the process of local adjustments) does not converge, and convergence is related to certain structures of the communication interests, which we call conflicts. We classify conflicts and show that for two communication scenarios in which convergence is guaranteed, the selfadjusting tree performs well. Furthermore, we investigate the different classes of conflicts separately and show that, for a certain class of conflicts, the performance of the tree network is asymptotically as good as the performance for converging instances. However, for the other conflict classes, a distributed selfadjusting binary search tree adapts poorly. A Practical Succinct Data Structure for TreeLike Graphs
Abstract: We present a new succinct data structure for graphs that are ``treelike,'' in the sense that the number of ``additional'' edges (w.r.t. a spanning tree) is not too high. Our algorithmic idea is to represent a BFSspanning tree of the graph with a succinct data structure for trees, and enhance it with additional information that accounts for the nontree edges. In practical tests, our data structure performs well for graphs containing up to 10% of nontree edges, reducing the space of a pointerbased representation by a factor of roughly 20, while increasing the worstcase running times for the operations by roughly the same factor.
Simultaneous Drawing of Planar Graphs with RightAngle Crossings and Few Bends
Abstract: Given two planar graphs that are defined on the same set of vertices, a RAC simultaneous drawing is one in which each graph is drawn planar, there are no edge overlaps and the crossings between the two graphs form right angles. The geometric version restricts the problem to straightline drawings. It is known, however, that there exists a wheel and a matching which do not admit a geometric RAC simultaneous drawing.
In order to enlarge the class of graphs that admit RAC simultaneous drawings, we allow bends in the resulting drawings. We prove that two planar graphs always admit a RAC simultaneous drawing with six bends per edge each, in quadratic area. For more restricted classes of planar graphs (i.e., matchings, paths, cycles, outerplanar graphs and subhamiltonian graphs), we manage to significantly reduce the required number of bends per edge, while keeping the area quadratic. EdgeColorings of Weighted Graphs
Abstract: Let G be a graph with a positive integer weight ω(v) for each vertex v. One wishes to assign each edge e a positive integer f(e) as a color
so that ω(v)≦ f(e)  f(e′) for any vertex v and any two edges e and e′ incident to v. Such an assignment f is called an ωedgecoloring of G, and the maximum integer assigned to edges is called the span of f. The ωchromatic index of G is the minimum span over all ωedgecolorings of G. In the paper, we present three efficient algorithms to nd an ωedgecoloring of a given graph. One of them nds an ωedgecoloring with span smaller than twice the ωchromatic index. We also obtain several upper bounds and lower bounds on the !chromatic index. Forming Plurality at Minimum Cost
Abstract: In this paper, we are concerned with a kind of spatial equilibria, the plurality points, in twodimensional Euclidean space. Given a set of voters, each of which corresponds to a point, a plurality point is defined as a point closer to at least as many voters as any other point in the space. We generalize the definition by appending weights on the voters, and define the plurality point as a point $\vartriangle$ satisfying that the sum of weights of the voters closer to $\vartriangle$ is no less than that of the voters closer to any other point in the space. To remedy the issue of the nonexistence of plurality points, we investigate the problem of eliminating some voters with minimum ``cost'' so that there is a plurality point with respect to the remaining voters. We show that the problem is NPhard. Moreover, if all voters' weights are restricted to be equal, we show that the problem can be solved in $O(n^5\log n)$ time, where $n$ is the number of voters.
Folding a Paper Strip to Minimize Thickness
Abstract: In this paper, we study how to fold a specified origami crease pattern in order to minimize the impact of paper thickness. Specifically, origami designs are often expressed by a mountainvalley pattern (plane graph of creases with relative fold orientations), but in general this specification is consistent with exponentially many possible folded states. We analyze the complexity of finding the best consistent folded state according to two metrics: minimizing the total number of layers in the folded state (so that a “flat folding” is indeed close to flat), and minimizing the total amount of paper required to execute the folding (where “thicker” creases consume more paper). We prove both problems strongly NPcomplete even for 1D folding. On the other hand, we prove both problems fixedparameter tractable in 1D with respect to the number of layers.
On Bar (1, j)Visibility Graphs
Abstract: A graph is called a bar (1,j)visibility graph if its vertices can be represented as horizontal vertexsegments (bars) and each edge as a vertical edgesegment connecting the bars of the end vertices such that each edgesegment intersects at most one other bar and each bar is intersected by at most j edgesegments. Bar (1,j)visibility refines bar 1visibility in which there is no bound on the number of intersections of bars. We construct gadgets which show structural properties of bar (1,j)visibility graphs, study bounds on the maximal number of edges and show that there is an infinite hierarchy of bar (1,j)visibility graphs. Finally, we prove that it is NPcomplete to test whether a graph is bar (1, infinity)visible.
An Efficient Silent SelfStabilizing Algorithm for 1Maximal Matching in Anonymous Networks
Abstract: We propose a new selfstabilizing 1maximal matching algorithm which is silent and works for any anonymous networks without a cycle of a length of a multiple of 3 under a central unfair daemon. Let n and e be the numbers of nodes and edges in a graph, respectively. The time complexity of the proposed algorithm is O(e) moves. Therefore, the complexity is O(n) moves for trees or rings whose length is not a multiple of 3. That is a significant improvement from the best existing results of O(n^4) moves for the same problem setting.
Common Unfolding of Regular Tetrahedron and JohnsonZalgaller Solid
Abstract: Common unfolding of a regular tetrahedron and a JohnsonZalgaller solid is investigated. More precisely, we investigate the sets of all edge unfoldings of JohnsonZalgaller solids. Among 92 JohnsonZalgaller solids, some of edge unfolding of J17 and J84 admit to fold into a regular tetrahedron. On the other hand, there are no edge unfolding of the other JohnsonZalgaller solids that admit to fold into a regular tetrahedron.
Dynamic Online Multiselection in Internal and External Memory
Abstract: We consider the dynamic version of the \emph{online multiselection} problem for internal and external memory, in which~$q$ selection queries are requested on an unsorted array of $N$~elements. Our internal memory result is $1$competitive with the offline result of Kaligosi\etal [ICALP 2005].
In particular, we extend the results of Barbary\etal [ESA 2013] by supporting arbitrary \emph{insertions} and \emph{deletions} while supporting online \emph{select} and \emph{search} queries on the array. Assuming that the insertion of an element is immediately preceded by a search for that element, we show that our dynamic online algorithm performs an optimal number of comparisons, up to lower order terms and an additive~$O(N)$ term. For the external memory model, we describe the first online multiselection algorithm that is $O(1)$competitive. This result improves upon the work of Sibeyn [Journal of Algorithms 2006] when $q > m$, where $m$ is the number of blocks that can be stored in main memory. We also extend it to support searches, insertions, and deletions of elements efficiently. Logspace and FPT Algorithms for Graph Isomorphism for Subclasses of Bounded Treewidth Graphs [Short Paper]
Abstract: The graph isomorphism problem (GI) is to decide whether two graphs are isomorphic.
This problem has considerable importance in complexity theory due to its unresolved complexity status. We give a deterministic logspace algorithm for the graph isomorphism problem for graphs with bounded treedepth. We also show that the graph isomorphism problem is fixed parameter tractable for a parameterized graph class where the graph parameter is the length of the longest cycle. Threshold Circuits for Global Patterns in 2Dimensional Maps
Abstract: In this paper, we consider a biologicallyinspired Boolean function, called PnD, which models a task for detecting specific global spatial arrangements of local visual patterns on a 2dimensional map. We prove that PnD is computable by a threshold circuit of size
$O(\sqrt{n}\log n)$, which is improvement on the previous upper bound $O(n)$. We also show that the size of our circuit is almost optimal up to logarithmic factor: we show that any threshold circuit computing PnD needs size $\Omega(\sqrt{n}/\log n)$. Bounds on ColorSpanning Set Unit Covering
Abstract: In this paper, we consider a new problem of finding bounds on unit covering in colorspanning set model:
Given a set of $n$ points in $d$dimensional plane colored with $m$ colors, \emph{MinCSBC} problem is to select $m$ points of different colors minimizing the minimum number of unit balls needed to cover them. Similarly, \emph{MaxCSBC} problem is to choose one point of each color to maximize the minimum number of needed unit balls. We show that MinCSBC is NPhard and hard to approximate within any constant factor either even in one dimension. For $d=1$ we propose an $\ln(m)$approximation algorithm and also, we present a constantfactor approximation algorithm for fixed $f$ where $f$ is the maximum frequency of the colors. For MaxCSBC problem, we first prove the NPhardness. Then, we present an approximation algorithm within a factor $1/2$ in onedimensional case. Faulttolerant Gathering of Asynchronous, Oblivious Mobile Robots Under Oneaxis Agreement
Abstract: In this paper, we have studied one of the fundamental coordination problem for multi robot system, namely {\it gathering}, for $n \ge 2$ asynchronous, oblivious mobile robots in the presence of $f < n$ faulty robots. Earlier works have reported that, in general, to solve gathering problem for asynchronous robots, many assumptions are required, like multiplicity detection or total agreement in coordinate axis or constant amount of memory bits. However, in this paper we have proved that gathering of asynchronous robots is possible with less number of such assumptions and even in the presence of any number of faulty robots. In our case, the robots only agree on the direction and orientation of any one axis.
Superset Generation on Decision Diagrams [Short Paper]
Abstract: Generating all supersets from a given set family is important, because it is closely related to identifying causeeffect relationship.
This paper presents an efficient method for superset generation by using the compressed data structures BDDs and ZDDs. We analyze the size of a BDD that represents all supersets. As a byproduct, we obtain a nontrivial upper bound for the size of a BDD that represents a monotone Boolean function in a fixed variable ordering. Furthermore, we apply our superset generation method to hitting set generation. Simultaneous TimeSpace Upper Bounds for RedBlue Path Problem in Planar DAGs
Abstract: In this paper, we consider the {\RB} problem, which states that given a graph $G$ whose edges are colored either red or blue and two fixed vertices $s$ and $t$ in $G$, is there a path from $s$ to $t$ in $G$ that alternates between red and blue edges. The {\RB} problem in planar DAGs is {\NL}complete. We exhibit a polynomial time and $O(\sspace)$ space algorithm (for any $\epsilon >0$) for the {\RB} problem in planar DAG.
We also consider a natural relaxation of {\RB} problem, denoted as {\EB} problem. The {\EB} problem in DAGs is known to be {\NL}complete. We provide a polynomial time and $O(\sspace)$ space (for any $\epsilon >0$) bound for {\EB} problem in planar DAGs. An Almost Optimal Algorithm for Voronoi Diagrams of NonDisjoint Line Segments
Abstract: This paper presents an almost optimal algorithm that computes the Voronoi diagram of a set $S$ of $n$ line segments that may intersect or cross each other. If there are $k$ intersections among the input segments in $S$, our algorithm takes $O(n \alpha(n) \log n + k)$ time, where $\alpha(\cdot)$ denotes the functional inverse of the Ackermann function. The best known running time prior to this work was $O((n + k) \log n)$. Since the lower bound of the problem is shown to be $\Omega(n \log n + k)$ in the worst case, our algorithm is worstcase optimal for $k = \Omega(n \alpha(n) \log n)$, and is only a factor of $\alpha(n)$ away from the lower bound. For the purpose, we also present an improved algorithm that computes the medial axis or the Voronoi diagram of a polygon with holes.
Approximate Distance Oracle in $O(n^2)$ Time and $O(n)$ Space for Chordal Graphs
Abstract: We preprocess a given unweighted chordal graph $G$ on $n$ vertices in $O(n^2)$ time to build a data structure of $O(n)$ size such that any subsequent distance query can be answered in constant time with a bounded constant factor error. In particular, for each pair of vertices $u_i,u_j\in V(G), 1 \leq i,j \leq n$, we take constant time to output a distance value $d_{ij} \leq 2d_G(u_i,u_j)+8$ using our data structure, where $d_G$ is the distance between $u_i$ and $u_j$ in $G$. In contrast, for the closely related APSP problem on
chordal graphs, the current best algorithm runs in $O(n^{2.376})$ time. Our improvement comes from a relationship that we discover between the graph distance and minimum hitting sets of cliques on certain paths in a clique tree associated with a chordal graph. We design an efficient data structure which additively approximates (error of +3) these minimum hitting sets of cliques for all the paths in the clique tree. This data structure is then integrated with an efficient data structure which answers LCA queries in rooted trees to yield our distance oracle for the given chordal graph. Compact encodings and indexes for the nearest larger neighbor problem
Abstract: Given a ddimensional array, for any integer d > 0, the nearest larger neighbor (NLN) query returns the position of the element which is closest, in L_1 distance, to the query position, and is larger than the element at the query position. We consider a data structure version of this problem, where we need to preprocess a given sequence of elements to construct a data structure that can answer NLN queries efficiently.
We also consider the version when only the nearest larger right neighbor (NLRN) is sought, in one dimension. For this problem, for an array of length n, we obtain an index that takes O((n/c) log c) bits, and supports NLRN queries in O(c) time, for any any parameter c, where $1 \le c \le n$, improving the earlier result of Jayapaul et al. [IWOCA, 2014]. In the twodimensional case, for an $n \times n$ array $A$, we give a $O(n^2)$bit (optimal) encoding that supports NLN queries (although, not efficiently). When $A$ is a binary matrix, we describe an $O(n^2)$bit encoding that supports NLN queries in O(1) time, and also an index of size O(n^2/c) bits that supports NLN queries in O(c) time, for any parameter c, where $1 \le c \le n$. Competitive Analysis for MultiObjective Online Algorithms
Abstract: So far, the concept of competitive analysis for online problems is in general applied to singleobjective online problems. However, many online problems can be extended to multiobjective online problems in a natural way, but a uniform theory for the analysis of these problems is not provided in the literature. We expand the concept of competitive analysis to multiobjective online problems and achieve a consistent framework for the analysis of multiobjective online problems. Furthermore, we analyze the multiobjective time series search problem and present deterministic algorithms with best possible competitive ratios.
Fast algorithms for constrained graph density problems
Abstract: We consider the question of finding communities in large social networks. In literature and practice, "communities" refer to a wellconnected subgraph of the entire network. For instance, the notion of graph density has been considered as a reasonable measure of a community. Researchers have also looked at the minimum degree of a subgraph as a measure of the connectedness of the community.
Typically, a community is meaningful in the context of a social network if it is of somewhat significant size. Thus, earlier work has considered the densest graph problem subject to various comatroid constraints. Most of these algorithms utilize an exact dense subgraph procedure as a subroutine; such a subroutine involves computing maximum flows or solving 'lp's. Consequently, they are rather inefficient when considered for massive graphs. For massive graphs, we are constrained to run in nearlinear time, while producing subgraphs that provide reasonable approximations to the optimal solutions. Our current work presents efficient greedy algorithms for the problem of graph density subject to a general class of constraints called comatroid constraints. We also consider the minimum degree objective: we obtain efficient algorithms for this objective subject to both comatroid and dependency constraints. Our algorithms heavily utilize the core decomposition of a graph. Enumerating Eulerian Trails via Hamiltonian Path Enumeration
Abstract: Given an undirected graph G, we consider enumerating all Eulerian trails, that is, trails containing all edges in G. We consider achieving it with the enumeration of Hamiltonian paths with the zerosuppressed decision diagram (ZDD), a data structure that can efficiently store a set of paths. First we compute the line graph L(G), the graph representing adjacency of the edges in G. Because every Eulerian trail in G corresponds to a Hamiltonian path in L(G) but the converse is not true, we also formulated the condition when a Hamiltonian path in L(G) corresponds to an Eulerian trail in G. Then we enumerate all Hamiltonian paths in L(G) satisfying the condition with the help of ZDD.
PTAS's for Some Metric pSource Communication Spanning Tree Problems
Abstract: In this work we consider some NPhard cases of the metric psource communication spanning tree problem (metric pOCT).
Given an undirected complete graph G=(V,E) with nonnegative length w(e) associated to each edge satisfying the triangular inequality, a subset S of V with p vertices and nonnegative routing requirements r(u,v) between all pairs of nodes u in S and v in V, the metric pOCT's objective is to find a spanning tree T of G, that minimizes the sum of routing costs over T of all pairs of vertices, where the routing cost over T between vertices u in S and v in V is r(u,v)d(T, u,v) being d(H,x,y) the minimum distance between nodes x and y in a subgraph H of G. This problem is a particular case of the optimum communication spanning tree problem (OCT). We prove a general result which allows us to derive polynomial approximation schemes for some NPhard cases of the metric pOCT improving the existing ratios for these problems. Nonrepetitive strings over alphabet lists
Abstract: A word is nonrepetitive if it does not contain a subword of the form vv. Given a list of alphabets L = L1, L2, . . . , Ln, we investigate the question of generating nonrepetitive words w = w1w2 . . . wn, such that the symbol wi is a letter in the alphabet Li. This problem has been studied by several authors (e.g., [GKM10], [Sha09]), and it is a natural extension of the original problem posed and solved by A. Thue. While we do not solve the problem in its full generality, we show that such strings exist over many classes of lists. We also suggest techniques for tackling the problem, ranging from online algorithms, to combinatorics over 01 matrices, and to proof complexity. Finally, we show some properties of the extension of the problem to abelian squares. 