Author name cluster

David Ilcinkas

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.

15 papers

2 author rows

TCS Journal 2020 Journal Article

Beachcombing on strips and islands

Evangelos Bampas
Jurek Czyzowicz
David Ilcinkas
Ralf Klasing

A group of mobile robots (beachcombers) have to search collectively every point of a given domain. At any given moment, each robot can be in walking mode or in searching mode. It is assumed that each robot's maximum allowed searching speed is strictly smaller than its maximum allowed walking speed. A point of the domain is searched if at least one of the robots visits it in searching mode. The Beachcombers' Problem consists in developing efficient schedules (algorithms) for the robots which collectively search all the points of the given domain as fast as possible. We consider searching schedules in the following one-dimensional geometric domains: the cycle of a known circumference L, the finite straight line segment of a known length L, and the semi-infinite line [ 0, + ∞ ). We first consider the online Beachcombers' Problem (i. e. the scenario when the robots do not know in advance the length of the segment to be searched), where the robots are initially collocated at the origin of a semi-infinite line. It is sought to design a schedule A with maximum speed S, defined as S = inf ℓ ⁡ ℓ t A ( ℓ ), where t A ( ℓ ) denotes the time when the search of the segment [ 0, ℓ ] is completed under A. We consider a discrete and a continuous version of the problem, depending on whether the infimum is taken over ℓ ∈ N ⁎ or ℓ ≥ 1. We prove that the LeapFrog algorithm, which was proposed in Czyzowicz et al. (2015) [12], is in fact optimal in the discrete case. This settles in the affirmative a conjecture from that paper. We also show how to extend this result to the more general continuous online setting. For the offline version of the Beachcombers' Problem (i. e. the scenario when the robots know in advance the length of the segment to be searched), we consider the t-source Beachcombers' Problem (i. e. all robots start from a fixed number t ≥ 1 of starting positions) on the cycle and on the finite segment. For the t-source Beachcombers' Problem on the cycle, we show that the structure of the optimal solutions is identical to the structure of the optimal solutions to the 2t-source Beachcombers' Problem on a finite segment. In consequence, by using results from Czyzowicz et al. (2014) [13], we prove that the 1-source Beachcombers' Problem on the cycle is NP-hard, and we derive approximation algorithms for the problem. For the t-source variant of the Beachcombers' Problem on the cycle and on the finite segment, we also derive efficient approximation algorithms. One important contribution of our work is that, in all variants of the offline Beachcombers' Problem that we discuss, we allow the robots to change direction of movement and search points of the domain on both sides of their respective starting positions. This represents a significant generalization compared to the model considered in Czyzowicz et al. (2014) [13], in which each robot had a fixed direction of movement that was specified as part of the solution to the problem. We manage to prove that changes of direction do not help the robots achieve optimality.

Details DOI

TCS Journal 2020 Journal Article

Exploration of carrier-based time-varying networks: The power of waiting

David Ilcinkas
Ahmed M. Wade

We study the problem of exploration by a mobile entity (agent) of a class of highly dynamic networks, namely the carrier graphs (the C-graphs, modeling public transportation systems, among others). These are defined by a set of carriers following infinitely their prescribed route along the stations of the network. Flocchini, Mans, and Santoro [9] studied this problem in the case when the agent must always travel on the carriers and thus cannot wait on a station. They described the necessary and sufficient conditions for the problem to be solvable and proved that the optimal worst-case number of time units (and thus of moves) to explore a n-node C-graph of k carriers and maximal period p is in Θ ( k p 2 ) in the general case. In this paper, we study the impact of the ability to wait at the stations. We exhibit the necessary and sufficient conditions for the problem to be solvable in this context, and we prove that waiting at the stations allows the agent to reduce the optimal worst-case number of moves by a multiplicative factor of at least Θ ( p ), while the worst-case time complexity is reduced to Θ ( n p ). (In any connected carrier graph, we have n ≤ k p.) We also show some complementary optimal results in specific cases (same period for all carriers, highly connected C-graphs). Finally this new ability allows the agent to completely map the C-graph, in addition to just exploring it.

Details DOI

TCS Journal 2019 Journal Article

On asynchronous rendezvous in general graphs

Evangelos Bampas
Lélia Blin
Jurek Czyzowicz
David Ilcinkas
Arnaud Labourel
Maria Potop-Butucaru
Sébastien Tixeuil

A pair of agents (robots) are moving in a graph with the goal of meeting at the same node or while traversing the same edge. An asynchronous adversary knows the prescribed walks of the two agents and is in complete control of the speed of each agent during its walk. We provide a complete characterization of pairs of walks that enforce rendezvous against an asynchronous adversary after traversing a given number of edges. The characterization is efficient in that it can be checked in polynomial time. We argue that the certificate of rendezvous enforcement that is produced by the checking algorithm contains a wealth of information on why rendezvous is enforced.

Details DOI

I&C Journal 2018 Journal Article

On mobile agent verifiable problems

Evangelos Bampas
David Ilcinkas

We consider decision problems that are solved in a distributed fashion by synchronous mobile agents operating in an unknown, anonymous network. Each agent has a unique identifier and an input string and they have to decide collectively a property which may involve their input strings, the graph on which they are operating, and their particular starting positions. Building on recent work by Fraigniaud and Pelc [J. Parallel Distrib. Comput, vol. 109, pp. 117–128], we introduce several natural new computability classes allowing for a finer classification of problems below MAV or its complement class co-MAV, the former being the class of problems that are verifiable when the agents are provided with an appropriate certificate. We provide inclusion and separation results among all these classes. We also determine their closure properties with respect to set-theoretic operations. Our main technical tool, which is of independent interest, is a new meta-protocol that enables the execution of a possibly infinite number of mobile agent protocols essentially in parallel, similarly to the well-known dovetailing technique from classical computability theory.

Details DOI

TCS Journal 2016 Journal Article

The impact of dynamic events on the number of errors in networks

Christian Glacet
Nicolas Hanusse
David Ilcinkas

In order to achieve routing in a graph, nodes need to store routing information. In the case of shortest path routing, for a given destination, every node has to store an advice that is an outgoing link toward a neighbor. If this neighbor does not belong to a shortest path then the advice is considered as an error and the node giving this advice will be qualified a liar. This article focuses on the impact of graph dynamics on the advice set for a given destination. More precisely we show that, for a weighted graph G of diameter D with n nodes and m edges, the expected number of errors after M edge deletions is bounded by O ( n ⋅ M ⋅ D / m ). We also show that this bound is tight when M = O ( n ). Moreover, for M ′ node deletions, the expected number of errors is O ( M ′ ⋅ D ). Finally we show that after a single edge addition the expected number of liars can be Θ ( n ) for some families of graphs.

Details DOI

I&C Journal 2013 Journal Article

Worst-case optimal exploration of terrains with obstacles

Jurek Czyzowicz
David Ilcinkas
Arnaud Labourel
Andrzej Pelc

A mobile robot represented by a point moving in the plane has to explore an unknown flat terrain with impassable obstacles. Both the terrain and the obstacles are modeled as arbitrary polygons. We consider two scenarios: the unlimited vision, when the robot situated at a point p of the terrain explores (sees) all points q of the terrain for which the segment pq belongs to the terrain, and the limited vision, when we require additionally that the distance between p and q is at most 1. All points of the terrain (except obstacles) have to be explored and the performance of an exploration algorithm, called its complexity, is measured by the length of the trajectory of the robot. For unlimited vision we show an exploration algorithm with complexity O ( P + D k ), where P is the total perimeter of the terrain (including perimeters of obstacles), D is the diameter of the convex hull of the terrain, and k is the number of obstacles. We do not assume knowledge of these parameters. We also prove a matching lower bound showing that the above complexity is optimal, even if the terrain is known to the robot. For limited vision we show exploration algorithms with complexity O ( P + A + A k ), where A is the area of the terrain (excluding obstacles). Our algorithms work either for arbitrary terrains (if one of the parameters A or k is known) or for c-fat terrains, where c is any constant (unknown to the robot) and no additional knowledge is assumed. (A terrain T with obstacles is c-fat if R / r ⩽ c, where R is the radius of the smallest disc containing T and r is the radius of the largest disc contained in T.) We also prove a matching lower bound Ω ( P + A + A k ) on the complexity of exploration for limited vision, even if the terrain is known to the robot.

Details DOI

TCS Journal 2012 Journal Article

More efficient periodic traversal in anonymous undirected graphs

Jurek Czyzowicz
Stefan Dobrev
Leszek Gąsieniec
David Ilcinkas
Jesper Jansson
Ralf Klasing
Ioannis Lignos
Russell Martin

We consider the problem of periodic graph exploration in which a mobile entity with constant memory, an agent, has to visit all n nodes of an input simple, connected, undirected graph in a periodic manner. Graphs are assumed to be anonymous, that is, nodes are unlabeled. While visiting a node, the agent may distinguish between the edges incident to it; for each node v, the endpoints of the edges incident to v are uniquely identified by different integer labels called port numbers. We are interested in algorithms for assigning the port numbers together with traversal algorithms for agents using these port numbers to obtain short traversal periods. Periodic graph exploration is unsolvable if the port numbers are set arbitrarily; see Budach (1978) [1]. However, surprisingly small periods can be achieved by carefully assigning the port numbers. Dobrev et al. (2005) [4] described an algorithm for assigning port numbers and an oblivious agent (i. e. , an agent with no memory) using it, such that the agent explores any graph with n nodes within the period 10 n. When the agent has access to a constant number of memory bits, the optimal length of the period was proved in Gąsieniec et al. (2008) [7] to be no more than 3. 75 n − 2 (using a different assignment of the port numbers and a different traversal algorithm). In this paper, we improve both these bounds. More precisely, we show how to achieve a period length of at most ( 4 + 1 3 ) n − 4 for oblivious agents and a period length of at most 3. 5 n − 2 for agents with constant memory. To obtain our results, we introduce a new, fast graph decomposition technique called a three-layer partition that may also be useful for solving other graph problems in the future. Finally, we present the first non-trivial lower bound, 2. 8 n − 2, on the period length for the oblivious case.

Details DOI

TCS Journal 2011 Journal Article

Asynchronous deterministic rendezvous in bounded terrains

Jurek Czyzowicz
David Ilcinkas
Arnaud Labourel
Andrzej Pelc

Two mobile agents (robots) have to meet in an a priori unknown bounded terrain modeled as a polygon, possibly with polygonal obstacles. Robots are modeled as points, and each of them is equipped with a compass. Compasses of robots may be incoherent. Robots construct their routes, but the actual walk of each robot is decided by the adversary that may, e. g. , speed up or slow down the robot. We consider several scenarios, depending on three factors: (1) obstacles in the terrain are present, or not, (2) compasses of both robots agree, or not, (3) robots have or do not have a map of the terrain with their positions marked. The cost of a rendezvous algorithm is the worst-case sum of lengths of the robots’ trajectories until they meet. For each scenario, we design a deterministic rendezvous algorithm and analyze its cost. We also prove lower bounds on the cost of any deterministic rendezvous algorithm in each case. For all scenarios these bounds are tight.

Details DOI

TCS Journal 2010 Journal Article

Fast radio broadcasting with advice

David Ilcinkas
Dariusz R. Kowalski
Andrzej Pelc

We study deterministic broadcasting in radio networks in the recently introduced framework of network algorithms with advice. We concentrate on the problem of trade-offs between the number of bits of information (size of advice) available to nodes and the time in which broadcasting can be accomplished. In particular, we ask what is the minimum number of bits of information that must be available to nodes of the network, in order to broadcast very fast. For networks in which constant time broadcast is possible under a complete knowledge of the network we give a tight answer to the above question: O ( n ) bits of advice are sufficient but o ( n ) bits are not, in order to achieve constant broadcasting time in all these networks. This is in sharp contrast with geometric radio networks of constant broadcasting time: we show that in these networks a constant number of bits suffices to broadcast in constant time. For arbitrary radio networks we present a broadcasting algorithm whose time is inverse-proportional to the size of the advice.

Details DOI

TCS Journal 2010 Journal Article

Remembering without memory: Tree exploration by asynchronous oblivious robots

Paola Flocchini
David Ilcinkas
Andrzej Pelc
Nicola Santoro

In an effort to understand the algorithmic limitations of computing by a swarm of robots, the research has focused on the minimal capabilities that allow a problem to be solved. The weakest of the commonly used models is Asynch where the autonomous mobile robots, endowed with visibility sensors (but otherwise unable to communicate), operate in Look-Compute-Move cycles performed asynchronously for each robot. The robots are often assumed (or required to be) oblivious: they keep no memory of observations and computations made in previous cycles. We consider the setting when the robots are dispersed in an anonymous and unlabeled graph, and they must perform the very basic task of exploration: within finite time every node must be visited by at least one robot and the robots must enter a quiescent state. The complexity measure of a solution is the number of robots used to perform the task. We study the case when the graph is an arbitrary tree and establish some unexpected results. We first prove that, in general, exploration cannot be done efficiently. More precisely we prove that there are n -node trees where Ω ( n ) robots are necessary; this holds even if the maximum degree is 4. On the other hand, we show that if the maximum degree is 3, it is possible to explore with only O ( log n log log n ) robots. The proof of the result is constructive. We also prove that the size of the team used in our solution is asymptotically optimal: there are trees of degree 3, whose exploration requires Ω ( log n log log n ) robots. Our final result shows that the difficulty in tree exploration comes in fact from the symmetries of the tree. Indeed, we show that, in order to explore trees that do not have any non-trivial automorphisms, 4 robots are always sufficient and often necessary.

Details DOI

TCS Journal 2008 Journal Article

Setting port numbers for fast graph exploration

David Ilcinkas

We consider the problem of periodic graph exploration by a finite automaton in which an automaton with a constant number of states has to explore all unknown anonymous graphs of arbitrary size and arbitrary maximum degree. In anonymous graphs, nodes are not labeled but edges are labeled in a local manner (called local orientation) so that the automaton is able to distinguish them. Precisely, the edges incident to a node v are given port numbers from 1 to d v, where d v is the degree of v. Periodic graph exploration means visiting every node infinitely often. We are interested in the length of the period, i. e. , the maximum number of edge traversals between two consecutive visits of any node by the automaton in the same state and entering the node by the same port. This problem is unsolvable if local orientations are set arbitrarily. Given this impossibility result, we address the following problem: what is the minimum function π ( n ) such that there exists an algorithm for setting the local orientation, and a finite automaton using it, such that the automaton explores all graphs of size n within the period π ( n )? The best result so far is the upper bound π ( n ) ≤ 10 n, by Dobrev et al. [S. Dobrev, J. Jansson, K. Sadakane, W. -K. Sung, Finding short right-hand-on-the-wall walks in graphs, in: 12th Colloquium on Structural Information and Communication Complexity, SIROCCO, in: LNCS, vol. 3499, 2005, pp. 127–139], using an automaton with no memory (i. e. only one state). In this paper we prove a better upper bound π ( n ) ≤ 4 n. Our automaton uses three states but performs periodic exploration independently of its starting position and initial state.

Details DOI

I&C Journal 2008 Journal Article

Tree exploration with advice

Pierre Fraigniaud
David Ilcinkas
Andrzej Pelc

We study the amount of knowledge about the network that is required in order to efficiently solve a task concerning this network. The impact of available information on the efficiency of solving network problems, such as communication or exploration, has been investigated before but assumptions concerned availability of particular items of information about the network, such as the size, the diameter, or a map of the network. In contrast, our approach is quantitative: we investigate the minimum number of bits of information (bits of advice) that has to be given to an algorithm in order to perform a task with given efficiency. We illustrate this quantitative approach to available knowledge by the task of tree exploration. A mobile entity (robot) has to traverse all edges of an unknown tree, using as few edge traversals as possible. The quality of an exploration algorithm A is measured by its competitive ratio, i. e. , by comparing its cost (number of edge traversals) to the length of the shortest path containing all edges of the tree. Depth-First-Search has competitive ratio 2 and, in the absence of any information about the tree, no algorithm can beat this value. We determine the minimum number of bits of advice that has to be given to an exploration algorithm in order to achieve competitive ratio strictly smaller than 2. Our main result establishes an exact threshold number of bits of advice that turns out to be roughly log log D, where D is the diameter of the tree. More precisely, for any constant c, we construct an exploration algorithm with competitive ratio smaller than 2, using at most log log D - c bits of advice, and we show that every algorithm using log log D - g ( D ) bits of advice, for any function g unbounded from above, has competitive ratio at least 2.

Details DOI

MFCS Conference 2006 Invited Paper

Tree Exploration with an Oracle

Pierre Fraigniaud
David Ilcinkas
Andrzej Pelc

Abstract We study the amount of knowledge about the network that is required in order to efficiently solve a task concerning this network. The impact of available information on the efficiency of solving network problems, such as communication or exploration, has been investigated before but assumptions concerned availability of particular items of information about the network, such as the size, the diameter, or a map of the network. In contrast, our approach is quantitative: we investigate the minimum number of bits of information (minimum oracle size) that has to be given to an algorithm in order to perform a task with given efficiency. We illustrate this quantitative approach to available knowledge by the task of tree exploration. A mobile entity (robot) has to traverse all edges of an unknown tree, using as few edge traversals as possible. The quality of an exploration algorithm \({\cal A}\) is measured by its competitive ratio, i. e. , by comparing its cost (number of edge traversals) to the length of the shortest path containing all edges of the tree. Depth-First-Search has competitive ratio 2 and, in the absence of any information about the tree, no algorithm can beat this value. We determine the minimum number of bits of information that has to be given to an exploration algorithm in order to achieve competitive ratio strictly smaller than 2. Our main result establishes an exact threshold oracle size that turns out to be roughly loglog D, where D is the diameter of the tree. More precisely, for any constant c, we construct an exploration algorithm with competitive ratio smaller than 2, using an oracle of size at most loglog D – c, and we show that every algorithm using an oracle of size loglog D – g ( D ), for any function g unbounded from above, has competitive ratio at least 2.

Details

TCS Journal 2005 Journal Article

Graph exploration by a finite automaton

Pierre Fraigniaud
David Ilcinkas
Guy Peer
Andrzej Pelc
David Peleg

A finite automaton, simply referred to as a robot, has to explore a graph whose nodes are unlabeled and whose edge ports are locally labeled at each node. The robot has no a priori knowledge of the topology of the graph or of its size. Its task is to traverse all the edges of the graph. We first show that, for any K-state robot and any d ⩾ 3, there exists a planar graph of maximum degree d with at most K + 1 nodes that the robot cannot explore. This bound improves all previous bounds in the literature. More interestingly, we show that, in order to explore all graphs of diameter D and maximum degree d, a robot needs Ω ( D log d ) memory bits, even if we restrict the exploration to planar graphs. This latter bound is tight. Indeed, a simple DFS up to depth D + 1 enables a robot to explore any graph of diameter D and maximum degree d using a memory of size O ( D log d ) bits. We thus prove that the worst case space complexity of graph exploration is Θ ( D log d ) bits.

Details DOI

MFCS Conference 2004 Conference Paper

Graph Exploration by a Finite Automaton

Pierre Fraigniaud
David Ilcinkas
Guy Peer
Andrzej Pelc
David Peleg

Abstract A finite automaton, simply referred to as a robot, has to explore a graph whose nodes are unlabeled and whose edge ports are locally labeled at each node. The robot has no a priori knowledge of the topology of the graph or of its size. Its task is to traverse all the edges of the graph. We first show that, for any K -state robot and any d ≥ 3, there exists a planar graph of maximum degree d with at most K +1 nodes that the robot cannot explore. This bound improves all previous bounds in the literature. More interestingly, we show that, in order to explore all graphs of diameter D and maximum degree d, a robot needs Ω( D log d ) memory bits, even if we restrict the exploration to planar graphs. This latter bound is tight. Indeed, a simple DFS at depth D +1 enables a robot to explore any graph of diameter D and maximum degree d using a memory of size O ( D log d ) bits. We thus prove that the worst case space complexity of graph exploration is Θ( D log d ) bits.

Details