Author name cluster

Duncan Adamson

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

I&C Journal 2025 Journal Article

Collision-free Robot Scheduling

Duncan Adamson
Nathan Flaherty
Igor Potapov
Paul G. Spirakis

In this paper, we investigate the problem of designing schedules for completing a set of tasks at fixed locations with multiple robots in a laboratory. We represent the laboratory as a graph with tasks placed on fixed vertices and robots represented as agents, with the constraint that no two robots may occupy the same vertex at any given timestep. Each schedule is partitioned into a set of timesteps, corresponding to a walk through the graph (allowing for a robot to wait at a vertex to complete a task), with each timestep taking time equal to the time for a robot to move from one vertex to another and each task taking some given number of timesteps during the completion of which a robot must stay at the vertex containing the task. The goal is to determine a set of schedules, with one schedule for each robot, minimising the number of timesteps taken by the schedule taking the greatest number of timesteps within the set of schedules. We show that this problem is NP-complete for both star graphs (for k ≥ 2 robots), and planar graphs (for any number of robots). Finally, we provide positive results for path, cycle, and tadpole graphs, showing that we can find an optimal set of schedules for k robots completing m tasks of equal duration of a path of length n in O ( k m n ), O ( k m n 2 ) time, and O ( k 3 m 4 n ) time respectively.

Details DOI

TCS Journal 2025 Journal Article

Harmonious colourings of temporal matchings

Duncan Adamson

Graph colouring is a fundamental problem in computer science, with a large body of research dedicated to both the general colouring problem and restricted cases. Harmonious colourings are one such restriction, where each edge must contain a globally unique pair of colours, i. e. if an edge connects a vertex coloured x with a vertex coloured y, then no other pair of connected vertices can be coloured x and y. Finding such a colouring in the traditional graph setting is known to be NP-hard, even in trees. This paper considers the generalisation of harmonious colourings to Temporal Graphs, specifically ( k, t ) -Temporal matchings, a class of temporal graphs where the underlying graph is a matching (a collection of disconnected components containing pairs of vertices), each edge can appear in at most t timesteps, and each timestep can contain at most k other edges. We provide a complete overview of the complexity landscape of finding temporal harmonious colourings for ( k, t ) -matchings. We show that finding a Temporal Harmonious Colouring, a colouring that is harmonious in each timestep, is NP-hard for (k, t)-Temporal Matchings when k ≥ 2, t ≥ 4, or when k ≥ 3 and t ≥ 2. We further show that this problem is inapproximable for t ≥ 2 and an unbounded value of k, and that the problem of determining the temporal harmonious chromatic number of a ( 2, 3 ) -temporal matching can be determined in linear time. Finally, we strengthen this result by a set of upper and lower bounds of the temporal harmonious chromatic number both for individual temporal matchings and for the classes of ( k, t ) -temporal matchings, paths, and cycles.

Details DOI

I&C Journal 2025 Journal Article

k-Universality of Regular Languages

Duncan Adamson
Pamela Fleischmann
Annika Huch
Tore Koß
Florin Manea
Dirk Nowotka

A subsequence of a word w is a word u such that u = w [ i 1 ] w [ i 2 ] … w [ i k ], for some set of indices 1 ≤ i 1 < i 2 < … < i k ≤ | w |. A word w is k-subsequence universal over an alphabet Σ if every word in Σ k appears in w as a subsequence. In this paper, we study the intersection between the set of k-subsequence universal words over some alphabet Σ and regular languages over Σ. We call a regular language L k-∃-subsequence universal if there exists a k-subsequence universal word in L, and k-∀-subsequence universal if every word of L is k-subsequence universal. We give algorithms solving the problems of deciding if a given regular language, represented by a finite automaton recognising it, is k-∃-subsequence universal and, respectively, if it is k-∀-subsequence universal, for a given k. The algorithms are FPT w. r. t. the size of the input alphabet, and their run-time does not depend on k; they run in polynomial time in the number n of states of the input automaton when the size of the input alphabet is O ( log ⁡ n ). Moreover, we show that the problem of deciding if a given regular language is k-∃-subsequence universal is NP-complete, when the language is over a large alphabet. Further, we provide algorithms for counting the number of k-subsequence universal words (paths) accepted by a given deterministic (respectively, non-deterministic) finite automaton, and ranking an input word (path) within the set of k-subsequence universal words accepted by a given finite automaton.

Details DOI

MFCS Conference 2022 Conference Paper

The Complexity of Periodic Energy Minimisation

Duncan Adamson
Argyrios Deligkas
Vladimir V. Gusev
Igor Potapov

The computational complexity of pairwise energy minimisation of N points in real space is a long-standing open problem. The idea of the potential intractability of the problem was supported by a lack of progress in finding efficient algorithms, even when restricted the integer grid approximation. In this paper we provide a firm answer to the problem on ℤ^d by showing that for a large class of pairwise energy functions the problem of periodic energy minimisation is NP-hard if the size of the period (known as a unit cell) is fixed, and is undecidable otherwise. We do so by introducing an abstraction of pairwise average energy minimisation as a mathematical problem, which covers many existing models. The most influential aspects of this work are showing for the first time: 1) undecidability of average pairwise energy minimisation in general 2) computational hardness for the most natural model with periodic boundary conditions, and 3) novel reductions for a large class of generic pairwise energy functions covering many physical abstractions at once. In particular, we develop a new tool of overlapping digital rhombuses to incorporate the properties of the physical force fields, and we connect it with classical tiling problems. Moreover, we illustrate the power of such reductions by incorporating more physical properties such as charge neutrality, and we show an inapproximability result for the extreme case of the 1D average energy minimisation problem.

Details