WALCOM: Algorithms and Computation

In recent years, there has been an explosion of interest in

succinct

data structures, which store the given data in compact or compressed formats and answer queries on the data rapidly while it is still in its compressed format. Our focus in this talk is to introduce

encoding

data structures. Encoding data structures consider the data together with the queries and aim to store only as much information about the data as is needed to store the queries. Once this is done, the original data can be deleted. In many cases, one can obtain space-efficient encoding data structures even when the original data is incompressible.

We consider the question of finding communities in

large

social networks. In literature and practice, “communities” refer to a

well-connected

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

co-matroid constraints

. Most of these algorithms utilize an exact dense subgraph procedure as a subroutine; such a subroutine involves computing maximum flows or solving LPs. Consequently, they are rather inefficient when considered for massive graphs. For massive graphs, we are constrained to run in near-linear 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 an even more general class of constraints called

upward-monotone

constraints (these subsume co-matroid constraints). This generalizes and extends earlier work significantly. For instance, we are thereby able to present near-linear time 3-factor approximation algorithms for density subject to co-matroid constraints; we are also able to obtain 2-factor LP-based algorithms for density subject to 2 co-matroid constraints.

Our algorithms heavily utilize the

core decomposition

of a graph.

We study the directed ring loading problem with penalty cost, which is to select some of given multicast requests represented by hyperedges with different demands and embed them in a directed ring, such that the sum of the maximum congestion among all 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 then design a 1.582-approximation algorithm for the demand divisible case and a 3-approximation algorithm for the demand indivisible case, respectively. As a consequence, for any

ε

 > 0, we present a (1.582 + 

ε

)-approximation algorithm for the case where every multicast request contains exactly one sink.

Let

G

be a graph with a positive integer weight

ω

(

v

) for each vertex

v

. One wishes to assign each edge

e

of

G

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

ω

-edge-coloring 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

ω

-edge-colorings of

G

. In the paper, we present various upper and lower bounds on the

ω

-chromatic index, and obtain three efficient algorithms to find an

ω

-edge-coloring of a given graph. One of them finds an

ω

-edge-coloring with span smaller than twice the

ω

-chromatic index.

In this paper, we consider two new variants of the unit covering problem in color-spanning set model: Given a set of

n

points in

d

-dimensional plane colored with

m

colors, the

MinCSBC

problem is to select

m

points of different colors minimizing the minimum number of unit balls needed to cover them. Similarly, the

MaxCSBC

problem is to choose one point of each color to maximize the minimum number of needed unit balls. We show that MinCSBC is NP-hard and hard to approximate within any constant factor even in one dimension. For

d

 = 1, however, we propose an ln (

m

)-approximation algorithm and present a constant-factor approximation algorithm for fixed

f

, where

f

is the maximum frequency of the colors. For the MaxCSBC problem, we first prove its NP-hardness. Then we present an approximation algorithm with a factor of 1/2 in one-dimensional case.

Given a

d

-dimensional array, for any integer

d

 > 0, the

nearest larger value

(

NLV

) 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 the problem of preprocessing a given array, to construct a data structure that can answer

NLV

queries efficiently. In the 2-D case, given an

n

×

n

array

A

, we give an asymptotically optimal

O

(

n

2

)-bit encoding that answers

NLV

queries in

O

(1) time. When

A

is a binary array, we describe a simpler

O

(

n

2

)-bit encoding that also supports

NLV

queries in

O

(1) time. Using this, we obtain an index of size

O

(

n

2

/

c

) bits that supports

NLV

queries in

O

(

c

) time, for any parameter

c

, where 1 ≤ 

c

 ≤ 

n

, matching the lower bound. For the 1-D case we consider the

nearest larger right value

(

NLRV

) problem where the nearest larger value to the right is sought. For an array of length

n

, we obtain an index that takes

O

((

n

/

c

) log

c

) bits, and supports

NLRV

queries in

O

(

c

) time, for any any parameter

c

, where 1 ≤ 

c

 ≤ 

n

, improving the earlier results of Fischer et al. and Jayapaul et al.

We present a new succinct data structure for graphs that are “tree-like,” 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 BFS-spanning tree of the graph with a succinct data structure for trees, and enhance it with additional information that accounts for the non-tree edges. In practical tests, our data structure performs well for graphs containing up to 10% of non-tree edges, reducing the space of a pointer-based representation by a factor of ≈20, while increasing the worst-case running times for the operations by roughly the same factor.

In this paper, we are concerned with a kind of spatial equilibria, the plurality points, in two-dimensional 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 non-existence 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 NP-hard. 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.

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

 ∈ 

V

(

G

), 1 ≤ 

i

,

j

 ≤ 

n

, we take constant time to output a distance value

d

ij

 ≤ 2

d

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.373

) 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.

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 sub-trajectories in which the player moved in a more or less straight line from

s

to

t

. We consider two measures of straightness, namely

dilation

and

direction deviation

, and present efficient construction algorithms for our data structures, and analyze their performance.

We also present an

O

(

n

1.5 + 

ε

) algorithm that, given a trajectory

P

and a threshold

τ

, finds a simplification of

P

with a minimum number of vertices such that each edge in the simplification replaces a sub-trajectory of length at most

τ

times the length of the edge. This significantly improves the fastest known algorithm for the problem.

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 mountain-valley 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 NP-complete even for 1D folding. On the other hand, we prove the first problem fixed-parameter tractable in 1D with respect to the number of layers.

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

α

(

n

) log

n

 + 

k

) time, where

α

(·) 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 Ω(

n

log

n

 + 

k

) in the worst case, our algorithm is worst-case optimal for

k

 = Ω(

n

α

(

n

) log

n

), and is only a factor of

α

(

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.

In this work we consider some NP-hard cases of the metric

p

-source communication spanning tree problem (metric

p

-

OCT

). Given an undirected complete graph

G

 = (

V

,

E

) with non-negative length

ω

(

e

) associated to each edge

e

 ∈ 

E

satisfying the triangular inequality, a set

S

 ⊆ 

V

of

p

vertices and non-negative routing requirements

ψ

(

u

,

v

) between all pairs of nodes

u

 ∈ 

S

and

v

 ∈ 

V

, the metric

p

-

OCT

’s objective is to find a spanning tree

T

of

G

, that minimizes: ∑ 

u

 ∈ 

S

 ∑ 

v

 ∈ 

V

ψ

(

u

,

v

)

d

(

T

,

u

,

v

), where

d

(

H

,

x

,

y

) is the minimum distance between nodes

x

and

y

in a graph

H

 ⊆ 

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 NP-hard cases of the metric

p

-

OCT

improving the existing ratios for these problems.

In this paper, we have studied one of the fundamental coordination problems for multi robot system, namely

gathering

, for

n

 ≥ 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.

Given an undirected graph

G

, we consider enumerating all Eulerian trails, that is, walks containing each of the edges in

G

just once. We consider achieving it with the enumeration of Hamiltonian paths with the

zero-suppressed decision diagram

(ZDD), a data structure that can efficiently store a family of sets satisfying given conditions. First we compute the

line graph

L

(

G

), the graph representing adjacency of the edges in

G

. We also formulated the condition when a Hamiltonian path in

L

(

G

) corresponds to an Eulerian trail in

G

because every trail in

G

corresponds to a path in

L

(

G

) but the converse is not true. Then we enumerate all Hamiltonian paths in

L

(

G

) satisfying the condition with ZDD by representing them as their sets of edges.

This paper introduces the problem of communication pattern adaption for a distributed self-adjusting binary search tree. We propose a simple local algorithm that is closely related to the nearly thirty-year-old 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 self-adjustment 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 self-adjusting 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 self-adjusting binary search tree adapts poorly.

We propose a new self-stabilizing 1-maximal 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.

We consider the dynamic version of the

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 Kaligosiet al.[ICALP 2005]. In particular, we extend the results of Barbaryet al.[ESA 2013] by supporting arbitrary

insertions

and

deletions

while supporting online

select

and

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.

So far, the concept of competitive analysis for online problems is in general applied to single-objective online problems. However, many online problems can be extended to multi-objective 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 multi-objective online problems and achieve a consistent framework for the analysis of multi-objective online problems. Furthermore, we analyze the multi-objective time series search problem and present deterministic algorithms with best possible competitive ratios.

Given two planar graphs that are defined on the same set of vertices, a

RAC simultaneous drawing

is a drawing of the two graphs where each graph is drawn planar, no two edges overlap, and edges of one graph can cross edges of the other graph only at right angles. In the geometric version of the problem, vertices are drawn as points and edges as straight-line segments. It is known, however, that even pairs of very simple classes of planar graphs (such as wheels and matchings) do not always admit a geometric RAC simultaneous drawing.

In order to enlarge the class of graphs that admit RAC simultaneous drawings, we allow edges to have bends. We prove that any pair of planar graphs admits a RAC simultaneous drawing with at most six bends per edge. For more restricted classes of planar graphs (e.g., matchings, paths, cycles, outerplanar graphs, and subhamiltonian graphs), we significantly reduce the required number of bends per edge. All our drawings use quadratic area.

An edge dominating set of a graph

G

 = (

V

,

E

) is a subset

M

 ⊆ 

E

of edges such that each edge in

E

 ∖ 

M

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 polynomial-space 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.

A graph is called a bar (1,

j

)-visibility graph if its vertices can be represented as horizontal vertex-segments (bars) and each edge as a vertical edge-segment connecting the bars of the end vertices such that each edge-segment intersects at most one other bar and each bar is intersected by at most

j

edge-segments. Bar (1,

j

)-visibility refines bar 1-visibility 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

NP

-complete to test whether a graph is bar (1, ∞ )-visible.

In this paper, we consider the

RedBluePath

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

RedBluePath

problem in planar DAGs is

NL

-complete. We exhibit a polynomial time and

$O(n^{\frac{1}{2}+\epsilon})$

space algorithm (for any

ε

 > 0) for the

RedBluePath

problem in planar DAG. We also consider a natural relaxation of

RedBluePath

problem, denoted as

EvenPath

problem. The

EvenPath

problem in DAGs is known to be

NL

-complete. We provide a polynomial time and

$O(n^{\frac{1}{2}+\epsilon})$

space (for any

ε

 > 0) bound for

EvenPath

problem in planar DAGs.

A word is non-repetitive if it does not contain a subword of the form

vv

. Given a list of alphabets

L

 = 

L

1

,

L

2

,…,

L

n

, we investigate the question of generating non-repetitive words

w

 = 

w

1

w

2

…

w

n

, such that the symbol

w

i

is a letter in the alphabet

L

i

. 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 0-1 matrices, and to proof complexity. Finally, we show some properties of the extension of the problem to abelian squares.

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.

Common unfolding of a regular tetrahedron and a Johnson-Zalgaller solid is investigated. More precisely, we investigate the sets of all edge unfoldings of Johnson-Zalgaller solids. Among 92 Johnson-Zalgaller 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 Johnson-Zalgaller solids that admit to fold into a regular tetrahedron.

In this paper, we consider a biologically-inspired Boolean function, called

$P^n_D$

, which models a task for detecting specific global spatial arrangements of local visual patterns on a 2-dimensional map. We prove that

$P^n_D$

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

$P^n_D$

needs size

$\Omega(\sqrt{n}/\log n)$

.

Generating all supersets from a given set family is important, because it is closely related to identifying cause-effect relationship. This paper presents an efficient method for superset generation by using the compressed data structures BDDs and ZDDs effectively. We analyze the size of a BDD that represents all supersets. As a by-product, we obtain a non-trivial upper bound for the size of a BDD that represents a monotone Boolean function in a fixed variable ordering.

Let

S

 = {

p

1

,

p

2

,…,

p

n

} be a set of pairwise disjoint geometric objects of some type in a 2

D

plane and let

C

 = {

c

1

,

c

2

,…,

c

n

} be a set of closed objects of some type in the same plane with the property that each element in

C

covers exactly one element in

S

and any two elements in

C

are interior-disjoint. We call an element in

S

a

seed

and an element in

C

a

cover

. A

cover contact graph (CCG)

has a vertex for each element of

C

and an edge between two vertices whenever the corresponding cover elements touch. It is known how to construct, for any given point seed set, a disk or triangle cover whose contact graph is 1- or 2-connected but the problem of deciding whether a

k

-connected

CCG

can be constructed or not for

k

 > 2 is still unsolved. A

triangle cover contact graph (TCCG)

is a cover contact graph whose cover elements are triangles. In this paper, we give an algorithm to construct a 4-connected

TCCG

for a given set of point seeds. We also show that any outerplanar graph has a realization as a

TCCG

on a given set of collinear point seeds. Note that, under this restriction, only trees and cycles are known to be realizable as

CCG

.

We give a deterministic logspace algorithm for the graph isomorphism problem for graphs with bounded tree-depth. We also show that the graph isomorphism problem is fixed parameter tractable for a related parameterized graph class where the graph parameter is the length of the longest cycle.

We identify an error in the analysis of the online algorithm $\textsc{rpp-mult}$ for the bi-objective time series search problem presented in [1]. The strong competitive ratio with respect to $f_2(c) = \frac{1}{k} \sum_{i=1}^k c_i$ of $\textsc{rpp-mult}$ stated in [1, Theorem 3] does not hold due to an error in the proof. In the following, we point out this error. For details about the problem and the terminology, we refer to the original paper.In the course of the proof of [1, Theorem 3], the expression$$\max_{x \in \mathcal{I}_1} \left\{\frac{M_1}{x} + \frac{M_2x}{z^{\star}} \right\}$$is considered (see Equation (9)). Here, the maximum is falsely determined as $x^*= \sqrt{{(M_1z^{\star})}{M_2}}$. In fact, $x^* \notin \mathcal{I}_1$, and, thus, Equation (9) does not hold. The same mistake has been made in Equation (11), i.e., the chosen maximum is not a point in $\mathcal{I}_2$.Note that the proof cannot be modified such that the stated competitive ratio is proven. However, in [2], a best possible algorithm for the bi-objective time series search problem is presented, as outlined below.Hasegawa and Itoh define the online algorithm Balanced Price Policybpp _k for the k-objective time series search problem with respect to an arbitrary monotone continuous function f: ℝk → ℝ, see Algorithm 1.Let $z_k^f = \sup_{\left(x_1,\dots,x_k\right) \in \mathcal{S}_f^k} f\left(\frac{M_1}{x_1},\dots,\frac{M_k}{x_k}\right)$, where$\mathcal{S}_f^k = \left\{ (x_1,\dots,x_k) \in I_1 \times \cdots \times I_k: f\left(\frac{M_1}{x_1},\dots,\frac{M_k}{x_k}\right) = f\left(\frac{x_1}{m_1},\dots,\frac{x_k}{m_k}\right)\right\}$with I _i  = [m _i ,M _i ] for i = 1,…,k.Hasegawa and Itoh prove that, for any integer k ≥ 1 and any monotone continuous function f: ℝk → ℝ, the competitive ratio of $\textsc{bpp}_k$ with respect to f is given by $z_f^k$ and this is the best possible competitive ratio, see [2, Section 4.1].By means of this result, the following theorem gives the best possible competitive ratio with respect to f₂ and k = 2:Theorem 1 (Hasegawa and Itoh, [2, Theorem 6.1]).With respect to the function f₂ for k = 2, the following holds:$z^2_{f_2} = \frac{1}{2}\left\lbrack \sqrt{\left(\frac{1}{2}\left(\frac{M_2}{m_2}-1\right)\right)^2 + \frac{M_1}{m_1}} + \frac{1}{2}\left(\frac{M_2}{m_2}+1\right) \right \rbrack.$References1Tiedemann, M. and Ide, J. and Schöbel, A.: Competitive Analysis for Multi-Objective Online Algorithms. In: Proceedings of the 9th Workshop on Algorithms and Computation (WALCOM). LNCS, vol. 8973, pp. 210–221 (2015)2Hasegawa, S. and Itoh, T.: Optimal Online Algorithms for the Multi-Objective Time Series Search Problem. arXiv:1506.04474v4 [cs.DS] (2015)