Combinatorial Algorithms

Maximum Common Induced Subgraph

(henceforth MCIS) is among the most studied classical

$${\mathsf {NP}}$$

-hard problems. MCIS remains

$${\mathsf {NP}}$$

-hard on many graph classes including bipartite graphs, planar graphs and

k

-trees. Little is known, however, about the parameterized complexity of the problem. When parameterized by the vertex cover number of the input graphs, the problem was recently shown to be fixed-parameter tractable. Capitalizing on this result, we show that the problem does not have a polynomial kernel when parameterized by vertex cover unless

$${\mathsf {NP}}\subseteq \mathsf {coNP}/poly$$

. We also show that

Maximum Common Connected Induced Subgraph

(MCCIS), which is a variant where the solution must be connected, is also fixed-parameter tractable when parameterized by the vertex cover number of input graphs. Both problems are shown to be

$${\mathsf {W[1]}}$$

-complete on bipartite graphs and graphs of girth five and, unless

$${\mathsf {P}}= {\mathsf {NP}}$$

, they do not belong to the class

$${\mathsf {XP}}$$

when parameterized by a bound on the size of the minimum feedback vertex sets of the input graphs, that is solving them in polynomial time is very unlikely when this parameter is a constant.

In this paper we study the following problem, named Maximum Edges in Transitive Closure, which has applications in computational biology. Given a simple, undirected graph

$$G = (V,E)$$

and a coloring of the vertices, remove a collection of edges from the graph such that each connected component is

colorful

(i.e., it does not contain two identically colored vertices) and the number of edges in the transitive closure of the graph is maximized.

The problem is known to be APX-hard, and no approximation algorithms are known for it. We improve the hardness result by showing that the problem is NP-hard to approximate within a factor of

$$|V|^{1/3 - \varepsilon }$$

, for any constant

$$\varepsilon > 0$$

. Additionally, we show that the problem is APX-hard already for the case when the number of vertex colors equals 3. We complement these results by showing the first approximation algorithm for the problem, with approximation factor

$$\sqrt{2 \cdot \text {OPT}}$$

.

It is well recognised that data mining and statistical analysis pose a serious treat to privacy. This is true for financial, medical, criminal and marketing research. Numerous techniques have been proposed to protect privacy, including restriction and data modification. Recently proposed privacy models such as differential privacy and k-anonymity received a lot of attention and for the latter there are now several improvements of the original scheme, each removing some security shortcomings of the previous one. However, the challenge lies in evaluating and comparing privacy provided by various techniques. In this paper we propose a novel entropy based security measure that can be applied to any generalisation, restriction or data modification technique. We use our measure to empirically evaluate and compare a few popular methods, namely query restriction, sampling and noise addition.

We give a complete characterization of bipartite graphs having tree-like Galois lattices. We prove that the poset obtained by deleting bottom and top elements from the Galois lattice of a bipartite graph is tree-like if and only if the graph is a Bipartite Distance Hereditary graph. We show that the lattice can be realized as the containment relation among directed paths in an arborescence. Moreover, a compact encoding of Bipartite Distance Hereditary graphs is proposed, that allows optimal time computation of neighborhood intersections and maximal bicliques.

In this article, we introduce a new and simple data structure, the prefix table under Hamming distance, and present two algorithms to compute it efficiently: one asymptotically fast; the other very fast on average and in practice. Because the latter approach avoids the computation of global data structures, such as the suffix array and the longest common prefix array, it yields algorithms much faster in practice than existing methods. We show how this data structure can be used to solve two string problems of interest: (a) approximate string matching under Hamming distance; and (b) longest approximate overlap under Hamming distance. Analogously, we introduce the prefix table under edit distance, and present an efficient algorithm for its computation. In the process, we also define the border array under both distance measures, and provide an algorithm for conversion between prefix tables and border arrays.

We consider the border sets of partial words and study the combinatorics of specific representations of them, called border correlations, which are binary vectors of same length indicating the borders. We characterize precisely which of these vectors are valid border correlations, and establish a one-to-one correspondence between the set of valid border correlations and the set of valid period correlations of a given length, the latter being ternary vectors representing the strong and strictly weak period sets. It turns out that the sets of all border correlations of a given length form distributive lattices under suitably defined partial orderings. We also investigate the population size, i.e., the number of partial words sharing a given border correlation, and obtain formulas to compute it. We do so using the subgraph component polynomial of an undirected graph, introduced recently by Tittmann et al. (European Journal of Combinatorics, 2011), which counts the number of connected components in vertex induced subgraphs.

Motivated by text compression, the problem of representing sets of words of uniform length by partial words, i.e., sequences that may have some wildcard characters or holes, was recently considered and shown to be in

$$\mathcal {P}$$

. Polynomial-time algorithms that construct representations were described using graph theoretical approaches. As more holes are allowed, representations shrink, and if representation is given, the set can be reconstructed. We further study this problem by determining, for a binary alphabet, the largest possible value of the size of a set of partial words that is important in deciding the representability of a given set

S

of words of uniform length. This largest value, surprisingly, is

$$\varSigma _{i=0}^{|S|-1} 2^{\chi (i)}$$

where

$$\chi (i)$$

is the number of ones in the binary representation of

i

, a well-studied digital sum, and it is achieved when the cardinality of

S

is a power of two. We show that circular representability is in

$$\mathcal {P}$$

and that unlike non-circular representability, it is easy to decide. We also consider the problem of computing minimum length representation (circular) total words, those without holes, and reduce it to a cost/flow network problem.

This paper deals with two types of repetitions in strings:

squares

, which consist of two adjacent occurrences of substrings, and

runs

, which are periodic substrings that cannot be extended further to the left or right. We show how to compute all the primitively-rooted squares in a given partial word, which is a sequence that may have undefined positions, called holes or wildcards, that match any letter of the alphabet over which the sequence is defined. We also describe an algorithm for computing all primitively-rooted runs in a given partial word.

Given a triangle-free planar graph

G

and a cycle

C

of length 9 in

G

, we characterize all situations where a 3-coloring of

C

does not extend to a proper 3-coloring of

G

. This extends previous results for the length of

C

up to 8.

Heat kernel pagerank is a variation of Personalized PageRank given in an exponential formulation. In this work, we present a sublinear time algorithm for approximating the heat kernel pagerank of a graph. The algorithm works by simulating random walks of bounded length and runs in time

$$O\big (\frac{\log (\epsilon ^{-1})\log n}{\epsilon ^3\log \log (\epsilon ^{-1})}\big )$$

, assuming performing a random walk step and sampling from a distribution with bounded support take constant time.

The quantitative ranking of vertices obtained with heat kernel pagerank can be used for local clustering algorithms. We present an efficient local clustering algorithm that finds cuts by performing a sweep over a heat kernel pagerank vector, using the heat kernel pagerank approximation algorithm as a subroutine. Specifically, we show that for a subset

S

of Cheeger ratio

$$\phi $$

, many vertices in

S

may serve as seeds for a heat kernel pagerank vector which will find a cut of conductance

$$O(\sqrt{\phi })$$

.

A

$$\varGamma $$

-distance magic labeling of a graph

$$G = (V, E)$$

with

$$|V| = n$$

is a bijection

$$\ell $$

from

V

to an Abelian group

$$\varGamma $$

of order

n

such that the weight

$$w(x) =\sum _{y\in N_G(x)}\ell (y)$$

of every vertex

$$x \in V$$

is equal to the same element

$$\mu \in \varGamma $$

called the magic constant. A graph

G

is called a group distance magic graph if there exists a

$$\varGamma $$

-distance magic labeling for every Abelian group

$$\varGamma $$

of order |

V

(

G

)|.

A

$$\varGamma $$

-magic rectangle set

$$MRS_{\varGamma }(a, b; c)$$

of order

abc

is a collection of

c

arrays

$$(a\times b)$$

whose entries are elements of group

$$\varGamma $$

, each appearing once, with all row sums in every rectangle equal to a constant

$$\omega \in \varGamma $$

and all column sums in every rectangle equal to a constant

$$\delta \in \varGamma $$

.

In the paper we show that if

a

and

b

are both even then

$$MRS_{\varGamma }(a, b; c)$$

exists for any Abelian group

$$\varGamma $$

of order

abc

. Furthermore we use this result to construct group distance magic labeling for some families of graphs.

We investigate the problem maxDMM of computing a largest set of pairwise disjoint maximum matchings in undirected graphs. In this paper,

n

,

m

denote, respectively, the number of vertices and the number of edges. We solve maxDMM for bipartite graphs, by providing an

$$O(n^{1.5}\sqrt{m/\log n} + mn\log n)$$

-time algorithm. We design better algorithms for complete bipartite graphs, and

bisplit

graphs. (Bisplit graphs are bipartite graphs with the nested neighborhood property.) Specifically, we prove that the problem maxDMM is solvable in complete bipartite graphs in time

O

(

m

). A sequence

$$S=(s_1,\cdots ,s_t)$$

of positive integers is said to be

color-feasible

for a graph

G

, if there exists a proper edge-coloring of

G

with colors

$$1,\cdots ,t$$

, such that precisely

$$s_i$$

edges have color

i

, for every

$$i=1,\cdots ,t$$

. Actually, for complete bipartite graphs, we prove that, for any sequence

S

of integers which is color-feasible for a complete bipartite graph

G

, an edge-coloring of

G

corresponding to

S

can be obtained in time

O

(

m

). For bisplit graphs, (1) we solve maxDMM in time

$$O(mn\log n)$$

, and (2) we design an

$$O(n^2\log n)$$

-time algorithm to count all maximum matchings. This latter time is the same time in which runs the best known algorithm computing the number of maximum matchings in bisplit graphs [

17

], but our algorithm is much simpler than the one given in [

17

]. The key idea underlying both results is that bisplit graphs have an

O

(

n

)-time enumeration of their minimal vertex covers.

A

sliding camera

travelling along a line segment

s

in a polygon

P

can see a point

p

in

P

if and only if

p

lies on a line segment contained in

P

that intersects

s

at a right angle. The objective of the

minimum sliding cameras (MSC)

problem is to guard

P

with the fewest sliding cameras possible, each of which is a horizontal or vertical line segment. In this paper, we give an

$$O(n^3)$$

-time 3-approximation algorithm for the MSC problem on any simple orthogonal polygon with

n

vertices. Our algorithm involves establishing a connection between the MSC problem and the problem of guarding simple grids with

periscope guards

.

Let

G

of order

n

be the vertex-disjoint union of an even and an odd cycle. It is known that there exists a

G

-decomposition of

$$K_v$$

for all

$$v \equiv 1 \pmod {2n}$$

. We use an extension of the Bose construction for Steiner triple systems and a recent result on the Oberwolfach Problem for 2-regular graphs with two components to show that there exists a

G

-decomposition of

$$K_{v}$$

for all

$$v \equiv n \pmod {2n}$$

, unless

$$G = C_4\cup C_5$$

and

$$v = 9$$

.

Suppose that we are given two vertex covers

$$C_{0}$$

and

$$C_{t}$$

of a graph

G

, together with an integer threshold

$$k\ge \max \{\left| C_0 \right| , \left| C_t \right| \}$$

. Then, the

vertex cover reconfiguration

problem is to determine whether there exists a sequence of vertex covers of

G

which transforms

$$C_{0}$$

into

$$C_{t}$$

such that each vertex cover in the sequence is of cardinality at most

$$k$$

and is obtained from the previous one by either adding or deleting exactly one vertex. This problem is PSPACE-complete even for planar graphs. In this paper, we first give a linear-time algorithm to solve the problem for even-hole-free graphs, which include several well-known graphs, such as trees, interval graphs and chordal graphs. We then give an upper bound on

$$k$$

for which any pair of vertex covers in a graph

G

has a desired sequence. Our upper bound is best possible in some sense.

Given a sequence of

n

elements from a totally ordered set, and a position in the sequence, the nearest larger neighbor (NLN) query returns the position of the element which is closest to the query position, and is larger than the element at the query position. The problem of finding all nearest larger neighbors has attracted interest due to its applications for parenthesis matching and in computational geometry [

1

–

3

]. We consider a data structure version of this problem, which is to preprocess a given sequence of elements to construct a data structure that can answer NLN queries efficiently. We consider time-space tradeoffs for the problem in both the encoding (where the input is not accessible after the data structure has been created) and indexing model, and consider cases when the input is in a one or two dimensional array. We also consider the version when only the nearest larger right neighbor (NLRN) is sought (in one dimension). We initiate the study of this problem in two dimensions, and describe upper and lower bounds in the encoding and indexing models, distinguishing the two cases when all the elements are distinct or non-distinct.

We investigate a version of the Mastermind game, where the codebreaker may only store a constant number of questions and answers, called Constant-Size Memory Mastermind, which was recently introduced by Doerr and Winzen. We concentrate on the most difficult case, where the codebreaker may store only one question and one answer, called Size-One Memory Mastermind. We consider two variants of the game: the original one, where the answer is coded with white and black pegs, and the simplified one, where only black pegs are used in the answer. We show that for two pegs and an arbitrary number of colors, the number of questions needed by the codebreaker in an optimal strategy in the worst case for these games is equal to the corresponding number of questions in the games without a memory restriction. In other words, for these cases restricting the memory size does not make the game harder for the codebreaker. This is a continuation of a result of Doerr and Winzen, who showed that this holds asymptotically for a fixed number of colors and an arbitrary number of pegs. Furthermore, by computer search we determine additional pairs (

p

,

c

), where again the numbers of questions in an optimal strategy in the worst case for Size-One Memory Mastermind and original Mastermind are equal.

The complexity of the maximum common connected subgraph problem in partial

k

-trees is still not fully understood. Polynomial-time solutions are known for degree-bounded outerplanar graphs, a subclass of the partial 2-trees. On the contrary, the problem is known to be

NP

-hard in vertex-labeled partial 11-trees of bounded degree. We consider series-parallel graphs, i.e., partial 2-trees. We show that the problem remains

NP

-hard in biconnected series-parallel graphs with all but one vertex of degree bounded by three. A positive complexity result is presented for a related problem of high practical relevance which asks for a maximum common connected subgraph that preserves blocks and bridges of the input graphs. We present a polynomial time algorithm for this problem in series-parallel graphs, which utilizes a combination of BC- and SP-tree data structures to decompose both graphs.

In the

Student/Project Allocation problem

(spa)

we seek to assign students to individual or group projects offered by lecturers. Students provide a list of projects they find acceptable in order of preference. Each student can be assigned to at most one project and there are constraints on the maximum number of students that can be assigned to each project and lecturer. We seek matchings of students to projects that are optimal with respect to

profile

, which is a vector whose

r

th component indicates how many students have their

r

th-choice project. We present an efficient algorithm for finding a

greedy maximum matching

in the

spa

context – this is a maximum matching whose profile is lexicographically maximum. We then show how to adapt this algorithm to find a

generous maximum matching

– this is a matching whose reverse profile is lexicographically minimum. Our algorithms involve finding optimal flows in networks. We demonstrate how this approach can allow for additional constraints, such as lecturer lower quotas, to be handled flexibly.

In this paper we introduce and study a new problem named

min-max edge

q

-coloring

which is motivated by applications in wireless mesh networks. The input of the problem consists of an undirected graph and an integer

q

. The goal is to color the edges of the graph with as many colors as possible such that: (a) any vertex is incident to at most

q

different colors, and (b) the maximum size of a color group (i.e. set of edges identically colored) is minimized. We show the following results:

1.

Min-max edge

q

-coloring is NP-hard, for any

$$q \ge 2$$

.

2.

A polynomial time exact algorithm for min-max edge

q

-coloring on trees.

3.

Exact formulas of the optimal solution for cliques.

4.

An approximation algorithm for planar graphs.

Given a graph

G

, a

vertex switch

of

$$v \in V(G)$$

results in a new graph where neighbors of

v

become nonneighbors and vice versa. This operation gives rise to an equivalence relation over the set of labeled digraphs on

n

vertices. The equivalence class of

G

with respect to the switching operation is commonly referred to as

G

’s

switching class

. The algebraic and combinatorial properties of switching classes have been studied in depth; however, they have not been studied as thoroughly from an algorithmic point of view. The intent of this work is to further investigate the algorithmic properties of switching classes. In particular, we show that switching classes can be used to asymptotically speed up several super-linear unweighted graph algorithms. The current techniques for speeding up graph algorithms are all somewhat involved insofar that they employ sophisticated pre-processing, data-structures, or use “word tricks” on the RAM model to achieve at most a

$$O(\log (n))$$

speed up for sufficiently dense graphs. Our methods are much simpler and can result in super-polylogarithmic speedups. In particular, we achieve better bounds for diameter, transitive closure, bipartite maximum matching, and general maximum matching.

Let

D

be a set of positive integers. The

kappa value

of

D

, denoted by

$$\kappa (D)$$

, is the parameter involved in the so called “lonely runner conjecture.” Let

x

,

y

be positive integers, we investigate the kappa values for the family of sets

$$D =\{2, 3, x, y\}$$

. For a fixed positive integer

$$x > 3$$

, the exact values of

$$\kappa (D)$$

are determined for

$$y=x+i$$

,

$$1 \le i \le 6$$

. These results lead to some asymptotic behavior of

$$\kappa (D)$$

for

$$D=\{2, 3, x, y\}$$

.

Dirac’s and Ore’s conditions (1952 and 1960) are well known and classical sufficient conditions for a graph to contain a Hamiltonian cycle and they are generalized in 1976 by the Bondy-Chvátal Theorem. In this paper, we add constraints, called

conflicts

. A conflict in a graph

G

is a pair of distinct edges of

G

. We denote by

$$(G,\mathcal {C}onf)$$

a graph

G

with a set of conflicts

$$\mathcal {C}onf$$

. A

path without conflict

P

in

$$(G,\mathcal {C}onf)$$

is a path

P

in

G

such that for any edges

$$e,e'$$

of

P

,

$$\{e,e'\}\notin \mathcal {C}onf$$

. In this paper we consider graph with conflicts such that each vertex is not incident to the edges of more than one conflict. We call such graphs

one-conflict graphs

. We present sufficient conditions for one-conflict graphs to have a Hamiltonian path or cycle without conflict.

Covering subsequences by sets of permutations arises in numerous applications. Given a set of permutations that cover a specific set of subsequences, it is of interest not just to know how few permutations can be used, but also to find a set of size equal to or close to the minimum. These permutation construction problems have proved to be computationally challenging; few explicit constructions have been found for small sets of permutations of intermediate length, mostly arising from greedy algorithms. A different strategy is developed here. Starting with a set that covers the specific subsequences required, we determine local changes that can be made in the permutations without losing the required coverage. By selecting these local changes (using linear extensions) so as to make one or more permutations less ‘important’ for coverage, the method attempts to make a permutation redundant so that it can be removed and the set size reduced. A post-optimization method to do this is developed, and preliminary results on sequence covering arrays show that it is surprisingly effective.

We are interested in the problem of covering simple orthogonal polygons with the minimum number of

r

-stars; an orthogonal polygon is an

r

-star if it is star-shaped. The problem has been considered by Worman and Keil [

13

] who described an algorithm running in

$$O(n^{17} \hbox {poly-log}\, n)$$

time where

n

is the size of the input polygon.

In this paper, we consider the above problem on simple class-3 orthogonal polygons, i.e., orthogonal polygons that have dents along at most 3 different orientations. By taking advantage of geometric properties of these polygons, we give an output-sensitive

$$O(n + k \log k)$$

-time algorithm where

k

is the size of a minimum

r

-star cover; this is the first purely geometric algorithm for this problem. Ideas in this algorithm may be generalized to yield faster algorithms for the problem on general simple orthogonal polygons.

The dilation of an embedding is defined as the maximum distance between pairs of vertices of host graph that are images of adjacent vertices of guest graph. An embedding with a long dilation faces many problems, such as long communication delay, coupling problems and the existence of different types of uncontrolled noise. In this paper, we compute the minimum dilation of embedding circulant networks into butterfly and benes networks.

This paper provides the first solution to the kinetic reverse

k

-nearest neighbor (R

$$k$$

NN) problem in

$$\mathbb {R}^d$$

, which is defined as follows: Given a set

P

of

n

moving points in arbitrary but fixed dimension

d

, an integer

k

, and a query point

$$q\notin P$$

at any time

t

, report all the points

$$p\in P$$

for which

q

is one of the

k

-nearest neighbors of

p

.

The problem of listing the

K

shortest simple (loopless)

st

-paths in a graph has been studied since the early 1960s. For a non-negatively weighted graph with

n

vertices and

m

edges, the most efficient solution is an

$$O(K(mn + n^2 \log n))$$

algorithm for directed graphs by Yen and Lawler [Management Science, 1971 and 1972], and an

$$O(K(m+n \log n))$$

algorithm for the undirected version by Katoh

et

al.

[Networks, 1982], both using

$$O(Kn + m)$$

space. In this work, we consider a different parameterization for this problem: instead of bounding the number of

st

-paths output, we bound their length. For the bounded length parameterization, we propose new non-trivial algorithms matching the time complexity of the classic algorithms but using only

$$O(m+n)$$

space. Moreover, we provide a unified framework such that the solutions to both parameterizations – the classic

K

-shortest and the new length-bounded paths – can be seen as two different traversals of a same tree, a Dijkstra-like and a DFS-like traversal, respectively.

A set of vertices

S

resolves a graph

G

if every vertex is uniquely determined by its vector of distances to the vertices in

S

. The metric dimension of

G

is the minimum cardinality of a resolving set of

G

.

Let

$$\{G_1, G_2, \ldots , G_n\}$$

be a finite collection of graphs and each

$$G_i$$

has a fixed vertex

$$v_{0_i}$$

or a fixed edge

$$e_{0_i}$$

called a terminal vertex or edge, respectively. The

vertex-amalgamation

of

$$G_1, G_2, \ldots , G_n$$

, denoted by

$$Vertex-Amal\{G_i;v_{0_i}\}$$

, is formed by taking all the

$$G_i$$

’s and identifying their terminal vertices. Similarly, the

edge-amalgamation

of

$$G_1, G_2, \ldots , G_n$$

, denoted by

$$Edge-Amal\{G_i;e_{0_i}\}$$

, is formed by taking all the

$$G_i$$

’s and identifying their terminal edges.

Here we study the metric dimensions of vertex-amalgamation and edge-amalgamation for finite collection of arbitrary graphs. We give lower and upper bounds for the dimensions, show that the bounds are tight, and construct infinitely many graphs for each possible value between the bounds.

In this paper we study the structure of suffix trees. Given an unlabeled tree

$$\tau $$

on

n

nodes and suffix links of its internal nodes, we ask the question “Is

$$\tau $$

a suffix tree?", i.e., is there a string

S

whose suffix tree has the same topological structure as

$$\tau $$

? We place no restrictions on

S

, in particular we do not require that

S

ends with a unique symbol. This corresponds to considering the more general definition of

implicit

or

extended

suffix trees. Such general suffix trees have many applications and are for example needed to allow efficient updates when suffix trees are built online. We prove that

$$\tau $$

is a suffix tree if and only if it is realized by a string

S

of length

$$n-1$$

, and we give a linear-time algorithm for inferring

S

when the first letter on each edge is known. This generalizes the work of I et al. [Discrete Appl. Math. 163, 2014].

A feedback vertex set

F

of an undirected graph

G

is a vertex subset of

G

whose removal results in a forest. Such a set

F

is said to be independent if

F

forms an independent set of

G

. In this paper, we study the problem of finding an independent feedback vertex set of a given graph with the minimum number of vertices, from the viewpoint of graph classes. This problem is NP-hard even for planar bipartite graphs of maximum degree four. However, we show that the problem is solvable in linear time for graphs having tree-like structures, more specifically, for bounded treewidth graphs, chordal graphs and cographs. We then give a fixed-parameter algorithm for planar graphs when parameterized by the solution size. Such a fixed-parameter algorithm is already known for general graphs, but our algorithm is exponentially faster than the known one.

We address the problem of approximate pattern matching using the Levenshtein distance. Given a text

T

and a pattern

P

, find all locations in

T

that differ by at most

k

errors from

P

. For that purpose, we propose a filtration algorithm that is based on a novel type of seeds, combining exact parts and parts with a fixed number of errors. Experimental tests show that the method is specifically well-suited for short patterns with a large number of errors.