Frontiers in Algorithmics and Algorithmic Aspects in Information and Management

There has been remarkable progress in the classification program of the complexity of counting problems. This program is carried out in at least three interrelated formulations: Graph Homomorphisms, Counting CSP, and Holant Problems. In each formulation, complexity dichotomy theorems have been achieved which classify every problem in a given class to be either solvable in polynomial time or #P-hard.

Although pre-processing is a practical computing strategy almost universally employed for real-world attacks on NP-hard problems, it is perhaps surprising that for more than thirty years there has been no mathematically-disciplined theory of the subject. The parameterized / multivariate view of computational complexity makes such a theory possible, and this turns out to be deeply productive and useful. In the theory of parameterized complexity and algorithmics, the subject is termed

kernelization

. We survey the origins, recent developments and applications of the theory of polynomial-time kernelization.

Scheduling unrelated machines is a classical optimization problem in which we want to minimize the makespan of executing

m

tasks on

n

machines when machine

i

can execute task

j

in time t

ij

. Nisan and Ronen [6] posed the following problem: if the machines are selfish, how well can an incentive compatible mechanism approximate the minimum makespan? This is an important multiparameter problem in mechanism design and this question has been one of primary motivating problems in algorithmic game theory.

This talk surveys results from applying an idea of Liotta, Preparata and Tamassia: that a designer of geometric algorithms could consider the arithmetic precision necessary to guarantee a correct implementation as a resource whose use is to be minimized, much as we do with running time and memory space. As is often the case, constraints can inspire creativity in design of new algorithms for classic problems; examples include point location, segment intersection, and Voronoi diagram construction.

The uniform bounded facility location problem (UBFLP) seeks to the optimal way of locating facilities to minimize total costs (opening costs plus routing costs), while the maximal routing costs of all clients are at most a given bound

d

. After building a mixed 0-1 integer programming model for UBFLP, the paper gives ln

n

+1-approximation algorithm for UBFLP on general graph. Then, we present the first constant-factor approximation algorithm with an approximation guarantee of 6.853 + 

ε

for UBFLP on plane, which is composed of the algorithm by Dai and Yu [1] and the schema of Xu and Xu [2].

From the online point of view, this paper studies a variation of the k-Canadian Traveler Problem (

k

-CTP), in which there are multiple travelers who communicate with each other to share real-time information. The objective is to find a route from the origination to the destination as soon as possible. Based on different communication levels, we consider two problems with full communication(

P

1

) and with limited communication(

P

2

) respectively. We present lower bounds for the two problems respectively. Considering the urban traffic environment, we propose a Retrace-Alternating strategy for both problems, and prove that increasing the proportion of full communication travelers may not always improve the competitive performance of online strategies.

The incremental median problem consists of finding an incremental sequence of facility sets

F

1

 ⊆ 

F

2

 ⊆ ⋯ ⊆ 

F

n

, where each

F

k

contains at most

k

facilities. We say that this incremental medians sequence is

c

-competitive if the cost of each

F

k

is at most

c

times of the optimum cost of

k

-median problem. The smallest such

c

is called the

competitive ratio

. A particular case of the problem is considered in this paper: both the clients and facilities are located on the real line. [5] and [14] presented a polynomial-time algorithm for this one-dimensional case that computes an incremental sequence with competitive ratio 8. The best algorithm available has competitive ratio

$(1+\sqrt{2})^2\approx 5.83$

[19]. In this paper we give an improved polynomial-time algorithm with competitive factor 4.

In this paper, we investigate the problem of scheduling resumable proportionally deteriorating jobs on a single machine with a non-availability constraint. The goal is to minimize the total completion time. We show the problem is NP-hard. Furthermore, we present a fully polynomial time approximation scheme (FPTAS).

Given two genomic maps

G

1

and

G

2

each represented as a sequence of

n

gene markers, the

maximal strip recovery

(MSR) problem is to retain the maximum number of markers in both

G

1

and

G

2

such that the resultant subsequences, denoted as

G

1

*

and

G

2

*

, can be partitioned into the same set of maximal strips, which are common substrings of length greater than or equal to two. The

complementary

maximal strip recovery (CMSR) problem has the complementary goal to delete the minimum number of markers. Both MSR and CMSR have been shown NP-hard and APX-complete, and they admit a 4-approximation and a 3-approximation respectively. In this paper, we present an improved

$\frac 73$

-approximation algorithm for the CMSR problem, with its worst-case performance analysis done through a

sequential amortization

.

In this paper, we generalize the greedy routing concept to use semi-metric spaces. We prove that any connected

n

-vertex graph

G

admits a greedy embedding onto an appropriate semi-metric space such that (1) each vertex

v

of the graph is represented by up to

k

virtual coordinates (where the numbers are from 1 to 2

n

 − 1 and

k

 ≤ 

deg

(

v

)); and (2) using an appropriate distance definition, there is always a distance decreasing path between any two vertices in

G

. In particular, we prove that, for a 3-connected plane graph

G

, there is a greedy embedding of

G

such that: (1) the greedy embedding can be obtained in linear time; and (2) each vertex can be represented by at most 3 virtual coordinates from 1 to 2

n

 − 1. To our best knowledge, this is the first greedy routing algorithm for 3-connected plane graphs, albeit with non-standard notions of greedy embedding and greedy routing, such that: (1) it runs in linear time to compute the virtual coordinates for the vertices; and (2) the virtual coordinates are represented succinctly in

O

(

log

n

) bits.

A star forest is a collection of vertex-disjoint trees of depth at most 1, and its size is the number of leaves in all its components. A spanning star forest of a given graph

G

is a spanning subgraph of

G

that is also a star forest. The

spanning star forest problem

(SSF for short) [14] is to find the maximum-size spanning star forest of a given graph. In this paper, we study several variants of SSF, obtaining first or improved approximation and hardness results in all settings as shown below.

1

We study SSF on graphs of minimum degree

δ

(

n

),

n

being the number of vertices in the input graph. Call this problem ( ≥ 

δ

(

n

))-SSF. We give an (almost) complete characterization of the complexity of ( ≥ 

δ

(

n

))-SSF with respect to

δ

(

n

) as follows.

When 1 ≤ 

δ

(

n

) ≤ 

O

(1), ( ≥ 

δ

(

n

))-SSF is

APX

-complete.

When

ω

(1) ≤ 

δ

(

n

) ≤ 

O

(

n

1 − 

ε

) for some constant

ε

 > 0, ( ≥ 

δ

(

n

))-SSF is

NP

-hard but admits a PTAS.

When

δ

(

n

) ≥ 

ω

(

n

1 − 

ε

) for every constant

ε

 > 0, ( ≥ 

δ

(

n

))-SSF is not

NP

-hard assuming Exponential Time Hypothesis (ETH).

2

We investigate the spanning

k

-tree forest problem, which is a natural generalization of SSF. We obtain the first inapproximability bound of

$1-\Omega(\frac{1}{k})$

for this problem, which asymptotically matches the known approximation ratio of

$1-\frac{1}{k+1}$

given in [13]. We then propose an approximation algorithm for it with a slightly improved approximation ratio of

$1-\frac{1}{k+2}$

.

3

We prove that SSF cannot be approximated to any factor larger than

$\frac{244}{245}$

in polynomial time, unless

P

 = 

NP

. This improves the previously best known bound of

$\frac{259}{260}$

[14].

A vertex subset

X

of a graph

G

is said to be cyclable in

G

if there is a cycle in

G

containing all vertices of

X

. Ore [6] showed that the vertex set of

G

with cardinality

n

 ≥ 3 is cyclable (

i

.

e

.

G

is hamiltonian) if the degree sum of any pair of nonadjacent vertices in

G

is at least

n

. Shi [8] and Ota [7] respectively generalized Ore’s result by considering the cyclability of any vertex subset

X

of

G

under Ore type condition. Flandrin

et

al

. [4] in 2005 extended Shi’s conclusion under the condition called

regional

Ore

′

s

condition

. Zhu, Li and Deng [10] introduced the definition of implicit degrees of vertices. In this work, we generalize the result of Flandrin

et

al

. under their type condition with implicit degree sums. More precisely, we obtain that

X

is cyclable in a

k

-connected graph

G

if the implicit degree sum of any pair of nonadjacent vertices

u

,

v

 ∈ 

X

i

is at least the order of

G

, where each

X

i

,

i

 = 1,2, ⋯ ,

k

is a vertex subset of

G

and

X

 = ∪ 

k

i

 = 1

X

i

. In [10], the authors demonstrated that the implicit degree of a vertex is at least the degree of the vertex. Hence our result is better than the result of Flandrin

et

al

. in some way.

Lattice animals are connected sets of lattice cells. When the lattice is in

d

dimensions, connectedness is through (

d

 − 1)-dimensional features of the lattice. For example, connectedness of two-dimensional animals (e.g., on the rectangular, triangular, and hexagonal lattices) are through edges, connectedness of 3-dimensional polycubes is through faces, etc. Much attention has been given in the literature to algorithms for counting animals of a given size (number of cells) on different lattices. One such algorithm was suggested in 1981 by Redelmeier for counting polyominoes (animals on the 2D orthogonal lattice). This was the first algorithm that generated polyominoes without repetitions. In previous works we extended this algorithm to other lattices and showed how to avoid its (originally) huge memory consumption. In the current paper we describe how to parallelize the extended algorithm. Our implementation runs on the Internet, effectively using an unlimited number of computers running portions of the computation. Thus, we were able to extend the known counts of animals on many types of lattices with values which were previously out of reach.

In this paper, we present an improved algorithm to decide whether a graph of maximum degree 3 has an edge dominating set of size at most

k

or not, which is based on enumeration of vertex covers. We first enumerate vertex covers of size at most 2

k

and then construct an edge dominating set based on each vertex cover to find a satisfied edge dominating set. To enumerate vertex covers, we use a branch-and-reduce method that will generate a search tree of size

O

(2.1479

k

). Then we get the running time bound of the algorithm.

In this paper we study several geometric problems of color-spanning sets: given

N

points with

M

colors in the plane, choosing

M

points with distinct colors such that some geometric properties of those

M

points are minimized or maximized. The geometric properties studied in this paper are the maximum diameter, the largest closest pair, and the minimum planar spanning tree. We give an

O

(

N

log

N

) expected time algorithm for the maximum diameter problem. For the largest closest pair and the minimum planar spanning tree problems, we give hardness proofs.

This paper presents the following approximation algorithms for computing a minimum cost sequence of planes to cut a convex polyhedron

P

of

n

vertices out of a sphere

Q

: an

O

(

n

log

n

) time

O

(log

2

n

)-factor approximation, an

O

(

n

1.5

log

n

) time

O

(log

n

)-factor approximation, and an

O

(1)-factor approximation with exponential running time. Our results significantly improve upon the previous

O

(

n

3

) time

O

(log

2

n

)-factor approximation solution.

An

acyclic edge-colouring

of a graph is a proper edge-colouring such that the subgraph induced by the edges of any two colours is acyclic. The

acyclic chromatic index

of a graph

G

is the smallest possible number of colours in an acyclic edge-colouring of

G

. In [12], we have shown that the acyclic chromatic index of a connected subcubic graph

G

is at most 4 with the exception of

K

4

and

K

3,3

, for which five colors are optimal. Here we give a quadratic-time algorithm that finds an acyclic 4-edge-colouring of a given connected subcubic graph different from

K

4

and

K

3,3

.

In this paper, we study the {

k

}-domination, total {

k

}-domin-ation, {

k

}-domatic number, and total {

k

}-domatic number problems, from complexity and algorithmic points of view. Let

k

 ≥ 1 be a fixed integer and

ε

 > 0 be any constant. Under the hardness assumption of

$NP\not\subseteq DTIME(n^{O(\log\log n)})$

, we obtain the following results.

1

The total {

k

}-domination problem is

NP

-complete even on bipartite graphs.

2

The total {

k

}-domination problem has a polynomial time ln

n

approximation algorithm, but cannot be approximated within

$(\frac{1}{k}-\epsilon)\ln n$

in polynomial time.

3

The total {

k

}-domatic number problem has a polynomial time

$(\frac{1}{k}+\epsilon)\ln n$

approximation algorithm, but does not have any polynomial time

$(\frac{1}{k}-\epsilon)\ln n$

approximation algorithm.

All our results hold also for the non-total variants of the problems.

Power assignment in wireless ad hoc networks can be seen as a family of problems in which the task is to find in a given power requirement network a minimum power communication subnetwork that satisfies a given connectivity constraint. These problems have been extensively studied from the viewpoint of approximation, heuristic, linear programming,

etc

. In this paper, we add a new facet by initiating a systematic parameterized complexity study of three types of power assignment problems related to multicast: Min-power Single-source

h

-Multicast, Min-power Strongly Connected

h

-Multicast and Min-power Multi-source

h

-Multicast. We investigate their parameterized complexities with respect to the number of terminals and the number of senders. We show that Min-power Single-source

h

-Multicast is fixed-parameter tractable with respect to the number of terminals and achieve several parameterized hardness results.

For an undirected graph

G

, a zero-sum flow is an assignment of non-zero integers to the edges such that the sum of the values of all edges incident with each vertex is zero. We extend this notion to a more general one in this paper, namely a

constant-sum flow

. The constant under a constant-sum flow is called an

index

of

G

, and

I

(

G

) is denoted as the

index set

of all possible indices of

G

. Among others we obtain that the index set of a regular graph admitting a perfect matching is the set of all integers. We also completely determine the index sets of all

r

-regular graphs except that of 4

k

-regular graphs of even order,

k

 ≥ 1.

In this paper, we study a two-dimensional knapsack problem: packing squares as many as possible into a unit square. Our results are the following:

(i)

first, we propose an algorithm called IHS(Increasing Height Shelf), and prove that the packing is optimal if there are at most 5 squares packed in an optimal packing, and this upper bound 5 is sharp;

(ii)

secondly, if all the items have size(side length) at most

$\frac{1}{k}$

, where

k

 ≥ 1 is a constant number, we propose a simple algorithm with an approximation ratio

$\frac{k^2+3k+2}{k^2}$

in time

O

(

n

log

n

).

(iii)

finally, we give a PTAS for the general case, and our algorithm is much simpler than the previous approach[16].

We consider the frugal coverage problem, an interesting variation of set cover defined as follows. Instances of the problem consist of a universe of elements and a collection of sets over these elements; the objective is to compute a subcollection of sets so that the number of elements it covers plus the number of sets not chosen is maximized. The problem was introduced and studied by Huang and Svitkina [7] due to its connections to the donation center location problem. We prove that the greedy algorithm has approximation ratio at least 0.782, improving a previous bound of 0.731 in [7]. We also present a further improvement that is obtained by adding a simple corrective phase at the end of the execution of the greedy algorithm. The approximation ratio achieved in this way is at least 0.806. Our analysis is based on the use of linear programs which capture the behavior of the algorithms in worst-case examples. The obtained bounds are proved to be tight.

We present new algorithms for two problems on interval structures that arise in computer-aided manufacturing and in other areas. We give an

O

(

Kn

) time algorithm for the single-source

K

-link shortest path problem on an interval graph with

n

weighted vertices, and two

O

(

n

) time algorithms for a generalized version of the optimal color-spanning problem for

n

points on a real line, where each point is assigned one of

m

colors (

m

 ≤ 

n

). A standard approach for solving the

K

-link shortest path problem would take

O

(

Kn

2

) time, and thus our result offers a linear time improvement. The previously best known algorithm for the optimal color-spanning problem in ℝ

1

takes

O

(

n

) time and space. We provide two algorithms for a generalized version of this problem in which each color must appear a specified minimum number of times. One of these two solutions is suitable for an

online

processing of the (streaming) input points; it uses

O

(

m

) working space for the ordinary 1-D optimal color-spanning problem.

This paper considers the single machine scheduling problem with an operator non-availability period. The operator non-availability period is an open time interval in which a job may neither start nor complete. The objective is to minimize the total completion time. The problem is NP-hard. We present an algorithm with a tight worst-case ratio of 20/17.

Sequencing errors in high-throughput sequencing data constitute one of the major problems in analyzing such data. Error correction can reduce the error rate. However, it is a computation and data intensive process for large-scale data. This poses challenges for more efficient and scalable algorithms. In this paper, we propose PSAEC, an improved algorithm for short read error correction using partial suffix arrays in high-throughput sequencing data. Our algorithm optimizes the HiTEC program by replacing full suffix arrays with partial suffix arrays to index reads which is more time and space efficient. Moreover, PSAEC is a scalable parallel algorithm that can works well on multi-core computers using Pthread. Experiments show that our algorithm delivers good, scalable performance.

A feedback vertex set is a subset of vertices whose deletion makes the remaining graph a forest. We show that the minimum FVS (MFVS) in star convex bipartite graphs is

$\mathcal{NP}$

-hard to find, and give a tighter lower bound on the size of MFVS in sparse random graphs, to provide further evidence on the hardness of random CSPs.

We consider the problem of unrelated parallel machine scheduling when the DVS (dynamic voltage scaling) method is used to conserve energy consumption. Given an energy budget, we present (2 + 

ε

)-approximation algorithms for the makespan minimization problem under two different settings, the continuous model in which speeds are allowed to be any real number in [

s

min

,

s

max

] and the discrete model in which only

d

distinct speeds are available. We also show how to derive a 2-approximation algorithm if the energy budget is allowed to be slightly exceeded.

The process where simple entities form more complex structures acting autonomously is called self-assembly; it lies at the centre of many physical, chemical and biological phenomena. Massively parallel formation of nanostructures or DNA computation are just two examples of possible applications of self-assembly once it is technologically harnessed. Various mathematical models have been proposed for self-assembly, including the well-known Winfree’s Tile Assembly Model based on Wang tiles on a two-dimensional plane. In the present paper we propose a model based on directed figures with partial catenation. Directed figures are defined as labelled polyominoes with designated start and end points, and catenation is defined for non-overlapping figures. This is one of possible extensions generalizing words and variable-length codes to planar structures, and a flexible model, allowing for a natural expression of self-assembling entities as well as

e.g.

image representation or “pictorial barcoding.” We prove several undecidability results related to filling the plane with a given set of figures and formation of infinite and semi-infinite zippers, demonstrating a unifying approach that could be useful for the study of self-assembly.

Automatic derivation of invariants is one of the critical conundrums in the framework of the inductive program verification methodologies. This paper presents a novel and simple approach to generating polynomial equations as loop invariants. Finite difference of expressions and linear equation solving are harnessed. Unlike related work, the generated constraints are linear equalities, which can be solved efficiently. Furthermore, invariants of higher degree can be constructed in terms of those of lower degree. The case studies demonstrate the effectiveness of the approach.

Genome rearrangements are large-scale mutations that result in a shuffling of the genes on a genome. Despite these rearrangements, whole genome analysis of modern species has revealed sets of genes that are found close to one another in multiple species. These

conserved gene clusters

provide useful information on gene function and genome evolution. In this paper, we consider a novel gene cluster model called

bidirectional best hit r

-window

(BBHRW) in which the idea is to (a) capture the “frequency of common genes” in an

r

-window (interval of at most

r

consecutive genes) of each genome and (b) to further strengthen it by the

bidirectional best hit

criteria. We define two variants of BBHRW using two different similarity measures to define the “frequency of common genes” in two

r

-windows. Then the algorithmic problem is as follows: Give two genomes of length

n

and

m

, and an integer

r

, compute all the BBHRW clusters. A straight-forward algorithm for solving this problem is an

O

(

nm

) algorithm that compares all pairs of

r

-windows. In this paper, we present faster algorithms (SWBST and SWOT) for solving these two BBHRW variants. Algorithm SWBST is a simpler algorithm that solves the first variant of the BBHRW, while algorithm SWOT solves both variants of the BBHRW. Both algorithms have running time

$O((n+m) r \lg r)$

. The algorithmic speed-up is achieved via a sliding window approach and with the use of efficient data structures. We implemented the algorithms and compare their running times for finding BBHRW clusters conserved in

E. coli

K-12 (2339 genes) and

B. subtilis

(2332 genes) with

r

from 1 to 30 to illustrate the speed-up achieved. We also compare the two similarity measures for these genomes to show that the choice of similarity measure is an important factor for this cluster model.

The link structure of the Web is generally viewed as the webgraph. One of the main objectives of web structure mining is to find hidden communities on the Web based on the webgraph, and one of its approaches tries to enumerate substructures each of which corresponds to a set of web pages of a community or its core. Through those research, it has been turned out that certain substructures can find sets of pages that are inherently irrelevant to communities. In this paper, we propose a model, which we call

contracted webgraphs

, where such substructures are contracted into single nodes to hide useless information. We then try structure mining iteratively on those contracted webgraphs since we can expect to find further hidden information once irrelevant information is eliminated. We also explore structural properties of contracted webgraphs from the viewpoint of scale-freeness, and we observe that they exhibit novel and extreme self-similarities.

The Min-Min problem of finding a disjoint path pair with the length of the shorter path minimized is known to be NP-complete and no

K

-approximation exists for any

K

 ≥ 1 [1]. In this paper, we give a simpler proof of this result in general digraphs. We show that this proof can be extended to the problem in planar digraphs whose complexity was unknown previously. As a by-product, we show this problem remains NP-complete even when all edge costs are equal (i.e. strongly NP-complete).

In this paper, we study 1-space bounded multi-dimensional bin packing. A sequence of items arrive over time, each item is a

d

-dimensional hyperbox and the length of each side is no more than 1. These items must be packed without overlapping into

d

-dimensional hypercubes with unit length on each side. In

d

-dimensional space, any two dimensions

i

and

j

define a space

P

ij

. When an item arrives, we must pack it into an active bin immediately without any knowledge of the future items, and 90°-rotation on any plane

P

ij

is allowed.

The objective is to minimize the total number of bins used for packing all these items in the sequence. In the 1-space bounded variant, there is only one active bin for packing the current item. If the active bin does not have enough space to pack the item, it must be closed and a new active bin is opened. For this problem, we give an online algorithm with competitive ratio 4

d

, which is the first study on 1-space bounded

d

-dimensional bin packing.

We consider a temperature-aware online deadline scheduling model. The objective is to schedule a number of unit jobs, with release dates, deadlines, weights and heat contributions, to maximize the weighted throughput subject to a temperature threshold. We give an optimal randomized algorithm and another resource-augmented constant-competitive randomized algorithm for the problem. We also give almost tight upper and lower bounds for the multiple processor case.

We study the online scheduling problem of maximising job completion subject to temperature constraints. In our setting, jobs are of equal length and have deadlines and heat contributions. The algorithm tries to complete as many jobs as possible before their deadlines while keeping the temperature of the system within an acceptable limit. We give an optimal algorithm for the case where preemption is not allowed. Then we consider the case of preemption and prove a number of lower bounds, showing that for many combination of system parameters, preemption (with restart) is not helpful in improving the competitiveness.

For a set of

n

disjoint line segments

S

in

R

2

, the visibility counting problem (VCP) is to preprocess

S

such that the number of visible segments in

S

from a query point

p

can be computed quickly. For this configuration, the visibility testing problem (VTP) is to test whether

p

sees a fixed segment

s

. These problems can be solved in logarithmic query time by using

O

(

n

4

) preprocessing time and space. In this paper, we approximately solve this problem using quadratic preprocessing time and space. Our methods are superior to current approximation algorithms in terms of both approximation factor and preprocessing cost. In this paper, we propose a 2-approximation algorithm for the VCP using at most quadratic preprocessing time and space. The query time of this method is

$O_{\varepsilon}(n^{2}/\sqrt{k})$

where

k

is the preprocessing time and

O

ε

(

f

(

n

) ) = 

O

(

f

(

n

)

n

ε

). We also solve the VTP in expected logarithmic query time using quadratic time and space.

Comparing and ranking information is an important topic in social and information sciences, and in particular on the web. Its objective is to measure the difference of the preferences of voters on a set of candidates and to compute a consensus ranking. Commonly, each voter provides a total order of all candidates. Recently, this approach has been generalized to bucket orders, which allow ties.

In this work we further generalize and consider total, bucket, interval and partial orders. The disagreement between two orders is measured by the nearest neighbor Spearman footrule distance, which has not been studied so far. We show that the nearest neighbor Spearman footrule distance of two bucket orders and of a total and an interval order can be computed in linear time, whereas the computation is

NP

-complete and 6-approximable for a total and a partial order. Moreover, we establish the

NP

-completeness and the 4-approximability of the rank aggregation problem for bucket orders. This sharply contrasts the well-known efficient solution of this problem for total orders.

In this paper, we identify a minimum width rectangular annulus that encloses a given set of

n

points in a plane. We propose an

O

(

n

2

log

n

) time and

O

(

n

) space algorithm for this problem. To the best of our knowledge this is the first sub-cubic algorithm for rectangular annulus for arbitrary orientation.

We survey several planar graph generators that were selected according to availability, theoretical interest, easiness of implementation and efficiency. We experimentally study graph properties that allow for a basic classification of the generators. This analysis is extended by means of advanced algorithmical behavior on the generated graphs, in particular kernelization of fixed-parameter tractable problems. We will see the major influence of instance selection on algorithmic behavior. This selection has been disregarded in several publications, which deduce general results from non-representative data sets. Altogether, this study helps experimenters to carefully select sets of planar graphs that allow for a meaningful interpretation of their results.