# Algorithmica

### Line-Distortion, Bandwidth and Path-Length of a Graph

For a graph
\(G=(V,E)\)
the *minimum line-distortion problem* asks for the minimum *k* such that there is a mapping *f* of the vertices into points of the line such that for each pair of vertices *x*, *y* the distance on the line
\(|f(x) - f(y)|\)
can be bounded by the term
\(d_G(x, y)\le |f(x)-f(y)|\le k \, d_G(x, y)\)
, where
\(d_G(x, y)\)
is the distance in the graph. The *minimum bandwidth problem* minimizes the term
\(\max _{uv\in E}|f(u)-f(v)|\)
, where *f* is a mapping of the vertices of *G* into the integers
\(\{1, \ldots , n\}\)
. We investigate the minimum line-distortion and the minimum bandwidth problems on unweighted graphs and their relations with the *minimum length* of a Robertson–Seymour’s path-decomposition. The *length* of a path-decomposition of a graph is the largest diameter of a bag in the decomposition. The *path-length* of a graph is the minimum length over all its path-decompositions. In particular, we show:

there is a simple polynomial time algorithm that embeds an arbitrary unweighted input graph *G* into the line with distortion
\(\mathcal{O}(k^2)\)
, where *k* is the minimum line-distortion of *G*;

if a graph *G* can be embedded into the line with distortion *k*, then *G* admits a Robertson–Seymour’s path-decomposition with bags of diameter at most *k* in *G*;

for every class of graphs with path-length bounded by a constant, there exist an efficient constant-factor approximation algorithm for the minimum line-distortion problem and an efficient constant-factor approximation algorithm for the minimum bandwidth problem;

there is an efficient 2-approximation algorithm for computing the path-length of an arbitrary graph;

AT-free graphs and some intersection families of graphs have path-length at most 2;

for AT-free graphs, there exist a linear time 8-approximation algorithm for the minimum line-distortion problem and a linear time 4-approximation algorithm for the minimum bandwidth problem.

### Exact Algorithms for Minimum Weighted Dominating Induced Matching

Say that an edge of a graph *G* dominates itself and every other edge sharing a vertex of it. An edge dominating set of a graph
\(G=(V,E)\)
is a subset of edges
\(E' \subseteq E\)
which dominates all edges of *G*. In particular, if every edge of *G* is dominated by exactly one edge of
\(E'\)
then
\(E'\)
is a dominating induced matching. It is known that not every graph admits a dominating induced matching, while the problem to decide if it does admit it is NP-complete. In this paper we consider the problems of counting the number of dominating induced matchings and finding a minimum weighted dominating induced matching, if any, of a graph with weighted edges. We describe three exact algorithms for general graphs. The first runs in linear time for a given vertex dominating set of fixed size of the graph. The second runs in polynomial time if the graph admits a polynomial number of maximal independent sets. The third one is an
\(O^*(1.1939^n)\)
time and polynomial (linear) space, which improves over the existing algorithms for exactly solving this problem in general graphs.

### Evaluation of Monotone DNF Formulas

Stochastic boolean function evaluation (SBFE) is the problem of determining the value of a given boolean function *f* on an unknown input *x*, when each bit
\(x_i\)
of *x* can only be determined by paying a given associated cost
\(c_i\)
. Further, *x* is drawn from a given product distribution: for each
\(x_i\)
,
\(\mathbf{Pr}[x_i=1] = p_i\)
and the bits are independent. The goal is to minimize the expected cost of evaluation. In this paper, we study the complexity of the SBFE problem for classes of DNF formulas. We consider both exact and approximate versions of the problem for subclasses of DNF, for arbitrary costs and product distributions, and for unit costs and/or the uniform distribution.

### An FPTAS for the Volume Computation of 0-1 Knapsack Polytopes Based on Approximate Convolution

Computing high dimensional volumes is a hard problem, even for approximation. Several randomized approximation techniques for #P-hard problems have been developed in the three decades, while some deterministic approximation algorithms are recently developed only for a few #P-hard problems. Motivated by a new technique for a deterministic approximation, this paper is concerned with the *volume* computation of 0-1 *knapsack polytopes*, which is known to be #P-hard. This paper presents a new technique based on *approximate convolutions* for a *deterministic* approximation of volume computations, and provides a fully polynomial-time approximation scheme for the volume computation of 0-1 knapsack polytopes. We also give an extension of the result to multi-constrained knapsack polytopes with a constant number of constraints.

### A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs

The maximum stable set problem is NP-hard, even when restricted to triangle-free graphs. In particular, one cannot expect a polynomial time algorithm deciding if a bull-free graph has a stable set of size *k*, when *k* is part of the instance. Our main result in this paper is to show the existence of an FPT algorithm when we parameterize the problem by the solution size *k*. A polynomial kernel is unlikely to exist for this problem. We show however that our problem has a polynomial size Turing-kernel. More precisely, the hard cases are instances of size
\({O}(k^5)\)
. As a byproduct, if we forbid odd holes in addition to the bull, we show the existence of a polynomial time algorithm for the stable set problem. We also prove that the chromatic number of a bull-free graph is bounded by a function of its clique number and the maximum chromatic number of its triangle-free induced subgraphs. All our results rely on a decomposition theorem for bull-free graphs due to Chudnovsky which is modified here, allowing us to provide extreme decompositions, adapted to our computational purpose.

### Max-Throughput for (Conservative) k -of- n Testing

We define a variant of
\(k\)
-of-
\(n\)
testing that we call *conservative*
\(k\)
-of-
\(n\)
testing. We present a polynomial-time, combinatorial algorithm for the problem of maximizing throughput of conservative
\(k\)
-of-
\(n\)
testing, in a parallel setting. This extends previous work of Condon et al. and Kodialam who presented combinatorial algorithms for parallel pipelined filter ordering, which is the special case where
\(k=1\)
(or
\(k=n\)
). We also give a polynomial-time algorithm for maximizing throughput for *standard*
\(k\)
-of-
\(n\)
testing, based on the ellipsoid method, using previous techniques.

### Improved Approximation Algorithms for Projection Games

The projection games (aka Label Cover) problem is of great importance to the field of approximation algorithms, since most of the NP-hardness of approximation results we know today are reductions from Label Cover. In this paper we design several approximation algorithms for projection games: (1) A polynomial-time approximation algorithm that improves on the previous best approximation by Charikar et al. (Algorithmica 61(1):190–206, 2011). (2) A sub-exponential time algorithm with much tighter approximation for the case of smooth projection games. (3) A polynomial-time approximation scheme (PTAS) for projection games on planar graphs and a tight running time lower bound for such approximation schemes. The conference version of this paper had only the PTAS but not the running time lower bound.

### Approximating Maximum Agreement Forest on Multiple Binary Trees

Given a collection of phylogenetic trees on the same leaf label-set, the Maximum Agreement Forest problem (Maf) asks for a largest common subforest of these trees. The Maf problem on two binary phylogenetic trees has been studied extensively. In this paper, we are focused on the Maf problem on multiple (i.e., two or more) binary phylogenetic trees and present two polynomial-time approximation algorithms, one for the Maf problem on multiple rooted trees, and the other for the Maf problem on multiple unrooted trees. The ratio of our algorithm for the Maf problem on multiple rooted trees is 3, which is an improvement over the previous best ratio 8 for the problem. Our approximation algorithm of ratio 4 for the Maf problem on multiple unrooted trees is the first constant ratio approximation algorithm for the problem.

### Tight Bounds for Active Self-Assembly Using an Insertion Primitive

We prove two limits on the behavior of a model of self-assembling particles introduced by Dabby and Chen (Proceedings of 24th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1526–1536, 2013), called *insertion systems*, where monomers insert themselves into the middle of a growing linear polymer. First, we prove that the expressive power of these systems is equal to context-free grammars, answering a question posed by Dabby and Chen. Second, we prove that systems of *k* monomer types can deterministically construct polymers of length
\(n = 2^{\varTheta (k^{3/2})}\)
in
\(O(\log ^{5/3}(n))\)
expected time, and that this is optimal in both the number of monomer types and expected time.

### Logit Dynamics with Concurrent Updates for Local Interaction Potential Games

*Logit choice* dynamics constitute a family of randomized best response dynamics based on the *logit choice function* (McFadden in Frontiers in econometrics. Academic Press, New York, 1974) that models players with limited rationality and knowledge. In this paper we study the *all-logit dynamics* [also known as *simultaneous learning* (Alós-Ferrer and Netzer in Games Econ Behav 68(2):413–427, 2010)], where at *each* time step *all* players *concurrently* update their strategies according to the logit choice function. In the well studied *(one-)logit dynamics* (Blume in Games Econ Behav 5(3):387–424, 1993) instead at each step *only one* randomly chosen player is allowed to update. We study properties of the all-logit dynamics in the context of *local interaction potential games*, a class of games that has been used to model complex social phenomena (Montanari and Saberi 2009; Peyton in The economy as a complex evolving system. Oxford University Press, Oxford, 2003) and physical systems (Levin et al. in Probab Theory Relat Fields 146(1–2):223–265, 2010; Martinelli in Lectures on probability theory and statistics. Springer, Berlin, 1999). In a local interaction potential game players are the vertices of a *social graph* whose edges are two-player potential games. Each player picks one strategy to be played for all the games she is involved in and the payoff of the player is the sum of the payoffs from each of the games. We prove that local interaction potential games characterize the class of games for which the all-logit dynamics is reversible. We then compare the stationary behavior of one-logit and all-logit dynamics. Specifically, we look at the expected value of a notable class of observables, that we call *decomposable* observables. We prove that the difference between the expected values of the observables at stationarity for the two dynamics depends only on the *rationality* level
\(\beta \)
and on the distance of the social graph from a bipartite graph. In particular, if the social graph is bipartite then decomposable observables have the same expected value. Finally, we show that the mixing time of the all-logit dynamics has the same twofold behavior that has been highlighted in the case of the one-logit: for some games it exponentially depends on the rationality level
\(\beta \)
, whereas for other games it can be upper bounded by a function independent from
\(\beta \)
.

### Computing the Greedy Spanner in Linear Space

The greedy spanner is a high-quality spanner: its total weight, edge count and maximal degree are asymptotically optimal and in practice significantly better than for any other spanner with reasonable construction time. Unfortunately, all known algorithms that compute the greedy spanner on \(n\) points use \(\varOmega (n^2)\) space, which is impractical on large instances. To the best of our knowledge, the largest instance for which the greedy spanner was computed so far has about 13,000 vertices. We present a linear-space algorithm that computes the same spanner for points in \(\mathbb {R}^d\) running in \(O(n^2 \log ^2 n)\) time for any fixed stretch factor and dimension. We discuss and evaluate a number of optimizations to its running time, which allowed us to compute the greedy spanner on a graph with a million vertices. To our knowledge, this is also the first algorithm for the greedy spanner with a near-quadratic running time guarantee that has actually been implemented.

### Binary Jumbled Pattern Matching on Trees and Tree-Like Structures

Binary jumbled pattern matching asks to preprocess a binary string \(S\) in order to answer queries \((i,j)\) which ask for a substring of \(S\) that is of length \(i\) and has exactly \(j\) 1-bits. This problem naturally generalizes to vertex-labeled trees and graphs by replacing “substring” with “connected subgraph”. In this paper, we give an \(O(n^2 / \log ^2 n)\) -time solution for trees, matching the currently best bound for (the simpler problem of) strings. We also give an \({O}({g^{2 / 3} n^{4 / 3}/(\log n)^{4/3}})\) -time solution for strings that are compressed by a context-free grammar of size \(g\) in Chomsky normal form. This solution improves the known bounds when the string is compressible under many popular compression schemes. Finally, we prove that on graphs the problem is fixed-parameter tractable with respect to the treewidth \(w\) of the graph, even for a constant number of different vertex-labels, thus improving the previous best \(n^{O(w)}\) algorithm.

### The Compressed Annotation Matrix: An Efficient Data Structure for Computing Persistent Cohomology

Persistent homology with coefficients in a field \(\mathbb {F}\) coincides with the same for cohomology because of duality. We propose an implementation of a recently introduced algorithm for persistent cohomology that attaches annotation vectors with the simplices. We separate the representation of the simplicial complex from the representation of the cohomology groups, and introduce a new data structure for maintaining the annotation matrix, which is more compact and reduces substantially the amount of matrix operations. In addition, we propose a heuristic to simplify further the representation of the cohomology groups and improve both time and space complexities. The paper provides a theoretical analysis, as well as a detailed experimental study of our implementation and comparison with state-of-the-art software for persistent homology and cohomology.

### A Quantization Framework for Smoothed Analysis of Euclidean Optimization Problems

We consider the smoothed analysis of Euclidean optimization problems. Here, input points are sampled according to density functions that are bounded by a sufficiently small smoothness parameter \(\phi \) . For such inputs, we provide a general and systematic approach that allows designing linear-time approximation algorithms whose output is asymptotically optimal, both in expectation and with high probability. Applications of our framework include maximum matching, maximum TSP, and the classical problems of k-means clustering and bin packing. Apart from generalizing corresponding average-case analyses, our results extend and simplify a polynomial-time probable approximation scheme on multidimensional bin packing on \(\phi \) -smooth instances, where \(\phi \) is constant (Karger and Onak in Polynomial approximation schemes for smoothed and random instances of multidimensional packing problems, pp 1207–1216, 2007). Both techniques and applications of our rounding-based approach are orthogonal to the only other framework for smoothed analysis of Euclidean problems we are aware of (Bläser et al. in Algorithmica 66(2):397–418, 2013).

### A Faster Computation of All the Best Swap Edges of a Shortest Paths Tree

We consider a two-edge connected, non-negatively real-weighted graph *G* with *n* vertices and *m* edges, and a single-source shortest paths tree (SPT) of *G* rooted at an arbitrary vertex. If an edge of the SPT is temporarily removed, a widely recognized approach to reconnect the vertices disconnected from the root consists of joining the two resulting subtrees by means of a single non-tree edge, called a *swap edge*. This allows to reduce consistently the set-up and computational costs which are incurred if one instead rebuilds a new optimal SPT from scratch. In the past, several optimality criteria have been considered to select a *best* possible swap edge, and here we restrict our attention to arguably the two most significant measures: the minimization of either the *maximum* or the *average* distance between the root and the disconnected vertices. For the former criteria, we present an
\(O(m \log \alpha (m,n))\)
time algorithm—where
\(\alpha \)
is the inverse of the Ackermann function—to find a best swap edge for *every* edge of the SPT, thus improving onto the previous
\(O(m \log n)\)
time algorithm. Concerning the latter criteria, we provide an
\(O(m+n \log n)\)
time algorithm for the special but important case where *G* is *unweighted*, which compares favourably with the
\(O\left( m+n \, \alpha (n,n)\log ^2n\right) \)
time bound that one would get by using the fastest algorithm known for the weighted case—once this is suitably adapted to the unweighted case.

### Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines

In this paper we initiate the study of job scheduling on related and unrelated machines so as to minimize the maximum flow time or the maximum weighted flow time (when each job has an associated weight). Previous work for these metrics considered only the setting of parallel machines, while previous work for scheduling on unrelated machines only considered
\(L_p, p<\infty \)
norms. Our main results are: (1) we give an
\(\mathcal {O}({\varepsilon }^{-3})\)
-competitive algorithm to minimize maximum weighted flow time on related machines where we assume that the machines of the online algorithm can process
\(1+{\varepsilon }\)
units of a job in 1 time-unit (
\({\varepsilon }\)
speed augmentation). (2) For the objective of minimizing maximum flow time on unrelated machines we give a simple
\(2/{\varepsilon }\)
-competitive algorithm when we augment the speed by
\({\varepsilon }\)
. For *m* machines we show a lower bound of
\({\varOmega }(m)\)
on the competitive ratio if speed augmentation is not permitted. Our algorithm does not assign jobs to machines as soon as they arrive. To justify this “drawback” we show a lower bound of
\({\varOmega }(\log m)\)
on the competitive ratio of *immediate dispatch* algorithms. In both these lower bound constructions we use jobs whose processing times are in
\(\left\{ 1,\infty \right\} \)
, and hence they apply to the more restrictive *subset parallel* setting. (3) For the objective of minimizing maximum weighted flow time on unrelated machines we establish a lower bound of
\({\varOmega }(\log m)\)
-on the competitive ratio of any online algorithm which is permitted to use
\(s=\mathcal {O}(1)\)
speed machines. In our lower bound construction, job *j* has a processing time of
\(p_j\)
on a subset of machines and infinity on others and has a weight
\(1/p_j\)
. Hence this lower bound applies to the subset parallel setting for the special case of minimizing maximum stretch.

### Improved Quantum Query Algorithms for Triangle Detection and Associativity Testing

We show that the quantum query complexity of detecting if an *n*-vertex graph contains a triangle is
\(O(n^{9/7})\)
. This improves the previous best algorithm of Belovs (Proceedings of 44th symposium on theory of computing conference, pp 77–84, 2012) making
\(O(n^{35/27})\)
queries. For the problem of determining if an operation
\(\circ : S \times S \rightarrow S\)
is associative, we give an algorithm making
\(O(|S|^{10/7})\)
queries, the first improvement to the trivial
\(O(|S|^{3/2})\)
application of Grover search. Our algorithms are designed using the learning graph framework of Belovs. We give a family of algorithms for detecting constant-sized subgraphs, which can possibly be directed and colored. These algorithms are designed in a simple high-level language; our main theorem shows how this high-level language can be compiled as a learning graph and gives the resulting complexity. The key idea to our improvements is to allow more freedom in the parameters of the database kept by the algorithm.

### Computing Approximate Nash Equilibria in Polymatrix Games

In an
\(\epsilon \)
-Nash equilibrium, a player can gain at most
\(\epsilon \)
by unilaterally changing his behavior. For two-player (bimatrix) games with payoffs in [0, 1], the best-known
\(\epsilon \)
achievable in polynomial time is 0.3393 (Tsaknakis and Spirakis in Internet Math 5(4):365–382, 2008). In general, for *n*-player games an
\(\epsilon \)
-Nash equilibrium can be computed in polynomial time for an
\(\epsilon \)
that is an increasing function of *n* but does not depend on the number of strategies of the players. For three-player and four-player games the corresponding values of
\(\epsilon \)
are 0.6022 and 0.7153, respectively. Polymatrix games are a restriction of general *n*-player games where a player’s payoff is the sum of payoffs from a number of bimatrix games. There exists a very small but constant
\(\epsilon \)
such that computing an
\(\epsilon \)
-Nash equilibrium of a polymatrix game is
\(\mathtt {PPAD}\)
-hard. Our main result is that a
\((0.5+\delta )\)
-Nash equilibrium of an *n*-player polymatrix game can be computed in time polynomial in the input size and
\(\frac{1}{\delta }\)
. Inspired by the algorithm of Tsaknakis and Spirakis [28], our algorithm uses gradient descent style approach on the maximum regret of the players. We also show that this algorithm can be applied to efficiently find a
\((0.5+\delta )\)
-Nash equilibrium in a two-player Bayesian game.

### An Optimal Algorithm for the Weighted Backup 2-Center Problem on a Tree

In this paper, we are concerned with the weighted backup 2-center problem on a tree. The backup 2-center problem is a kind of center facility location problem, in which one is asked to deploy two facilities, with a given probability to fail, in a network. Given that the two facilities do not fail simultaneously, the goal is to find two locations, possibly on edges, that minimize the expected value of the maximum distance over all vertices to their closest functioning facility. In the weighted setting, each vertex in the network is associated with a nonnegative weight, and the distance from vertex *u* to *v* is weighted by the weight of *u*. With the strategy of prune-and-search, we propose a linear time algorithm, which is asymptotically optimal, to solve the weighted backup 2-center problem on a tree.