Search Our Scientific Publications & Authors

Algorithmica 2021 21;83(2):726-752. Epub 2020 Oct 21.

Algorithms Group, University of Sheffield, Sheffield, UK.

This paper revisits the classical edge-disjoint paths (EDP) problem, where one is given an undirected graph and a set of terminal pairs and asks whether contains a set of pairwise edge-disjoint paths connecting every terminal pair in . Our aim is to identify structural properties (parameters) of graphs which allow the efficient solution of EDP without restricting the placement of terminals in in any way. In this setting, EDP is known to remain NP-hard even on extremely restricted graph classes, such as graphs with a vertex cover of size 3. Read More

Algorithmica 2021 25;83(1):144-176. Epub 2020 Jul 25.

Département d'informatique, Université du Québec en Outaouais, Gatineau, Canada.

A robot modeled as a deterministic finite automaton has to build a structure from material available to it. The robot navigates in the infinite oriented grid . Some cells of the grid are full (contain a brick) and others are empty. Read More

Algorithmica 2021 27;83(1):116-143. Epub 2020 Jul 27.

TU Graz, Graz, Austria.

Flip graphs are a ubiquitous class of graphs, which encode relations on a set of combinatorial objects by elementary, local changes. Skeletons of associahedra, for instance, are the graphs induced by quadrilateral flips in triangulations of a convex polygon. For some definition of a flip graph, a natural computational problem to consider is the flip distance: Given two objects, what is the minimum number of flips needed to transform one into the other? We consider flip graphs on orientations of simple graphs, where flips consist of reversing the direction of some edges. Read More

Algorithmica 2020 20;82(11):3306-3337. Epub 2020 Jun 20.

Helsinki Institute for Information Technology (HIIT), Espoo, Finland.

We derandomize Valiant's (J ACM 62, Article 13, 2015) subquadratic-time algorithm for finding outlier correlations in binary data. This demonstrates that it is possible to perform a deterministic subquadratic-time similarity join of high dimensionality. Our derandomized algorithm gives deterministic subquadratic scaling essentially for the same parameter range as Valiant's randomized algorithm, but the precise constants we save over quadratic scaling are more modest. Read More

Algorithmica 2020 22;82(8):2267-2291. Epub 2020 Jan 22.

ETH Zürich, Zurich, Switzerland.

We investigate the problem of counting all induced subgraphs of size  in a graph  that satisfy a given property . This continues the work of Jerrum and Meeks who proved the problem to be -hard for some families of properties which include (dis)connectedness [JCSS 15] and even- or oddness of the number of edges [Combinatorica 17]. Using the recent framework of graph motif parameters due to Curticapean, Dell and Marx [STOC 17], we discover that for monotone properties  , the problem is hard for if the reduced Euler characteristic of the associated simplicial (graph) complex of is non-zero. Read More

Algorithmica 2020 14;82(5):1410-1433. Epub 2019 Nov 14.

7University of Southampton, Southampton, UK.

We consider the two-sided stable matching setting in which there may be uncertainty about the agents' preferences due to limited information or communication. We consider three models of uncertainty: (1) lottery model-for each agent, there is a probability distribution over linear preferences, (2) compact indifference model-for each agent, a weak preference order is specified and each linear order compatible with the weak order is equally likely and (3) joint probability model-there is a lottery over preference profiles. For each of the models, we study the computational complexity of computing the stability probability of a given matching as well as finding a matching with the highest probability of being stable. Read More

Algorithmica 2020 6;82(5):1136-1188. Epub 2020 Feb 6.

3Budapest University of Technology and Economics, Budapest, Hungary.

Stable matching problems with lower quotas are fundamental in academic hiring and ensuring operability of rural hospitals. Only few tractable (polynomial-time solvable) cases of stable matching with lower quotas have been identified; most such problems are -hard and also hard to approximate (Hamada et al. in Algorithmica 74(1):440-465, 2016). Read More

Algorithmica 2020 25;82(3):429-508. Epub 2019 Oct 25.

Institut für Mathematik, Alpen-Adria-Universität Klagenfurt, Universitätsstraße 65-67, 9020 Klagenfurt am Wörthersee, Austria.

In this article, -regular sequences in the sense of Allouche and Shallit are analysed asymptotically. It is shown that the summatory function of a regular sequence can asymptotically be decomposed as a finite sum of periodic fluctuations multiplied by a scaling factor. Each of these terms corresponds to an eigenvalue of the sum of matrices of a linear representation of the sequence; only the eigenvalues of absolute value larger than the joint spectral radius of the matrices contribute terms which grow faster than the error term. Read More

Algorithmica 2019 5;81(10):3993-4009. Epub 2018 Sep 5.

1Eindhoven University of Technology, Eindhoven, The Netherlands.

In this paper, we develop new tools and connections for . In this setting, we are given a problem instance and an integer , and the goal is to design an approximation algorithm with the fastest possible running time. We give randomized algorithms that establish an approximation ratio of for maximum independent set in time, for chromatic number in time, for minimum vertex cover in time, and for minimum -hypergraph vertex cover in time. Read More

Algorithmica 2019 25;81(5):1965-1987. Epub 2018 Sep 25.

2Department of Computer Science, University of Sheffield, Sheffield, UK.

In this paper we study graph problems in the dynamic streaming model, where the input is defined by a sequence of edge insertions and deletions. As many natural problems require space, where is the number of vertices, existing works mainly focused on designing space algorithms. Although sublinear in the number of edges for dense graphs, it could still be too large for many applications (e. Read More

Algorithmica 2019 13;81(4):1699-1727. Epub 2018 Aug 13.

1University of Oxford, Oxford, UK.

Singleton arc consistency is an important type of local consistency which has been recently shown to solve all constraint satisfaction problems (CSPs) over constraint languages of bounded width. We aim to characterise all classes of CSPs defined by a forbidden pattern that are solved by singleton arc consistency and closed under removing constraints. We identify five new patterns whose absence ensures solvability by singleton arc consistency, four of which are provably maximal and three of which generalise 2-SAT. Read More

Algorithmica 2019 4;81(4):1657-1683. Epub 2018 Sep 4.

4Department of Computer Science, University of Sheffield, Sheffield, UK.

We consider the -complete problem of counting the number of linear extensions of a poset ; a fundamental problem in order theory with applications in a variety of distinct areas. In particular, we study the complexity of parameterized by the well-known decompositional parameter treewidth for two natural graphical representations of the input poset, i.e. Read More

Algorithmica 2019 30;81(2):497-518. Epub 2018 Jul 30.

Faculty of Mathematics, Informatics, and Mechanics, University of Warsaw, Warsaw, Poland.

We introduce the non-commutative subset convolution-a convolution of functions useful when working with determinant-based algorithms. In order to compute it efficiently, we take advantage of Clifford algebras, a generalization of quaternions used mainly in the quantum field theory. We apply this tool to speed up algorithms counting subgraphs parameterized by the treewidth of a graph. Read More

Algorithmica 2019 7;81(1):317-342. Epub 2018 May 7.

6CSAIL, Massachusetts Institute of Technology, Cambridge, USA.

Two mobile robots are initially placed at the same point on an infinite line. Each robot may move on the line in either direction not exceeding its maximal speed. The robots need to find a stationary target placed at an unknown location on the line. Read More

Algorithmica 2019 2;81(1):124-166. Epub 2018 Apr 2.

1University of Liverpool, Liverpool, UK.

The problem of pollution control has been mainly studied in the environmental economics literature where the methodology of game theory is applied for the pollution control. To the best of our knowledge this is the first time this problem is studied from the computational point of view. We introduce a new network model for pollution control and present two applications of this model. Read More

Algorithmica 2019 18;81(2):476-496. Epub 2018 Sep 18.

1Institut für Theoretische Informatik, Leibniz Universität Hannover, Appelstrasse 4, 30167 Hannover, Germany.

In the present paper, we introduce the backdoor set approach into the field of temporal logic for the global fragment of linear temporal logic. We study the parameterized complexity of the satisfiability problem parameterized by the size of the backdoor. We distinguish between backdoor detection and evaluation of backdoors into the fragments of Horn and Krom formulas. Read More

Algorithmica 2018 14;80(10):2909-2940. Epub 2017 Aug 14.

Institute of Information Systems 184/2, TU Wien, Favoritenstrasse 9-11, 1040 Vienna, Austria.

A secure set in a graph is defined as a set of vertices such that for any the majority of vertices in the neighborhood of belongs to . It is known that deciding whether a set is secure in a graph is -complete. However, it is still open how this result contributes to the actual complexity of deciding whether for a given graph and integer , a non-empty secure set for of size at most exists. Read More

Algorithmica 2018 13;80(2):742-771. Epub 2017 Feb 13.

Algorithms and Complexity Group, TU Wien, Vienna, Austria.

A modulator in a graph is a vertex set whose deletion places the considered graph into some specified graph class. The cardinality of a modulator to various graph classes has long been used as a structural parameter which can be exploited to obtain fixed-parameter algorithms for a range of hard problems. Here we investigate what happens when a graph contains a modulator which is large but "well-structured" (in the sense of having bounded rank-width). Read More

Algorithmica 2018 17;80(4):1115-1145. Epub 2017 Mar 17.

2Department of Computer Science, Oxford University, Oxford, UK.

We study the inefficiency of mixed Nash equilibria, expressed as the price of anarchy, of all-pay auctions in three different environments: combinatorial, multi-unit and single-item auctions. First, we consider item-bidding combinatorial auctions where all-pay auctions run in parallel, one for each good. For fractionally subadditive valuations, we strengthen the upper bound from 2 (Syrgkanis and Tardos in Proceedings of the 45th symposium on theory of computing (STOC '13), 2013) to 1. Read More

Algorithmica 2018 28;80(10):2818-2833. Epub 2017 Jul 28.

1Vrije Universiteit Amsterdam, De Boelelaan 1105, 1081 HV Amsterdam, Netherlands.

The field of a priori optimization is an interesting subfield of stochastic combinatorial optimization that is well suited for routing problems. In this setting, there is a probability distribution over active sets, vertices that have to be visited. For a fixed tour, the solution on an active set is obtained by restricting the solution on the active set. Read More

Algorithmica 2018 20;80(5):1634-1657. Epub 2017 Sep 20.

2DTU Compute, Technical University of Denmark, Kongens Lyngby, Denmark.

Island models denote a distributed system of evolutionary algorithms which operate independently, but occasionally share their solutions with each other along the so-called migration topology. We investigate the impact of the migration topology by introducing a simplified island model with behavior similar to islands optimizing the so-called Maze fitness function (Kötzing and Molter in Proceedings of parallel problem solving from nature (PPSN XII), Springer, Berlin, pp 113-122, 2012). Previous work has shown that when a complete migration topology is used, migration must not occur too frequently, nor too soon before the optimum changes, to track the optimum of the Maze function. Read More

Algorithmica 2018 6;80(5):1604-1633. Epub 2017 Sep 6.

2IST Austria, Am Campus 1, 3400 Klosterneuburg, Austria.

Escaping local optima is one of the major obstacles to function optimisation. Using the metaphor of a fitness landscape, local optima correspond to hills separated by fitness valleys that have to be overcome. We define a class of fitness valleys of tunable difficulty by considering their , representing the Hamming path between the two optima and their , the drop in fitness. Read More

Algorithmica 2018 31;80(11):3253-3269. Epub 2017 Oct 31.

1Department of Computer Science, TU Eindhoven, Eindhoven, The Netherlands.

We study the following problem: preprocess a set of objects into a data structure that allows us to efficiently report all pairs of objects from that intersect inside an axis-aligned query range . We present data structures of size and with query time time, where is the number of reported pairs, for two classes of objects in : axis-aligned rectangles and objects with small union complexity. For the 3-dimensional case where the objects and the query range are axis-aligned boxes in  , we present a data structure of size and query time . Read More

Algorithmica 2018 22;80(11):2993-3022. Epub 2017 Aug 22.

2Department of Data Science and Knowledge Engineering (DKE), Maastricht University, Maastricht, The Netherlands.

The hybridization number problem requires us to embed a set of binary rooted phylogenetic trees into a binary rooted phylogenetic network such that the number of nodes with indegree two is minimized. However, from a biological point of view accurately inferring the root location in a phylogenetic tree is notoriously difficult and poor root placement can artificially inflate the hybridization number. To this end we study a number of relaxed variants of this problem. Read More

Algorithmica 2017 26;78(2):660-680. Epub 2016 Aug 26.

ASAP Research Group, School of Computer Science, University of Nottingham, Jubilee Campus, Wollaton Road, Nottingham, NG8 1BB UK.

Real-world optimisation problems are often dynamic. Previously good solutions must be updated or replaced due to changes in objectives and constraints. It is often claimed that evolutionary algorithms are particularly suitable for dynamic optimisation because a large population can contain different solutions that may be useful in the future. Read More

Algorithmica 2017 18;78(2):714-740. Epub 2016 Aug 18.

1Department of Computer Science, Aberystwyth University, Aberystwyth, SY23 3DB UK.

Understanding which function classes are easy and which are hard for a given algorithm is a fundamental question for the analysis and design of bio-inspired search heuristics. A natural starting point is to consider the easiest and hardest functions for an algorithm. For the (1+1) EA using standard bit mutation (SBM) it is well known that OneMax is an easiest function with unique optimum while Trap is a hardest. Read More

Algorithmica 2017 7;78(2):641-659. Epub 2016 Dec 7.

2DTU Compute, Technical University of Denmark, Kongens Lyngby, Denmark.

A simple island model with islands and migration occurring after every iterations is studied on the dynamic fitness function Maze. This model is equivalent to a  EA if , i. e. Read More

Algorithmica 2016 19;76(4):1077-1096. Epub 2016 Jan 19.

1Eindhoven University of Technology, Eindhoven, The Netherlands.

We consider the Vector Scheduling problem, a natural generalization of the classical makespan minimization problem to multiple resources. Here, we are given jobs, represented as -dimensional vectors in , and identical machines, and the goal is to assign the jobs to machines such that the maximum of each machine over all the coordinates is at most 1. For fixed , the problem admits an approximation scheme, and the best known running time is where ( suppresses polylogarithmic terms in ). Read More

Algorithmica 2014 Mar;68(4):835-858

Dept. of Computer Science University of California, Irvine Irvine, CA 92697-3435 USA, http://www.ics.uci.edu/~goodrich/

We study sorting algorithms based on randomized round-robin comparisons. Specifically, we study Spin-the-bottle sort, where comparisons are unrestricted, and Annealing sort, where comparisons are restricted to a distance bounded by a parameter. Both algorithms are simple, randomized, data-oblivious sorting algorithms, which are useful in privacy-preserving computations, but, as we show, Annealing sort is much more efficient. Read More

Algorithmica 2014 22;68(1):41-61. Epub 2012 Jun 22.

Department of Computer Science and Information Theory, Budapest University of Technology and Economics, Magyar tudósok körútja 2, 1117 Budapest, Hungary.

We study a family of problems where the goal is to make a graph Eulerian, i.e., connected and with all the vertices having even degrees, by a minimum number of deletions. Read More