Skip to main content
main-content

Über dieses Buch

This book constitutes the thoroughly refereed post-workshop proceedings of the 24th International Workshop on Combinatorial Algorithms, IWOCA 2013, held in Rouen, France, in July 2013. The 33 revised full papers presented together with 10 short papers and 5 invited talks were carefully reviewed and selected from a total of 91 submissions. The papers are organized in topical sections on algorithms on graphs; algorithms on strings; discrete geometry and satisfiability.

Inhaltsverzeichnis

Frontmatter

Invited Talks

Weak Heaps and Friends: Recent Developments

A weak heap is a variant of a binary heap where, for each node, the heap ordering is enforced only for one of its two children. In 1993, Dutton showed that this data structure yields a simple worst-case-efficient sorting algorithm. In this paper we review the refinements proposed to the basic data structure that improve the efficiency even further. Ultimately,

minimum

and

insert

operations are supported in

O

(1) worst-case time and

extract-min

operation in

$O(\lg n)$

worst-case time involving at most

$\lg n + O(1)$

element comparisons. In addition, we look at several applications of weak heaps. This encompasses the creation of a sorting index and the use of a weak heap as a tournament tree leading to a sorting algorithm that is close to optimal in terms of the number of element comparisons performed. By supporting

insert

operation in

O

(1) amortized time, the weak-heap data structure becomes a valuable tool in adaptive sorting leading to an algorithm that is constant-factor optimal with respect to several measures of disorder. Also, a weak heap can be used as an intermediate step in an efficient construction of binary heaps. For graph search and network optimization, a weak-heap variant, which allows some of the nodes to violate the weak-heap ordering, is known to be provably better than a Fibonacci heap.

Stefan Edelkamp, Amr Elmasry, Jyrki Katajainen, Armin Weiß

Efficient Exploration of Anonymous Undirected Graphs

We consider the problem of exploring an anonymous undirected graph using an oblivious robot. The studied exploration strategies are designed so that the next edge in the robot’s walk is chosen using only local information. In this paper, we present some current developments in the area. In particular, we focus on recent work on

equitable strategies

and on the

multi-agent rotor-router

.

Ralf Klasing

Regular Papers

On Maximum Rank Aggregation Problems

The rank aggregation problem consists in finding a consensus ranking on a set of alternatives, based on the preferences of individual voters. These are expressed by permutations, whose distance can be measured in many ways.

In this work we study a collection of distances, including the Kendall tau, Spearman footrule, Spearman rho, Cayley, Hamming, Ulam, and Minkowski distances, and compute the consensus against the maximum, which attempts to minimize the discrimination against any voter.

We provide a general schema from which we can derive the

NP

-hardness of the maximum rank aggregation problems under the aforementioned distances. This reveals a dichotomy for rank aggregation problems under the Spearman footrule and Minkowski distances: the common sum version is solvable in polynomial time whereas the maximum version is

NP

-hard. Moreover, the maximum rank aggregation problems are proved to be 2-approximable under all pseudometrics and fixed-parameter tractable under the Kendall tau, Hamming, and Minkowski distances.

Christian Bachmaier, Franz Josef Brandenburg, Andreas Gleißner, Andreas Hofmeier

Deciding Representability of Sets of Words of Equal Length in Polynomial Time

De Bruijn sequences of order

n

represent

the set

A

n

of all words of length

n

over a given alphabet

A

in the sense that they contain occurrences of each of these words. Recently, the computational problem of representing subsets of

A

n

by

partial words

, which are sequences that may have holes that match each letter of

A

, was considered and shown to be in

$\mathcal{NP}$

. However, membership in

$\mathcal{P}$

remained open. In this paper, we show that deciding if a subset is representable can be done in polynomial time. Our approach is graph theoretical.

Francine Blanchet-Sadri, Sinziana Munteanu

Prefix Table Construction and Conversion

The

prefix table

of a string

x

 = 

x

[1..

n

] is an array

π

 = 

π

[1..

n

] such that

π

[

i

] is the length of the longest substring beginning at

i

that equals a prefix of

x

. In this paper we describe and evaluate algorithms for prefix table construction, some previously proposed, others designed by us. We also describe and evaluate new linear-time algorithms for transformations between

π

and the

border array

.

Widmer Bland, Gregory Kucherov, W. F. Smyth

On the Approximability of Splitting-SAT in 2-CNF Horn Formulas

Splitting a variable in a Boolean formula means to replace an arbitrary set of its occurrences by a new variable. In the minimum splitting SAT problem, we ask for a minimum-size set of variables to be split in order to make the formula satisfiable. This problem is known to be APX-hard, even for 2-CNF formulas. We consider the case of 2-CNF Horn formulas, i.e., 2-CNF formulas without positive 2-clauses, and prove that this problem is APX-hard as well. We also analyze subcases of 2-CNF Horn formulas, where additional clause types are forbidden. While excluding negative 2-clauses admits a polynomial-time algorithm based on network flows, the splitting problem stays APX-hard for formulas consisting of positive 1-clauses and negative 2-clauses only.

Instead of splitting as many variables as possible to make a formula satisfiable, one can also look at the dual problem of finding the maximum number of variables that can be assigned without violating a clause. We also study the approximability of this maximum assignment problem on 2-CNF Horn formulas. While the polynomially solvable subproblems are the same as for the splitting problem, the maximum assignment problem in general Horn formulas is as hard to approximate as the maximum independent set problem.

Hans-Joachim Böckenhauer, Lucia Keller

Boundary-to-Boundary Flows in Planar Graphs

We give an iterative algorithm for finding the maximum flow between a set of sources and sinks that lie on the boundary of a planar graph. Our algorithm uses only

O

(

n

) queries to simple data structures, achieving an

O

(

n

log

n

) running time that we expect to be practical given the use of simple primitives. The only existing algorithm for this problem uses divide and conquer and, in order to achieve an

O

(

n

log

n

) running time, requires the use of the (complicated) linear-time shortest-paths algorithm for planar graphs.

Glencora Borradaile, Anna Harutyunyan

Exact Algorithms for Weak Roman Domination

We consider the

Weak Roman Domination

problem. Given an undirected graph

G

 = (

V

,

E

), the aim is to find a

weak roman domination

function (wrd-function for short) of minimum cost,

i.e.

a function

f

:

V

 → {0,1,2} such that every vertex

v

 ∈ 

V

is

defended

(

i.e.

there exists a neighbor

u

of

v

, possibly

u

 = 

v

, such that

$f(u) \geqslant 1$

) and for every vertex

v

 ∈ 

V

with

f

(

v

) = 0 there exists a neighbor

u

of

v

such that

$f(u) \geqslant 1$

and the function

f

u

 → 

v

defined by:

$$ f_{u \rightarrow v}(x) = \left\{ \begin{array} {l l} 1 ~~~~~~~~~~~~~\!~ \textrm{if~} x = v\\ f(u) - 1 ~~~~\textrm{if~} x = u\\ f(x) ~~~~~~~~~\textrm{if~} x \notin \{u,v\}\\ \end{array} \right. $$

does not contain any undefended vertex. The

cost

of a wrd-function

f

is defined by

cost

(

f

) = ∑ 

v

 ∈ 

V

f

(

v

). The trivial enumeration algorithm runs in time

$\mathcal{O}^*(3^n)$

and polynomial space and is the best one known for the problem so far. We are breaking the trivial enumeration barrier by providing two faster algorithms: we first prove that the problem can be solved in

$\mathcal{O}^*(2^n)$

time needing

exponential space

, and then describe an

$\mathcal{O}^*(2.2279^n)$

algorithm using

polynomial space

. Our results rely on structural properties of a wrd-function, as well as on the best polynomial space algorithm for the

Red-Blue Dominating Set

problem.

Mathieu Chapelle, Manfred Cochefert, Jean-François Couturier, Dieter Kratsch, Mathieu Liedloff, Anthony Perez

Verification Problem of Maximal Points under Uncertainty

The study of algorithms that handle imprecise input data for which precise data can be requested is an interesting area. In the

verification under uncertainty

setting, which is the focus of this paper, an algorithm is also given an assumed set of precise input data. The aim of the algorithm is to update the smallest set of input data such that if the updated input data is the same as the corresponding assumed input data, a solution can be calculated. We study this setting for the maximal point problem in two dimensions. Here there are three types of data, a set of points

P

 = {

p

1

,…,

p

n

}, the uncertainty areas information consisting of

areas of uncertainty

A

i

for each 1 ≤ 

i

 ≤ 

n

, with

p

i

 ∈ 

A

i

, and the set of

P

′ = {

p

1

, . . . ,

p

k

} containing the assumed points, with

p

i

 ∈ 

A

i

. An

update

of an area

A

i

reveals the actual location of

p

i

and

verifies

the assumed location if

p

i

 = 

p

i

. The objective of an algorithm is to compute the smallest set of points with the property that, if the updates of these points verify the assumed data, the set of maximal points among

P

can be computed. We show that the maximal point verification problem is NP-hard, by a reduction from the minimum set cover problem.

George Charalambous, Michael Hoffmann

Incidence Coloring Game and Arboricity of Graphs

An incidence of a graph

G

is a pair (

v

,

e

) where

v

is a vertex of

G

and

e

an edge incident to

v

. Two incidences (

v

,

e

) and (

w

,

f

) are adjacent whenever

v

 = 

w

, or

e

 = 

f

, or

vw

 = 

e

or

f

. The incidence coloring game [S.D. Andres, The incidence game chromatic number, Discrete Appl. Math. 157 (2009), 1980–1987] is a variation of the ordinary coloring game where the two players, Alice and Bob, alternately color the incidences of a graph, using a given number of colors, in such a way that adjacent incidences get distinct colors. If the whole graph is colored then Alice wins the game otherwise Bob wins the game. The incidence game chromatic number

i

g

(

G

) of a graph

G

is the minimum number of colors for which Alice has a winning strategy when playing the incidence coloring game on

G

.

Andres proved that

$i_g(G) \le 2\varDelta(G) + 4k - 2$

for every

k

-degenerate graph

G

. We show in this paper that

$i_g(G) \le \lfloor\frac{3\varDelta(G) - a(G)}{2}\rfloor + 8a(G) - 2$

for every graph

G

, where

a

(

G

) stands for the arboricity of

G

, thus improving the bound given by Andres since

a

(

G

) ≤ 

k

for every

k

-degenerate graph

G

. Since there exists graphs with

$i_g(G) \ge \lceil\frac{3\varDelta(G)}{2}\rceil$

, the multiplicative constant of our bound is best possible.

Clément Charpentier, Éric Sopena

Linear-Time Self-stabilizing Algorithms for Minimal Domination in Graphs

A distributed system is self-stabilizing if, regardless of the initial state, the system is guaranteed to reach a legitimate (correct) state in finite time. In 2007, Turau proposed the first linear-time self-stabilizing algorithm for the minimal dominating set (MDS) problem under an unfair distributed daemon [6]; this algorithm stabilizes in at most 9

n

moves, where

n

is the number of nodes. In 2008, Goddard et al. [2] proposed a 5

n

-move algorithm. In this paper, we present a 4

n

-move algorithm. We also prove that if an MDS-silent algorithm is preferred, then distance-1 knowledge is insufficient, where a self-stabilizing MDS algorithm is MDS-silent if it will not make any move when the starting configuration of the system is already an MDS.

Well Y. Chiu, Chiuyuan Chen

Phase Transition of Random Non-uniform Hypergraphs

Non-uniform hypergraphs appear in several domains of computer science as in the satisfiability problems and in data analysis. We analyze their typical structure before and near the birth of the

complex

component, that is the first connected component with more than one cycle. The model of non-uniform hypergraph studied is a natural generalization of the

multigraph process

defined in the “giant paper” [1]. This paper follows the same general approach based on analytic combinatorics. We study the evolution of hypergraphs as their complexity, defined as the

excess

, increases. Although less natural than the number of edges, this parameter allows a precise description of the structure of hypergraphs. Finally, we compute some statistics of the hypergraphs with a given excess, including the expected number of edges.

Élie de Panafieu

Domino Tatami Covering Is NP-Complete

A covering with dominoes of a rectilinear region is called

tatami

if no four dominoes meet at any point. We describe a reduction from planar

3SAT

to Domino Tatami Covering. As a consequence it is therefore NP-complete to decide whether there is a perfect matching of a graph that meets every 4-cycle, even if the graph is restricted to be an induced subgraph of the grid-graph. The gadgets used in the reduction were discovered with the help of a

SAT

-solver.

Alejandro Erickson, Frank Ruskey

The Complexity of the Identifying Code Problem in Restricted Graph Classes

An identifying code is a subset of vertices of a graph such that each vertex is uniquely determined by its nonempty neighbourhood within the identifying code. We study the associated computational problem

Minimum Identifying Code

, which is known to be

NP

-hard, even when the input graph belongs to a number of specific graph classes such as planar bipartite graphs. Though the problem is approximable within a logarithmic factor, it is known to be hard to approximate within any sub-logarithmic factor. We extend the latter result to the case where the input graph is bipartite, split or co-bipartite. Among other results, we also show that for bipartite graphs of bounded maximum degree (at least 3), it is hard to approximate within some constant factor. We summarize known results in the area, and we compare them to the ones for the related problem

Minimum Dominating Set

. In particular, our work exhibits important graph classes for which

Minimum Dominating Set

is efficiently solvable, but

Minimum Identifying Code

is hard (whereas in all previously studied classes, their complexity is the same). We also introduce a graph class for which the converse holds.

Florent Foucaud

Expanding the Expressive Power of Monadic Second-Order Logic on Restricted Graph Classes

We combine integer linear programming and recent advances in Monadic Second-Order model checking to obtain two new algorithmic meta-theorems for graphs of bounded vertex-cover. The first one shows that the model checking problem for cardMSO

1

, an extension of the well-known Monadic Second-Order logic by the addition of cardinality constraints, can be solved in FPT time parameterized by vertex cover. The second meta-theorem shows that the MSO partitioning problems introduced by Rao can also be solved in FPT time with the same parameter.

The significance of our contribution stems from the fact that these formalisms can describe problems which are W[1]-hard and even NP-hard on graphs of bounded tree-width. Additionally, our algorithms have only elementary dependence on the parameter and formula. We also show that both results are easily extended from vertex cover to neighborhood diversity.

Robert Ganian, Jan Obdržálek

Dynamising Interval Scheduling: The Monotonic Case

We investigate dynamic algorithms for the interval scheduling problem. We focus on the case when the set of intervals is monotonic. This is when no interval properly contains another interval. We provide two data structures for representing the intervals that allow efficient insertion, removal and various query operations. The first dynamic algorithm, based on the data structure called compatibility forest, runs in amortised time

O

(log

2

n

) for insertion and removal and

O

(log

n

) for query. The second dynamic algorithm, based on the data structure called linearised tree, runs in time

O

(log

n

) for insertion, removal and query. We discuss differences and similarities of these two data structures through theoretical and experimental results.

Alexander Gavruskin, Bakhadyr Khoussainov, Mikhail Kokho, Jiamou Liu

Graph Editing to a Fixed Target

For a fixed graph

H

, the

H

-

Minor Edit

problem takes as input a graph

G

and an integer

k

and asks whether

G

can be modified into

H

by a total of at most

k

edge contractions, edge deletions and vertex deletions. Replacing edge contractions by vertex dissolutions yields the

H

-

Topological Minor Edit

problem. For each problem we show polynomial-time solvable and

NP

-complete cases depending on the choice of

H

. Moreover, when

G

is AT-free, chordal or planar, we show that

H

-

Minor Edit

is polynomial-time solvable for all graphs

H

.

Petr A. Golovach, Daniël Paulusma, Iain Stewart

Tight Bound on the Diameter of the Knödel Graph

The Knödel graph

$W_{\varDelta,n}$

is a regular graph of even order and degree

$\varDelta$

where 2

$\leq \varDelta \leq \lfloor{log_2 n}\rfloor$

. Despite being a highly symmetric and widely studied graph, the diameter of

$W_{\varDelta,n}$

is known only for

$n=2^{\varDelta}$

. In this paper we present a tight upper bound on the diameter of the Knödel graph for general case. We show that the presented bound differs from the diameter by at most 2 when

$\varDelta < \alpha \lfloor{\log_2 n}\rfloor$

for some 0 < 

α

 < 1 where

α

 → 1 when

n

 → ∞. The proof is constructive and provides a near optimal diametral path for the Knödel graph

$W_{\varDelta,n}$

.

Hayk Grigoryan, Hovhannes A. Harutyunyan

Structural Properties of Subdivided-Line Graphs

Motivated by self-similar structures of Sierpiński graphs, we newly introduce the subdivided-line graph operation Γ and define the

n

-iterated subdivided-line graph Γ

n

(

G

) of a graph

G

. We then study structural properties of subdivided-line graphs such as edge-disjoint Hamilton cycles, hub sets, connected dominating sets, and completely independent spanning trees which can be applied to problems on interconnection networks. From our results, the maximum number of edge-disjoint Hamilton cycles, the minimum cardinality of a hub set, the minimum cardinality of a connected dominating set, and the maximum number of completely independent spanning trees in Sierpiński graphs are obtained as corollaries. In particular, our results for edge-disjoint Hamilton cycles and hub sets on iterated subdivided-line graphs are generalizations of the previously known results on Sierpiński graphs, while our proofs are simpler than those for Sierpiński graphs.

Toru Hasunuma

Induced Subtrees in Interval Graphs

The

Induced Subtree Isomorphism

problem takes as input a graph

G

and a tree

T

, and the task is to decide whether

G

has an induced subgraph that is isomorphic to

T

. This problem is known to be NP-complete on bipartite graphs, but it can be solved in polynomial time when

G

is a forest. We show that

Induced Subtree Isomorphism

can be solved in polynomial time when

G

is an interval graph. In contrast to this positive result, we show that the closely related

Subtree Isomorphism

problem is NP-complete even when

G

is restricted to the class of proper interval graphs, a well-known subclass of interval graphs.

Pinar Heggernes, Pim van ’t Hof, Martin Milanič

Protein Folding in 2D-Triangular Lattice Revisited

(Extended Abstract)

In this paper, we present a novel approximation algorithm to solve the protein folding problem in the H-P model. Our algorithm is polynomial in terms of the length of the given H-P string. The expected approximation ratio of our algorithm is

$1- \dfrac{2\log n }{n-1}$

for

n

 ≥ 6, where

n

2

is the total number of H in a given H-P string. The expected approximation ratio tends to 1 for large values of

n

. Hence our algorithm is expected to perform very well for larger H-P strings.

A. S. M. Shohidull Islam, M. Sohel Rahman

SAT and IP Based Algorithms for Magic Labeling with Applications

A labeling of a graph with

n

vertices and

m

edges is a one-to-one mapping from the union of the set of vertices and edges onto the set {1,2,…,

m

 + 

n

} . Such a labeling is defined as magic, if one or both of the following two conditions is fulfilled: the sum of an edge label and the labels of its endpoint vertices is constant for all edges; the sum of a vertex label and the labels of its incident edges is constant for all vertices. We present effective

IP

and

Sat

based algorithms for the problem of finding a magic labeling for a given graph. We experimentally compare the resulted algorithms by applying it to random graphs. Finally, we demonstrate its performance by solving five open problems within the theory of magic graphs, posed in the book of Wallis.

Gerold Jäger

An Optimal Algorithm for Computing All Subtree Repeats in Trees

Given a labeled tree

T

, our goal is to group repeating subtrees of

T

into equivalence classes with respect to their topologies and the node labels. We present an explicit, simple, and time-optimal algorithm for solving this problem for unrooted unordered labeled trees, and show that the running time of our method is linear with respect to the size of

T

. By unordered, we mean that the order of the adjacent nodes (children/neighbors) of any node of

T

is irrelevant. An unrooted tree

T

does not have a node that is designated as root and can also be referred to as an undirected tree. We show how the presented algorithm can easily be modified to operate on trees that do not satisfy some or any of the aforementioned assumptions on the tree structure; for instance, how it can be applied to rooted, ordered or unlabeled trees.

Tomáš Flouri, Kassian Kobert, Solon P. Pissis, Alexandros Stamatakis

Approximation Bounds on the Number of Mixedcast Rounds in Wireless Ad-Hoc Networks

We consider the following type of Maximum Network Lifetime problems. For a wireless network

N

with given capacities of node batteries, and a specification of a communication task which is to be performed periodically in

N

, find a maximum-size feasible collection of routing topologies for this task. Such a collection of routing topologies defines the maximum number of rounds this task can be performed before the first node in the network dies due to battery depletion. The types of communication tasks which we consider are unicast, broadcast, convergecast and mixedcast. The mixedcast is the requirement that some fixed number of tasks of the basic types (unicast, broadcast, convergecast) are periodically performed. We show that one can compute in polynomial time the number

k

of mixedcast rounds which is at least

$\lfloor{k_{opt}/5}\rfloor$

, for the single-topology variant of the problem, and at least

$\lfloor{k_{opt}/6}\rfloor$

, for the multiple-topology variant, improving the previous bounds.

Sang Hyuk Lee, Tomasz Radzik

Maximum Spectral Radius of Graphs with Connectivity at Most k and Minimum Degree at Least δ

Li, Shiu, Chan and Chang [On the spectral radius of graphs with connectivity at most

k

, J. Math. Chem., 46 (2009), 340-346] studied the spectral radius of graphs of order

n

with

κ

(

G

) ≤ 

k

and showed that among those graphs, the maximum spectral radius is obtained uniquely at

$K_k^n$

, which is the graph obtained by joining

k

edges from

k

vertices of

K

n

 − 1

to an isolated vertex. In this paper, we study the spectral radius of graphs of order

n

with

κ

(

G

) ≤ 

k

and minimum degree

δ

(

G

) ≥ 

k

. We show that among those graphs, the maximum spectral radius is obtained uniquely at

K

k

 + (

K

δ

 − 

k

 + 1

 ∪ 

K

n

 − 

δ

 − 1

).

Hongliang Lu, Yuqing Lin

Degree Sequences of PageRank Uniform Graphs and Digraphs with Prime Outdegrees

A

PageRank uniform digraph

is a digraph whose vertices have all the same PageRank score. These digraphs are interesting in the scope of privacy preserving release of digraph data in environments where a dishonest analyst may have previous structural knowledge about the PageRank score of some vertices. In this paper we first characterize PageRank uniform graphs (viewed as symmetric digraphs) and their degree sequence. Next, given a sequence of prime integers

S

, we give necessary and sufficient conditions for

S

to be the outdegree sequence of a PageRank uniform digraph.

Nacho López, Francesc Sebé

On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs

It is known that the maximum independent set problem is NP-complete for subcubic graphs, i.e. graphs of vertex degree at most 3. Moreover, the problem is NP-complete for

H

-free subcubic graphs whenever

H

contains a connected component which is not a tree with at most 3 leaves. We show that if every connected component of

H

is a tree with at most 3 leaves and at most 7 vertices, then the problem can be solved for

H

-free subcubic graphs in polynomial time.

Vadim Lozin, Jérôme Monnot, Bernard Ries

Construction Techniques for Digraphs with Minimum Diameter

We consider the so-called

order/degree problem

, that is, to determine the smallest diameter of a digraph given order and maximum out-degree. There is no general efficient algorithm known for the construction of such optimal digraphs but various construction techniques for digraphs with minimum diameter have been proposed. In this paper, we survey the known techniques.

Mirka Miller, Slamin, Joe Ryan, Edy Tri Baskoro

Suffix Tree of Alignment: An Efficient Index for Similar Data

We consider an index data structure for similar strings. The generalized suffix tree can be a solution for this. The generalized suffix tree of two strings

A

and

B

is a compacted trie representing all suffixes in

A

and

B

. It has |

A

| + |

B

| leaves and can be constructed in

O

(|

A

| + |

B

|) time. However, if the two strings are similar, the generalized suffix tree is not efficient because it does not exploit the similarity which is usually represented as an alignment of

A

and

B

.

In this paper we propose a space/time-efficient

suffix tree of alignment

which wisely exploits the similarity in an alignment. Our suffix tree for an alignment of

A

and

B

has |

A

| + 

l

d

 + 

l

1

leaves where

l

d

is the sum of the lengths of

all

parts of

B

different from

A

and

l

1

is the sum of the lengths of

some

common parts of

A

and

B

. We did not compromise the pattern search to reduce the space. Our suffix tree can be searched for a pattern

P

in

O

(|

P

| + 

occ

) time where

occ

is the number of occurrences of

P

in

A

and

B

. We also present an efficient algorithm to construct the suffix tree of alignment. When the suffix tree is constructed from scratch, the algorithm requires

O

(|

A

| + 

l

d

 + 

l

1

 + 

l

2

) time where

l

2

is the sum of the lengths of other common substrings of

A

and

B

. When the suffix tree of

A

is already given, it requires

O

(

l

d

 + 

l

1

 + 

l

2

) time.

Joong Chae Na, Heejin Park, Maxime Crochemore, Jan Holub, Costas S. Iliopoulos, Laurent Mouchard, Kunsoo Park

Fitting Voronoi Diagrams to Planar Tesselations

Given a tesselation of the plane, defined by a planar straight-line graph

G

, we want to find a minimal set

S

of points in the plane, such that the Voronoi diagram associated with

S

‘fits’

G

. This is the Generalized Inverse Voronoi Problem (GIVP), defined in [12] and rediscovered recently in [3]. Here we give an algorithm that solves this problem with a number of points that is linear in the size of

G

, assuming that the smallest angle in

G

is constant.

Greg Aloupis, Hebert Pérez-Rosés, Guillermo Pineda-Villavicencio, Perouz Taslakian, Dannier Trinchet-Almaguer

Partial Information Network Queries

We present a new pattern matching problem, the

partial information query (PIQ)

problem, which includes as special cases two problems that have important applications in bioinformatics: the

alignment query (AQ)

problem and the

topology-free query (TFQ)

problem. In both problems we have a pattern

$\cal P$

and a graph

H

, and we seek a subgraph of

H

that

resembles

$\cal P$

. AQ requires knowing the topology of

$\cal P$

, while TFQ ignores it. PIQ fits the scenario where partial information is available on the topology of

$\cal P$

. Our main result is a parameterized algorithm for PIQ, which can handle inputs where

$\cal P$

is a set of trees. It significantly improves the best known running time in solving TFQ. We also improve the best known running times in solving two special cases of AQ.

Ron Y. Pinter, Meirav Zehavi

An Application of Completely Separating Systems to Graph Labeling

In this paper a known algorithm used for the construction of completely separating systems (CSSs), Roberts’ Construction, is modified and used in a variety of ways to build CSSs. The main interest is in CSSs with different block sizes. A connection between CSSs and vertex antimagic edge labeled graphs is then exploited to prove that various non-regular graphs are antimagic. An outline for an algorithm which produces some of these non-regular graphs together with a vertex antimagic edge labeling is presented.

Leanne Rylands, Oudone Phanalasy, Joe Ryan, Mirka Miller

Universal Cycles for Weight-Range Binary Strings

We present an efficient universal cycle construction for the set of binary strings of length

n

with weight (number of 1s) in the range

c

,

c

 + 1, …,

d

where 0 ≤ 

c

 < 

d

 ≤ 

n

. The construction is based on a simple lemma for gluing universal cycles together, which can be implemented to generate each character in constant amortized time using

O

(

n

) space. The Gluing lemma can also be applied to construct universal cycles for other combinatorial objects including passwords and labeled graphs.

Joe Sawada, Aaron Williams, Dennis Wong

Circuit Complexity of Shuffle

We show that Shuffle(

x,y,w

), the problem of determining whether a string

w

can be composed from an order preserving shuffle of strings

x

and

y

, is not in

AC

0

, but it is in

AC

1

. The fact that shuffle is not in

AC

0

is shown by a reduction of parity to shuffle and invoking the seminal result [FSS84, while the fact that it is in

AC

1

is implicit in the results of [Man82a]. Together, the two results provide a strong complexity bound for this combinatorial problem.

Michael Soltys

An Optimal Algorithm for the Popular Condensation Problem

We consider an extension of the popular matching problem: the

popular condensation problem

. An instance of the popular matching problem consists of a set of applicants

A

and a set of posts

P

. Each applicant has a strictly ordered preference list, which is a sequence of posts in order of his/her preference. A matching

M

mapping from

A

to

P

is

popular

if there is no other matching

M

′ such that more applicants prefer

M

′ to

M

than prefer

M

to

M

′. Although some efficient algorithms have been proposed for finding a popular matching, a popular matching may not exist for those instances where the competition of some applicants cannot be resolved. The popular condensation problem is to find a popular matching with the minimum number of applicants whose preferences are neglected, that is, to optimally condense the instance to admit a local popular matching. We show that the problem can be solved in

O

(

n

 + 

m

) time, where

n

is the number of applicants and posts, and

m

is the total length of the preference lists.

Yen-Wei Wu, Wei-Yin Lin, Hung-Lung Wang, Kun-Mao Chao

Posters

Maximum st-Flow in Directed Planar Graphs via Shortest Paths

In this paper, we give a correspondence between maximum flows and shortest paths via duality in

directed

planar graphs with no constraints on the source and sink.

Glencora Borradaile, Anna Harutyunyan

Hypergraph Covering Problems Motivated by Genome Assembly Questions

We describe some genome assembly problems as a general problem of covering a hypergraph by linear and circular walks, where vertices represent sequence elements, repeated sequences are modelled by assigning a multiplicity to vertices, and edges represent co-localization information. We show that deciding if a given assembly hypergraph admits an assembly is fixed-parameter tractable, and we provide two exact polynomial time algorithms for clearing ambiguities caused by repeats.

Cedric Chauve, Murray Patterson, Ashok Rajaraman

Cluster Editing with Locally Bounded Modifications Revisited

For

Cluster Editing

where both the number of clusters and the edit degree are bounded, we speed up the kernelization by almost a factor

n

compared to Komusiewicz and Uhlmann (2012), at cost of a marginally worse kernel size bound. We also give sufficient conditions for a subset of vertices to be a cluster in some optimal clustering.

Peter Damaschke

New Approximation Algorithms for the Vertex Cover Problem

The vertex cover is a classical NP-complete problem that has received great attention these last decades. A conjecture states that there is no

c

-approximation polynomial algorithm for it with

c

a

constant

strictly less than 2. In this paper we propose a new algorithm with approximation ratio strictly less than 2 (but non constant). Moreover we show that our algorithm has the potential to return

any

optimal solution.

Franc̨ois Delbot, Christian Laforest, Raksmey Phan

Improved Approximation Algorithm for the Number of Queries Necessary to Identify a Permutation

In the past three decades, deductive games have become interesting from the algorithmic point of view. A well known deductive game is the famous Mastermind game. In this paper, we consider the so called Black-Peg variant of Mastermind. More precisely, we deal with a special version of the Black-Peg game with

n

holes and

k

 ≥ 

n

colors where no repetition of colors is allowed. We present a strategy that identifies the secret code in

$\mathcal{O}(n\log_2{n})$

queries. Our algorithm improves the previous result of Ker-I Ko and Shia-Chung Teng (1986) by almost a factor of 2 for the case

k

 = 

n

. To our knowledge there is no previous work dealing with the case

k

 > 

n

.

Mourad El Ouali, Volkmar Sauerland

Motif Matching Using Gapped Patterns

We consider the problem of matching a set

$\mathcal{P}$

of gapped patterns against a given text

T

of length

n

, where a gapped pattern is a sequence of strings (keywords), over a finite alphabet Σ of size

σ

, such that there is a gap of fixed length between each two consecutive strings.We assume the RAM model, with words of size w in bits.We are interested in computing the list ofmatching patterns for each position in the text. This problem is a specific instance of the

Variable Length Gaps problem

[2] (VLG problem) for multiple patterns and has applications in the discovery of transcription factor (TF) binding sites in DNA sequences when using generalized versions of the PositionWeightMatrix (PWM) model to representTF binding specificities. The paper [5] describes howa motif represented as a generalizedPWM can bematched as a set of gapped patternswith unit-length keywords, and presents algorithms for the restricted case of patterns with two unit-length keywords.

Emanuele Giaquinta, Kimmo Fredriksson, Szymon Grabowski, Esko Ukkonen

Domino Graphs and the Decipherability of Directed Figure Codes

We consider several kinds of decipherability of directed figure codes, where directed figures are defined as labelled polyominoes with designated start and end points, equipped with catenation that may use a merging function for overlapping regions. This setting extends decipherability questions from words to 2D structures. In this paper we develop a (variant of) domino graph that will allow us to decide some of the decipherability kinds by searching the graph for specific paths. Thus the main result characterizes directed figure decipherability by graph properties.

Włodzimierz Moczurad

A Pretty Complete Combinatorial Algorithm for the Threshold Synthesis Problem

A

linear pseudo-Boolean constraint

(LPB) [1,4,5] is an expression of the form

a

1

1

 + … + 

a

m

m

 ≥ 

d

. Here each ℓ

i

is a literal of the form

x

i

or 1 –

x

i

. An LPB can be used to represent a Boolean function; e.g. 2

x

1

 + 

x

2

 + 

x

3

 ≥ 2 represents the same function as the propositional formula

x

1 ∨ (

x

2 ∧ 

x

3).

Functions that can be represented by a single LPB are called

threshold functions

. The problem of finding the LPB for a threshold function given as disjunctive normal form (DNF) is called

threshold synthesis problem

. The reference on Boolean functions [4] formulates the research challenge of recognising threshold functions through an entirely combinatorial procedure. In fact, such a procedure had been proposed in [3,2] and was later reinvented by us [7]. In this paper, we report on an implementation of this procedure for which we have run experiments for up to

m

= 22. It can solve the biggest problems in a couple of seconds.

Christian Schilling, Jan-Georg Smaus, Fabian Wenzelmann

Conjunctive Hierarchical Secret Sharing Scheme Based on MDS Codes

An ideal conjunctive hierarchical secret sharing scheme, constructed based on the Maximum Distance Separable (MDS) codes, is proposed in this paper. The scheme, what we call, is computationally perfect. By computationally perfect, we mean, an authorized set can always reconstruct the secret in polynomial time whereas for an unauthorized set this is computationally hard. Also, in our scheme, the size of the ground field is independent of the parameters of the access structure. Further, it is efficient and requires

O

(

n

3

), where

n

is the number of participants.

Appala Naidu Tentu, Prabal Paul, China Venkaiah Vadlamudi

An FPT Certifying Algorithm for the Vertex-Deletion Problem

We provide a fixed-parameter certifying algorithm for the Vertex-deletion problem. An upper bound for the size of the forbidden set for

$\mathcal{C}$

+

k

v is shown demonstrating that, for all hereditary classes

$\mathcal{C}$

characterised by a finite forbidden set, the class

$\mathcal{C}$

+

k

v is characterised by a finite forbidden set.

The certifying algorithm runs in time

O

(

f

(

k

) ·

n

c

) and can be verified in

O

(

n

c

) in the affirmative case and

O

(

f

(

k

)) in the negative case. This is the first known fixed-parameter certifying algorithm, as far as the authors are aware.

Haiko Müller, Samuel Wilson

Backmatter

Weitere Informationen

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!

Bildnachweise