Algorithms and Computation

Three types of geometric structure—grid triangulations, rectangular subdivisions, and orthogonal polyhedra—can each be described combinatorially by a

regular labeling

: an assignment of colors and orientations to the edges of an associated maximal or near-maximal planar graph. We briefly survey the connections and analogies between these three kinds of labelings, and their uses in designing efficient geometric algorithms.

We survey some recent progress in the design of efficient protocols for secure computation and communication, in a variety of cryptographic settings. The common thread is the usefulness of interesting algorithmic methods originally developed for non-cryptographic applications. We also present some intriguing open problems for which new algorithmic ideas may be needed.

We study fixed parameter algorithms for three problems: Kemeny rank aggregation, feedback arc set tournament, and betweenness tournament. For Kemeny rank aggregation we give an algorithm with runtime

$O^*(2^{O(\sqrt{OPT})})$

, where

n

is the number of candidates,

$OPT \le \binom{n}{2}$

is the cost of the optimal ranking, and

O

*

(·) hides polynomial factors. This is a dramatic improvement on the previously best known runtime of

O

*

(2

O

(

OPT

)

). For feedback arc set tournament we give an algorithm with runtime

$O^*(2^{O(\sqrt{OPT})})$

, an improvement on the previously best known

$O^*(OPT^{O(\sqrt{OPT})})$

[4]. For betweenness tournament we give an algorithm with runtime

$O^*(2^{O(\sqrt{OPT/n})})$

, where

n

is the number of vertices and

$OPT \le \binom{n}{3}$

is the optimal cost. This improves on the previously known

$O^*(OPT^{O(OPT^{1/3})})$

[28], especially when

OPT

is small. Unusually we can solve instances with

OPT

as large as

n

(log

n

)

2

in polynomial time!

Given a graph with edge lengths and a set of pairs of vertices which should be connected (requirements) the Generalized Steiner Tree Problem (GSTP) asks for a minimum length subgraph that connects every requirement. For the Generalized Steiner Tree Problem restricted to complete graphs with edge lengths 1 and 2, we provide a 1.5-approximation algorithm. It is the first algorithm with the approximation ratio significantly better than 2 for a class of graphs for which GSTP is MAX SNP-hard.

We consider the question of finding an approximate period in a given string

S

of length

n

. Let

S

′ be a periodic string closest to

S

under some distance metric. We consider this distance the error of the periodic string, and seek the smallest period that generates a string with this distance to

S

. In this paper we consider the

Hamming

and

swap

distance metrics. In particular, if

S

is the given string, and

S

′ is the closest periodic string to

S

under the Hamming distance, and if that distance is

k

, we develop an

O

(

nk

loglog

n

) algorithm that constructs the smallest period that defines such a periodic string

S

′. We call that string the approximate period of

S

under the Hamming distance. We further develop an

O

(

n

2

) algorithm that constructs the approximate period under the swap distance. Finally, we show an

O

(

n

log

n

) algorithm for finite alphabets, and

O

(

n

log

3

n

) algorithm for infinite alphabets, that approximates the number of mismatches in the approximate period of the string.

Let

G

be a geometric graph whose vertex set

S

is a set of

n

points in ℝ

d

. The stretch factor of two distinct points

p

and

q

in

S

is the ratio of their shortest-path distance in

G

and their Euclidean distance. We consider the problem of approximating the sum of all

$n \choose 2$

stretch factors determined by all pairs of points in

S

. We show that for paths, cycles, and trees, this sum can be approximated, within a factor of 1 + 

ε

, in

O

(

n

polylog

(

n

)) time. For plane graphs, we present a (2 + 

ε

)-approximation algorithm with running time

O

(

n

5/3

polylog

(

n

)), and a (4 + 

ε

)-approximation algorithm with running time

O

(

n

3/2

polylog

(

n

)).

We study the Boolean Satisfiability Problem (SAT) restricted on input formulas for which there are linear arithmetic constraints imposed on

the indices of variables occurring in the same clause

. This can be seen as a structural counterpart of Schaefer’s dichotomy theorem which studies the SAT problem with additional constraints on

the assigned values of variables in the same clause

. More precisely, let

k

-SAT(

$m,\mathcal{A}$

) denote the SAT problem restricted on instances of

k

-CNF formulas, in every clause of which the indices of the last

k

 − 

m

variables are totally decided by the first

m

ones through some linear equations chosen from

$\mathcal{A}$

. For example, if

$\mathcal{A}$

contains

i

3

 = 

i

1

 + 2

i

2

and

i

4

 = 

i

2

 − 

i

1

 + 1, then a clause of the input to 4-SAT(

$2,\mathcal{A}$

) has the form

$y_{i_1}\lor y_{i_2} \lor y_{i_1+2i_2} \lor y_{i_2-i_1+1}$

, with

y

i

being

x

i

or

$\overline{x_i}$

. We obtain the following results:

1

If

m

 ≥ 2, then for any set

$\mathcal{A}$

of linear constraints, the restricted problem

k

-SAT

$(m,\mathcal{A})$

is either in

P

or

NP

-complete assuming

P

 ≠ 

NP

. Moreover, the corresponding #SAT problem is always #

P

-complete, and the

Max

-SAT problem does not allow a polynomial time approximation scheme assuming

P

 ≠ 

NP

.

2

m

 = 1, that is, in every clause only one index can be chosen freely. In this case, we develop a general framework together with some techniques for designing polynomial-time algorithms for the restricted SAT problems. Using these, we prove that for any

$\mathcal{A}$

, #2

-SAT

$(1,\mathcal{A})$

and

Max

-2-SAT

$(1,\mathcal{A})$

are both polynomial-time solvable, which is in sharp contrast with the hardness results of general #2

-SAT

and

Max

-2-SAT. For fixed

k

 ≥ 3, we obtain a large class of non-trivial constraints

$\mathcal{A}$

, under which the problems

k

-SAT

$(1,\mathcal{A})$

, #

k

-SAT

$(1,\mathcal{A})$

and

Max

-

k

-SAT

$(1,\mathcal{A})$

can all be solved in polynomial time or quasi-polynomial time.

In this paper, we consider the problem of predicate encryption and focus on the predicate for testing whether the Hamming distance between the attribute

X

of a data item and a target

V

is equal to (or less than) a threshold

t

where

X

and

V

are of length

m

. Existing solutions either do not provide attribute protection or produce a big ciphertext of size

O

(2

m

). For the equality version of the problem, we provide a scheme which is match-concealing (MC) secure and the sizes of the ciphertext and token are both

O

(

m

). For the inequality version of the problem, we give a practical scheme, also achieving MC security, which produces a ciphertext with size

$O(m^{t_{max}})$

if the maximum value of

t

,

t

max

, is known in advance and is a constant. We also show how to update the ciphertext if the user wants to increase

t

max

without constructing the ciphertext from scratch.

This pager gives a new randomized algorithm which solves 3-SAT in time

O

(1.32113

n

). The previous best bound is

O

(1.32216

n

) due to Rolf (J. SAT, 2006). The new algorithm uses the same approach as Iwama and Tamaki (SODA 2004), but exploits the non-uniform initial assignment due to Hofmeister et al. (STACS 2002) against the Schöning’s local search (FOCS 1999).

The counterfeit coin problem requires us to find all false coins from a given bunch of coins using a balance scale. We assume that the balance scale gives us only “balanced” or “tilted” information and that we know the number

k

of false coins in advance. The balance scale can be modeled by a certain type of oracle and its query complexity is a measure for the cost of weighing algorithms (the number of weighings). In this paper, we study the quantum query complexity for this problem. Let

Q

(

k

,

N

) be the quantum query complexity of finding all

k

false coins from the

N

given coins. We show that for any

k

and

N

such that

k

 < 

N

/2,

Q

(

k

,

N

) = 

O

(

k

1/4

), contrasting with the classical query complexity, Ω(

k

log(

N

/

k

)), that depends on

N

. So our quantum algorithm achieves a

quartic

speed-up for this problem. We do not have a matching lower bound, but we show some evidence that the upper bound is tight: any algorithm, including our algorithm, that satisfies certain properties needs Ω(

k

1/4

) queries.

We describe a data structure, called a

priority range tree

, which accommodates fast orthogonal range reporting queries on prioritized points. Let

S

be a set of

n

points in the plane, where each point

p

in

S

is assigned a weight

w

(

p

) that is polynomial in

n

, and define the rank of

p

to be

$r(p)=\lfloor \log w(p) \rfloor$

. Then the priority range tree can be used to report all points in a three- or four-sided query range

R

with rank at least

$\lfloor \log w \rfloor$

in time

O

(log

W

/

w

 + 

k

), and report

k

highest-rank points in

R

in time

O

(loglog

n

 + log

W

/

w

′ + 

k

), where

W

 = ∑ 

p

 ∈ 

S

w

(

p

),

w

′ is the smallest weight of any point reported, and

k

is the output size. All times assume the standard RAM model of computation. If the query range of interest is three sided, then the priority range tree occupies

O

(

n

) space, otherwise

O

(

n

log

n

) space is used to answer four-sided queries. These queries are motivated by the Weber–Fechner Law, which states that humans perceive and interpret data on a logarithmic scale.

In this paper we study the question of whether or not a static search tree should ever be unbalanced. We present several methods to restructure an unbalanced k-ary search tree

T

into a new tree

R

that preserves many of the properties of

T

while having a height of log

k

n

 + 1 which is one unit off of the optimal height. More specifically, we show that it is possible to ensure that the depth of the elements in

R

is no more than their depth in

T

plus at most log

k

log

k

n

 + 2. At the same time it is possible to guarantee that the average access time

P

(

R

) in tree

R

is no more than the average access time

P

(

T

) in tree

T

plus

O

(log

k

P

(

T

)). This suggests that for most applications, a balanced tree is always a better option than an unbalanced one since the balanced tree has similar average access time and much better worst case access time.

In this paper, we address the shortest path query problem, i.e., constructing a data structure of a given network to answer the shortest path length of two given points in a short time. We present a method named Levelwise Mesh Sparsification for the problem. The key idea is to divide the network into meshes and to sparsify the network in each mesh by removing unnecessary edges and vertices that are never used when the shortest path passes through the mesh. In large real-world road networks in the United States, our method is about 1,500 times faster than Dijkstra’s algorithm, which is competitive with existing methods. The time taken to construct the data structure is a few hours on a typical PC. Unlike previous methods, our geometric partition method succeeded in reducing the data for connecting the sparsified network. As a result, our method uses additional data that is only about 10% of the original data size, while existing methods use more than 2000%. Our method has considerable extensibility because it is independent of search algorithms. Thus, it can be used with Dijkstra’s algorithm and A*-search among others, and with several models such as negative costs, time-dependent costs, and so on. These are rarely handled by previous methods.

New data structures are presented for very fast predecessor queries on integer data sets stored on multiple disks. A structure is presented that supports predecessor queries in one disk seek performed in parallel over multiple disks, no matter how large the data set. For truly massive data sets, the space requirement of this structure approaches twice the space needed to simply store the data on disk.

A second structure is presented that supports predecessor queries in the time it takes to perform two disk seeks, but has more moderate space requirements. Its space usage approaches the space needed to store the data on disk, and has manageable space requirements for smaller massive data sets.

We consider an extension of the

popular matching

problem in this paper. The input to the popular matching problem is a bipartite graph

$G = (\mathcal{A} \cup \mathcal{B},E)$

, where

$\mathcal{A}$

is a set of people,

$\mathcal{B}$

is a set of items, and each person

$a \in \mathcal{A}$

ranks a subset of items in an order of preference, with ties allowed. The popular matching problem seeks to compute a matching

M

*

between people and items such that there is no matching

M

where more people are happier with

M

than with

M

*

. Such a matching

M

*

is called a popular matching. However, there are simple instances where no popular matching exists.

Here we consider the following natural extension to the above problem: associated with each item

$b \in \mathcal{B}$

is a non-negative price

cost

(

b

), that is, for any item

b

, new copies of

b

can be added to the input graph by paying an amount of

cost

(

b

) per copy. When

G

does not admit a popular matching, the problem is to “augment”

G

at minimum cost such that the new graph admits a popular matching. We show that this problem is NP-hard; in fact, it is NP-hard to approximate it within a factor of

$\sqrt{n_1}/2$

, where

n

1

is the number of people. This problem has a simple polynomial time algorithm when each person has a preference list of length at most 2. However, if we consider the problem of

constructing

a graph at minimum cost that admits a popular matching that matches all people, then even with preference lists of length 2, the problem becomes NP-hard. However, when the number of copies of each item is

fixed

, the problem of computing a minimum cost popular matching or deciding that no popular matching exists can be solved in

O

(

mn

1

) time.

We study line systems in metric spaces induced by graphs. A line is a subset of vertices defined by a relation of betweenness.

We show that the class of all graphs having exactly

k

different lines is infinite if and only if it contains a graph with a bridge. We also study lines in random graphs—a random graph almost surely has

$n \choose 2$

different lines and no line containing all the vertices.

We call a pair of graphs isolinear if their line systems are isomorphic. We prove that deciding isolinearity of graphs is polynomially equivalent to the Graph Isomorphism Problem.

Similarly to the Graph Reconstruction Problem, we question the reconstructability of graphs from their line systems. We present a polynomial-time algorithm which constructs a tree from a given line system. We give an application of line systems: This algorithm can be extended to decide the existence of an embedding of a metric space into a tree metric and to construct this embedding if it exists.

The concept of neighbor system, introduced by Hartvigsen (2009), is a set of integral vectors satisfying a certain combinatorial property. In this paper, we reveal the relationship of neighbor systems with jump systems and with bisubmodular polyhedra. We firstly prove that for every neighbor system, there exists a jump system which has the same neighborhood structure as the original neighbor system. This shows that the concept of neighbor system is essentially equivalent to that of jump system. We next show that the convex closure of a neighbor system is an integral bisubmodular polyhedron. In addition, we give a characterization of neighbor systems using bisubmodular polyhedra. Finally, we consider the problem of minimizing a separable convex function on a neighbor system. By using the relationship between neighbor systems and jump systems shown in this paper, we prove that the problem can be solved in weakly-polynomial time for a class of neighbor systems.

Given a multiset

M

 = 

V

1

 ∪ 

V

2

 ∪ ⋯ ∪ 

V

C

of

n

elements and a capacity function Δ: [1,

C

]→[2,

n

 − 1], we consider the problem of enumerating all unrooted trees

T

on

M

such that the degree of each vertex

v

 ∈ 

V

i

is bounded from above by Δ(

i

). The problem has a direct application of enumerating isomers of tree-like chemical graphs. We give an algorithm that generates all such trees without duplication in

O

(1)-time delay per output in the worst case using

O

(

n

) space, with

O

(

n

) initial preprocessing time.

A permutation graph is an intersection graph of segments lying between two parallel lines. A Seidel complementation of a finite graph at a vertex

v

consists in complementing the edges between the neighborhood and the non-neighborhood of

v

. Two graphs are

Seidel complement

equivalent if one can be obtained from the other by a sequence of

Seidel complementations

.

In this paper we introduce the new concept of

Seidel complementation

and

Seidel minor

. We show that this operation preserves cographs and the structure of modular decomposition.

The main contribution of this paper is to provide a new and succinct characterization of permutation graphs namely, a graph is a permutation graph if and only if it does not contain any of the following graphs:

C

5

,

C

7

,

$XF_{6}^{2}$

,

$XF_{5}^{2n+3}$

,

$C_{2n}, n\geqslant6$

and their complements as a Seidel minor. This characterization is in a sense similar to Kuratowski’s characterization [Kur30] of planar graphs by forbidden topological minors.

In a recent paper, we introduced the simultaneous representation problem (defined for any graph class

$\cal C$

) and studied the problem for chordal, comparability and permutation graphs. For interval graphs, the problem is defined as follows. Two interval graphs

G

1

and

G

2

, sharing some vertices

I

(and the corresponding induced edges), are said to be “simultaneous interval graphs” if there exist interval representations

R

1

and

R

2

of

G

1

and

G

2

, such that any vertex of

I

is mapped to the same interval in both

R

1

and

R

2

. Equivalently,

G

1

and

G

2

are simultaneous interval graphs if there exist edges

E

′ between

G

1

 − 

I

and

G

2

 − 

I

such that

G

1

 ∪ 

G

2

 ∪ 

E

′ is an interval graph.

Simultaneous representation problems are related to simultaneous planar embeddings, and have applications in any situation where it is desirable to consistently represent two related graphs, for example: interval graphs capturing overlaps of DNA fragments of two similar organisms; or graphs connected in time, where one is an updated version of the other.

In this paper we give an

O

(

n

2

log

n

) time algorithm for recognizing simultaneous interval graphs, where

n

 = |

G

1

 ∪ 

G

2

|. This result complements the polynomial time algorithms for recognizing probe interval graphs and provides an efficient algorithm for the interval graph sandwich problem for the special case where the set of optional edges induce a complete bipartite graph.

We investigate the unbalanced cut problems. A cut (

A

,

B

) is called

unbalanced

if the size of its smaller side is at most

k

(called

k

-size) or exactly

k

(called E

k

-size), where

k

is an input parameter. An

s

-

t

cut (

A

,

B

) is called unbalanced if its

s

-side is of

k

-size or E

k

-size. We consider three types of unbalanced cut problems, in which the quality of a cut is measured with respect to the capacity, the sparsity, and the conductance, respectively.

We show that even if the input graph is restricted to be a tree, the E

k

-Sparsest Cut problem (to find an E

k

-size cut with the minimum sparsity) is still

NP

-hard. We give a bicriteria approximation algorithm for the

k

-Sparsest Cut problem (to find a

k

-size cut with the minimum sparsity), which outputs a cut whose sparsity is at most

O

(log

n

) times the optimum and whose smaller side has size at most

O

(log

n

)

k

. As a consequence, this leads to a (

O

(log

n

),

O

(log

n

))-approximation algorithm for the Min

k

-Conductance problem (to find a

k

-size cut with the minimum conductance). We also prove that the Min

k

-Size

s

-

t

Cut problem is

NP

-hard and give an

O

(log

n

)-approximation algorithm for it.

It has been conjectured by Golumbic and Monma in 1984 that the intersection of tolerance and cocomparability graphs coincides with bounded tolerance graphs. Since cocomparability graphs can be efficiently recognized, a positive answer to this conjecture in the general case would enable us to efficiently distinguish between tolerance and bounded tolerance graphs, although it is NP-complete to recognize each of these classes of graphs separately. The conjecture has been proved under some – rather strong –

structural

assumptions on the input graph; in particular, it has been proved for complements of trees, and later extended to complements of bipartite graphs, and these are the only known results so far. Furthermore, it is known that the intersection of tolerance and cocomparability graphs is contained in the class of trapezoid graphs. In this article we prove that the above conjecture is true for every graph

G

, whose tolerance representation satisfies a slight assumption; note here that this assumption concerns only the given tolerance

representation

R

of

G

, rather than

any

structural property of

G

. This assumption on the representation is guaranteed by a wide variety of graph classes; for example, our results immediately imply the correctness of the conjecture for complements of triangle-free graphs (which also implies the above-mentioned correctness for complements of bipartite graphs). Our proofs are algorithmic, in the sense that, given a tolerance representation

R

of a graph

G

, we describe an algorithm to transform

R

into a bounded tolerance representation

R

 ∗ 

of

G

. Furthermore, we conjecture that any minimal tolerance graph

G

that is not a bounded tolerance graph, has a tolerance representation with exactly one unbounded vertex. Our results imply the non-trivial result that, in order to prove the conjecture of Golumbic and Monma, it suffices to prove our conjecture. In addition, there already exists evidence in the literature that our conjecture is true.

We study the maximum flow problem in directed

H

-minor-free graphs where

H

can be drawn in the plane with one crossing. If a structural decomposition of the graph as a clique-sum of planar graphs and graphs of constant complexity is given, we show that a maximum flow can be computed in

O

(

n

log

n

) time. In particular, maximum flows in directed

K

3,3

-minor-free graphs and directed

K

5

-minor-free graphs can be computed in

O

(

n

log

n

) time without additional assumptions.

We explore the intricate interdependent relationship among counting problems, considered from three frameworks for such problems: Holant Problems, counting CSP and weighted

H

-colorings. We consider these problems for general complex valued functions that take Boolean inputs. We show that results from one framework can be used to derive results in another, and this happens in both directions. Holographic reductions discover an underlying unity, which is only revealed when these counting problems are investigated in the complex domain ℂ. We prove three complexity dichotomy theorems, leading to a general theorem for Holant

c

problems. This is the natural class of Holant problems where one can assign constants 0 or 1. More specifically, given any signature grid on

G

 = (

V

,

E

) over a set ℱ of symmetric functions, we completely classify the complexity to be in P or #P-hard, according to ℱ, of

$$\sum_{\sigma: E \rightarrow \{0,1\}} \prod_{v\in V} f_v(\sigma\mid_{E(v)}),$$

where

f

v

 ∈ ℱ

$\cup \{\mbox{{\bf 0}, {\bf 1}}\}$

(

0

,

1

are the unary constant 0, 1 functions). Not only is holographic reduction the main tool, but also the final dichotomy is naturally stated in the language of holographic transformations. The proof goes through another dichotomy theorem on Boolean complex weighted #CSP.

We consider the problem of finding a sparse multiple of a polynomial. Given

f

 ∈ 

F

[

x

] of degree

d

, and a desired sparsity

t

, our goal is to determine if there exists a multiple

h

 ∈ 

F

[

x

] of

f

such that

h

has at most

t

non-zero terms, and if so, to find such an

h

. When

F

=ℚ and

t

is constant, we give a polynomial-time algorithm in

d

and the size of coefficients in

h

. When

F

is a finite field, we show that the problem is at least as hard as determining the multiplicative order of elements in an extension field of

F

(a problem thought to have complexity similar to that of factoring integers), and this lower bound is tight when

t

 = 2.

Abstract geometrical computation can solve NP-complete problems efficiently: any boolean constraint satisfaction problem, instance of SAT, can be solved in bounded space and time with simple geometrical constructions involving only drawing parallel lines on a Euclidean space-time plane. Complexity as the maximal length of a sequence of consecutive segments is quadratic. The geometrical algorithm achieves massive parallelism: an exponential number of cases are explored simultaneously. The construction relies on a fractal pattern and requires the same amount of space and time independently of the SAT formula.

We study polynomial time complexity of type 2 functionals. For that purpose, we introduce a first order functional stream language. We give criteria, named well-founded, on such programs relying on second order interpretation that characterize two variants of type 2 polynomial complexity including the Basic Feasible Functions (BFF). These characterizations provide a new insight on the complexity of stream programs. Finally, we adapt these results to functions over the reals, a particular case of type 2 functions, and we provide a characterization of polynomial time complexity in Recursive Analysis.

A Boolean function

f

:{1, − 1}

n

→{1, − 1} is said to be sign-represented by a real polynomial

$p:{\mathbb R}^n \rightarrow {\mathbb R}$

if sgn(

p

(

x

)) = 

f

(

x

) for all

x

 ∈ {1, − 1}

n

. The PTF density of

f

is the minimum number of monomials in a polynomial that sign-represents

f

. It is well known that every

n

-variable Boolean function has PTF density at most 2

n

. However, in general, less monomials are enough. In this paper, we present a method that reduces the problem of upper bounding the average PTF density of

n

-variable Boolean functions to the computation of (some modified version of) average PTF density of

k

-variable Boolean functions for small

k

. By using this method, we show that almost all

n

-variable Boolean functions have PTF density at most (0.617) 2

n

, which is the best upper bound so far.

Let

S

be a set of

n

points in ℝ

d

. A graph

G

 = (

S

,

E

) is called a

t

-spanner for

S

, if for any two points

p

and

q

in

S

, the shortest-path distance in

G

between

p

and

q

is at most

t

|

pq

|, where |

pq

| denotes the Euclidean distance between

p

and

q

. The graph

G

is called

θ

-angle-constrained, if any two distinct edges sharing an endpoint make an angle of at least

θ

. It is shown that, for any

θ

with 0 < 

θ

 < 

π

/3, a

θ

-angle-constrained

t

-spanner can be computed in

O

(

n

log

n

) time, where

t

depends only on

θ

.

In this paper, we consider the problem of computing a minimum bending energy path (or MinBEP) in a simple corridor. Given a simple 2D corridor

C

bounded by straight line segments and arcs of radius 2

r

, the MinBEP problem is to compute a path

P

inside

C

and crossing two pre-specified points

s

and

t

located at each end of

C

so that the bending energy of

P

is minimized. For this problem, we first show how to lower bound the bending energy of an optimal curve with bounded curvature, and then use this lower bound to design a (1 + 

ε

)-approximation algorithm for this restricted version of the MinBEP problem. Our algorithm is based on a number of interesting geometric observations and approximation techniques on smooth curves, and can be easily implemented for practical purpose. It is the first algorithm with a guaranteed performance ratio for the MinBEP problem.

Hybridizations of evolutionary algorithms and local search are among the best-performing algorithms for vertex coloring. However, the theoretical knowledge about these algorithms is very limited and it is agreed that a solid theoretical foundation is needed. We consider an iterated local search algorithm that iteratively tries to improve a coloring by applying mutation followed by local search. We investigate the capabilities and the limitations of this approach using bounds on the expected number of iterations until an optimal or near-optimal coloring is found. This is done for two different mutation operators and for different graph classes: bipartite graphs, sparse random graphs, and planar graphs.

In a bounded max-coloring of a vertex/edge weighted graph, each color class is of cardinality at most

b

and of weight equal to the weight of the heaviest vertex/edge in this class. The bounded max-vertex/edge-coloring problems ask for such a coloring minimizing the sum of all color classes’ weights. These problems generalize the well known max-coloring problems by taking into account the number of available resources (colors) in practical applications. In this paper we present complexity results and approximation algorithms for the bounded max-coloring problems on general graphs, bipartite graphs and trees.

In this paper we initiate an algorithmic study of B

oxicity

, a combinatorially well studied graph invariant, from the viewpoint of parameterized algorithms. The boxicity of an arbitrary graph

G

with the vertex set

V

(

G

) and the edge set

E

(

G

), denoted by box(

G

), is the minimum number of interval graphs on the same set of vertices such that the intersection of the edge sets of the interval graphs is

E

(

G

). In the B

oxicity

problem we are given a graph

G

together with a positive integer

k

, and asked whether the box(

G

) is at most

k

. The problem is notoriously hard and is known to be

NP

-complete even to determine whether the boxicity of a graph is at most two. This rules out any possibility of having an algorithm with running time |

V

(

G

)|

O

(

f

(

k

))

, where

f

is an arbitrary function depending on

k

alone. Thus we look for other structural parameters like “vertex cover number” and “max leaf number” and see its effect on the problem complexity. In particular, we give an algorithm that given a vertex cover of size

k

finds box(

G

) in time

$2^{O(2^k k^2)}|V(G)|$

. We also give a faster additive one approximation algorithm for finding box(

G

) that given a graph with vertex cover of size

k

runs in time

$2^{O(k^2 \log k)}|V(G)|$

. Our next result is an additive two approximation algorithm for B

oxicity

when parameterized by the max leaf number running in time

$2^{O(k^3\log k)}|V(G)|^{O(1)}$

. Our results are based on structural relationships between boxicity and the corresponding parameter and could be of independent interest.

We study the NP-complete

Target Set Selection

(

TSS

) problem occurring in social network analysis. Complementing results on its approximability and extending results for its restriction to trees and bounded treewidth graphs, we classify the influence of the parameters “diameter”, “cluster edge deletion number”, “vertex cover number”, and “feedback edge set number” of the underlying graph on the problem’s complexity, revealing both tractable and intractable cases. For instance, even for diameter-two split graphs

TSS

remains very hard.

TSS

can be efficiently solved on graphs with small feedback edge set number and also turns out to be fixed-parameter tractable when parameterized by the vertex cover number, both results contrasting known parameterized intractability results for the parameter treewidth. While these tractability results are relevant for sparse networks, we also show efficient fixed-parameter algorithms for the parameter cluster edge deletion number, yielding tractability for certain dense networks.

We explore opportunities for parameterising constant factor approximation algorithms for vertex cover. We provide a simple algorithm that works on any approximation ratio of the form

$\frac {2l+1}{l+1}$

and has complexity that outperforms an algorithm by Bourgeois et al. derived from a sophisticated exact parameterised algorithm. In particular, for

l

 = 1 (factor 1.5 approximation) our algorithm runs in time

$\mathcal{O}^{*}(1.09^{k})$

. Additionally, we present an improved polynomial-time approximation algorithm for graphs of average degree four.

The

degeneracy

of an

n

-vertex graph

G

is the smallest number

d

such that every subgraph of

G

contains a vertex of degree at most

d

. We show that there exists a nearly-optimal fixed-parameter tractable algorithm for enumerating all maximal cliques, parametrized by degeneracy. To achieve this result, we modify the classic Bron–Kerbosch algorithm and show that it runs in time

O

(

dn

3

d

/3

). We also provide matching upper and lower bounds showing that the largest possible number of maximal cliques in an

n

-vertex graph with degeneracy

d

(when

d

is a multiple of 3 and

n

 ≥ 

d

 + 3) is (

n

 − 

d

)3

d

/3

. Therefore, our algorithm matches the Θ(

d

(

n

 − 

d

)3

d

/3

) worst-case output size of the problem whenever

n

 − 

d

 = Ω(

n

).

Howard’s policy iteration algorithm is one of the most widely used algorithms for finding optimal policies for controlling

Markov Decision Processes

(MDPs). When applied to weighted directed graphs, which may be viewed as

Deterministic

MDPs (DMDPs), Howard’s algorithm can be used to find Minimum Mean-Cost cycles (MMCC). Experimental studies suggest that Howard’s algorithm works extremely well in this context. The theoretical complexity of Howard’s algorithm for finding MMCCs is a mystery. No polynomial time bound is known on its running time. Prior to this work, there were only linear lower bounds on the number of iterations performed by Howard’s algorithm. We provide the first weighted graphs on which Howard’s algorithm performs Ω(

n

2

) iterations, where

n

is the number of vertices in the graph.

We consider the Steiner tree problem under a 2-stage stochastic model with recourse and finitely many scenarios (SSTP). Thereby, edges are purchased in the first stage when only probabilistic information on the set of terminals and the future edge costs is known. In the second stage, one of the given scenarios is realized and additional edges are purchased to interconnect the set of (now known) terminals. The goal is to choose an edge set to be purchased in the first stage while minimizing the overall expected cost of the solution.

We provide a new semi-directed cut-set based integer programming formulation that is stronger than the previously known undirected model. To solve the formulation to provable optimality, we suggest a two-stage branch-and-cut framework, facilitating (integer) L-shaped cuts. The framework itself is also applicable to a range of other stochastic problems.

As SSTP has yet been investigated only from the theoretical point of view, we also present the first computational study for SSTP, showcasing the applicability of our approach and its benefits over solving the extensive form of the deterministic equivalent directly.

The single maximum coverage location problem is as follows. We are given an edge-weighted tree with customers located at the nodes. Each node

u

is associated with a demand

w

(

u

) and a radius

r

(

u

). The goal is to find, for some facility, a node

x

such that the total demand of customers

u

whose distance to

x

is at most

r

(

u

) is maximized.

We give a simple

O

(

n

log

n

) algorithm for this problem which improves upon the previously fastest algorithms. We complement this result by an Ω(

n

log

n

) lower bound showing that our algorithm is optimal.

We observe that our algorithm leads also to improved time bounds for several other location problems such as indirect covering subtree and certain competitive location problems. Finally, we outline how our algorithm can be extended to a large class of distance-based location problems.

Given a digraph

G

 = (

VG

,

AG

), an

even factor

M

 ⊆ 

AG

is a subset of arcs that decomposes into a collection of node-disjoint paths and even cycles. Even factors in digraphs were introduced by Geelen and Cunningham and generalize path matchings in undirected graphs.

Finding an even factor of maximum cardinality in a general digraph is known to be NP-hard but for the class of

odd-cycle symmetric

digraphs the problem is polynomially solvable. So far, the only combinatorial algorithm known for this task is due to Pap; its running time is

O

(

n

4

) (hereinafter

n

stands for the number of nodes in

G

).

In this paper we present a novel

sparse recovery

technique and devise an

O

(

n

3

log

n

)-time algorithm for finding a maximum cardinality even factor in an odd-cycle symmetric digraph. This technique also applies to a wide variety of related problems.