Drawing maps with advice

Abstract

We study the problem of the amount of information required to draw a complete or a partial map of a graph with unlabeled nodes and arbitrarily labeled ports. A mobile agent, starting at any node of an unknown connected graph and walking in it, has to accomplish one of the following tasks: draw a complete map of the graph, i.e., find an isomorphic copy of it including port numbering, or draw a partial map, i.e., a spanning tree, again with port numbering. The agent executes a deterministic algorithm and cannot mark visited nodes in any way. None of these map drawing tasks is feasible without any additional information, unless the graph is a tree. Hence we investigate the minimum number of bits of information (minimum size of advice) that has to be given to the agent to complete these tasks. It turns out that this minimum size of advice depends on the number $n$ of nodes or the number $m$ of edges of the graph, and on a crucial parameter $\mu$, called the multiplicity of the graph, which measures the number of nodes that have an identical view of the graph.

We give bounds on the minimum size of advice for both above tasks. For $\mu =1$ our bounds are asymptotically tight for both tasks and show that the minimum size of advice is very small. For $\mu >1$ the minimum size of advice increases abruptly. In this case our bounds are asymptotically tight for topology recognition and asymptotically almost tight for spanning tree construction.

Introduction

Knowing the topology of a network or at least a spanning tree of it is of significant help in organizing communication among nodes of the network and in accomplishing distributed tasks. It is well known that such tasks as, e.g., broadcasting or gossiping (information exchange) can be performed more efficiently when the topology of the network or a spanning tree of it are available to nodes, than when they have to be executed in an unknown network. One way of supplying this vital information to nodes is by means of exploration of the network, where a mobile agent has to traverse all links of the network and visit all its nodes. In fact, one of the main reasons to perform the well-studied task of graph exploration, see, e.g., [2], [4], [5], [14], [15], is to draw a faithful map of the graph that models the explored network. Provided that the agent has enough memory and computation power and that the exploration has been performed, drawing a map of the graph is easy, if nodes have distinct identities that can be perceived by the agent, or if the agent can leave marks at nodes when it visits them. However, neither of these assumptions is always satisfied. On the one hand, nodes may refuse to reveal their identities, e.g., for security reasons, or limited sensory capabilities of the agent may prevent it from perceiving these identities; on the other hand, nodes may not have facilities (whiteboards) allowing to leave marks, or such marks may be destructed between visits of the agent and thus unreliable. Thus it is important for the agent to be able to recognize the topology of the graph (draw a full map of the network) or construct its spanning tree (which is an important partial map of it) without relying on identities of the nodes and without marking them. In contrast, in order to allow the agent to move in the network, we have to assume that ports at every node are distinguishable for the agent. If an agent were unable to locally distinguish ports at a node, it may have even been unable to visit all neighbors of a node of degree at least 3. Indeed, after visiting the second neighbor, the agent cannot distinguish the port leading to the first visited neighbor from the port leading to the unvisited one. Thus an adversary may always force an agent to avoid all but two edges incident to such a node, thus effectively precluding exploration. Hence we assume that a node of degree $d$ has ports $1,\dots ,d$ corresponding to the incident edges. Ports at each node can be perceived by an agent visiting this node, but there is no coherence assumed between port labelings at different nodes. We assume that when an agent reaches a node, it learns the port number by which it entered it.

We consider two map drawing tasks that have to be accomplished by a mobile agent executing a deterministic algorithm and walking in an unknown connected graph with unlabeled nodes and labeled ports. One is topology recognition which consists in returning an isomorphic copy of the graph with correctly numbered ports, and the other is spanning tree construction which consists in returning a spanning tree of the graph, again with correctly numbered ports. Both tasks have to be performed by an agent that starts in an arbitrary node of an unknown graph and is allowed to explore it. These tasks can be easily accomplished after exploration if the graph is a tree (and in this case they are obviously equivalent): after performing an Eulerian tour of the tree, the agent realizes this fact and can reconstruct the topology of the tree. (By an Eulerian tour we mean a closed walk of minimum length that visits each edge at least once. Note that for a tree, each edge will be visited exactly twice in such a tour). However, it turns out that unless the graph is a tree, none of these tasks can be accomplished without any additional information given to the agent.

Fig. 1 (cf. [35]) gives an example of two non-isomorphic graphs after whose exploration an agent will get identical information, and thus will not be able to distinguish them. Indeed, a stronger fact is true: for any graph that is not a tree, an agent that has explored the graph and has no additional information can neither recognize the topology of the graph, nor even construct its spanning tree. This yields the main problem that we study in this paper.

What is the minimum number of bits of a priori information required by an agent exploring a graph, in order to recognize its topology or to construct its spanning tree?

This way of stating the problem follows the paradigm of network algorithms with advice that has become recently popular (cf. the subsection “Related work”), and can be described as follows. An oracle knowing the entire network can give a string of bits (advice) to the mobile agent. (In other settings strings of bits are given to nodes that subsequently exchange messages). Then an algorithm is executed by the agent without knowing in which network it operates, using the provided advice. The total number of bits given by the oracle is the size of advice. Thus the framework of advice permits to quantify the amount of information needed to solve a network problem, regardless of the type of information that is provided.

Since for trees no additional information is needed, in the rest of the paper we assume that the explored graph is not a tree. It turns out that the size of advice needed to solve the two problems under investigation depends on three parameters: the number $n$ of nodes, the number $m$ of edges, and a crucial parameter $\mu$ called the multiplicity of the graph. Our multiplicity parameter $\mu$ is related to the symmetricity $\sigma$ of a graph, defined in [35]. We define multiplicity for a graph $G$ with a particular port labeling, while $\sigma \left(G\right)$ is defined in [35] to be the maximum multiplicity over all port labelings of $G$. This parameter depends on the notion of the view from a node. Intuitively, this is the infinite tree with labeled ports, rooted at the given node, that would be obtained by a complete infinite exploration of the graph, if each visited node were attached as a new node in the tree (see the formal definition in Section 2). Since nodes of the graph are not labeled and cannot be marked, and thus already visited nodes cannot be recognized on subsequent visits, the view from a node is the maximum information that can be obtained by an agent starting at this node and exploring the graph (cf. Proposition 2.2). It has been proved in [31] that if views of two nodes of a $n$-node graph are different, then their views truncated to level $n-1$ are also different. Hence, knowing any upper bound on $n$, the agent can learn in finite time which nodes have equal views and which do not. It is known (cf. [35]) that, for every node $v$ of a graph, the number of nodes from which the view is identical as that from $v$ is the same. This number is the multiplicity $\mu$ of the graph.

We give bounds on the minimum size of advice required by an agent both for the task of topology recognition and of spanning tree construction. (We focus on the feasibility of accomplishing these tasks and not on the complexity of their performance). For $\mu =1$ our bounds are asymptotically tight for both tasks and show that the minimum size of advice is very small: for an arbitrary function $\phi =\omega \left(1\right)$ it suffices to give $\phi \left(n\right)$ bits of advice to accomplish both tasks for $n$-node graphs, and $\Theta \left(1\right)$ bits are not enough. For $\mu >1$ the minimum size of advice increases abruptly. In this case our bounds are asymptotically tight for topology recognition and asymptotically almost tight for spanning tree construction. We show that $\Theta (mlog\mu )$ bits of advice are enough and necessary to recognize topology in the class of graphs with $m$ edges and multiplicity $\mu >1$. For the second task we show that $\Omega (\mu log(n/\mu ))$ bits of advice are necessary and $O(\mu log(m/\mu ))$ bits of advice are enough to construct a spanning tree in the class of graphs with $n$ nodes, $m$ edges and multiplicity $\mu >1$. Thus in this case the gap between our bounds is always at most logarithmic, and the bounds are asymptotically tight, e.g., for multiplicity $\mu =O\left(n^{\alpha }\right)$, where $\alpha$ is any constant smaller than 1.

Our results imply the following, somewhat surprising comparison of the importance of graph exploration in accomplishing the two considered tasks. For the task of topology recognition, the fact that the agent can explore the graph has a small impact on the required size of advice, if $\mu >1$. Indeed, for any $\mu >1$, there are $2^{O(mlogn)}$ port-labeled non-isomorphic graphs with $n$ nodes, $m$ edges and multiplicity $\mu$. Hence without any exploration it would be enough to give $O(mlogn)$ bits of advice to recognize topology (by giving the index of the graph in some ordered list of all such graphs), and with the help of exploration the number of bits is $\Theta (mlog\mu )$. Thus the capability to explore the graph is “worth” at most a logarithmic factor in the size of advice (the largest difference occurring when $\mu$ is constant). In other words, the fact that the agent can explore the graph decreases the size of advice needed for topology recognition only by a logarithmic factor, as compared to a motionless agent. By contrast, for the task of spanning tree construction, the possibility of exploring the graph may have a crucial impact on the required size of advice. Indeed, we prove that for any $\mu$ there are at least $2^{\Omega (n/\mu )}$ graphs with $n$ nodes and multiplicity $\mu$, no pair of which has isomorphic spanning trees. Hence, without exploration, $\Omega (n/\mu )$ bits of advice would be necessary to solve the spanning tree construction problem. However, if the agent can explore the graph, only $O(\mu log(m/\mu ))$ bits are sufficient to find a spanning tree. Thus, for any $\mu$ polylogarithmic in $n$, the capability of exploring the graph is “worth” an exponential decrease of the size of advice required for spanning tree construction. In other words, an agent capable of exploring the graph requires exponentially smaller advice to solve the spanning tree construction problem, as compared with a motionless agent.

Network algorithms with advice were studied, e.g., in [16], [17], [18], [19], [20], [21], [24], [30]. When advice is given by the oracle to the nodes, rather than to a mobile agent, the advice paradigm becomes closely related to that of informative labeling schemes [1], [12], [22], [25], [26], [34]. In [12] it was shown that giving appropriate 2-bit labels to nodes of a graph allows an agent with a constant-size memory to explore all graphs, and that with 1-bit labels an agent can explore all graphs of bounded degree. In the advice paradigm the authors studied the minimum size of advice required for the solvability of the respective network problem or for its efficient solution. In [18] the authors compared the minimum size of advice required to solve two information dissemination problems using a linear number of messages. In [19] the authors established the size of advice given to a mobile agent, needed to break competitive ratio 2 of an exploration algorithm in trees. In [20] it was shown that advice of constant size permits to carry on the distributed construction of a minimum spanning tree in logarithmic time. In [17] the authors established lower bounds on the size of advice needed to beat time $\Theta \left({log}^{\ast }n\right)$ for 3-coloring of a cycle and to achieve time $\Theta \left({log}^{\ast }n\right)$ for 3-coloring of unoriented trees. It was also shown that, both for trees and for cycles, advice of size $\Omega \left(n\right)$ is needed to 3-color in constant time. In the case of [30] the issue was not efficiency but feasibility: it was shown that $\Theta (nlogn)$ is the minimum size of advice required to perform monotone connected graph clearing, using the minimum number of searchers. In [24] the authors studied radio networks for which it is possible to perform centralized broadcasting in constant time by a distributed algorithm. They proved that $O\left(n\right)$ bits of advice allow to obtain constant time in such networks, while $o\left(n\right)$ bits are not enough. In [21] the trade-off between the size of advice and broadcasting time in trees was investigated, assuming that advice is given only to the source of broadcasting. In [16] the authors studied on-line computation with advice.

Computability in anonymous networks and feasibility of distributed tasks performed using message exchange in anonymous networks, without advice, have been studied, e.g., in [3], [8], [33], [35]. Rendezvous was considered in this context, e.g., in [13].

The concept of quotient graphs, which we use as defined in [35], has been studied extensively in different settings and under different names, such as minimum base. Boldi and Vigna provide a detailed description of fibrations, defined for the more general case of directed graphs [9]. In particular, they give a polynomial-time (off-line) algorithm that for a given graph computes its minimum base. Fibrations have been used e.g. in [7] for the leader election problem, which is a classical symmetry breaking problem, where it is assumed that the processors are indistinguishable and communicate over the network by exchanging messages. For some further work on the leader election problem and on the problem of assigning unique labels to the processors in a distributed system see [10], [23], [28]. The concept of quotient graph has been studied earlier in [3] using the notion of coverings, for the scenario of message passing systems. Both coverings and fibrations are often used to determine the situations where finding a solution to some problem is impossible due to the symmetry of the graph. Informally speaking, if a base graph or a graph covered by the graph that models the network map several nodes of the network into the same class, then all those nodes perform the same computation, and therefore they cannot be distinguished. In our case nodes are indistinguishable for an agent exploring the network. Our proof techniques have some similarities to the ones used in the above-mentioned papers, as proving such results usually reduces to the construction of two graphs in which the execution of the algorithm is identical. However, in this work we deal with graph exploration by an agent, rather than with message passing systems and hence symmetry breaking issues are sometimes different (in the presence of a single agent the leader election problem becomes trivial). Métivier et al. [29] proved that some additional knowledge (the size of the graph) must be provided to the nodes of the graph to make several computational tasks feasible in the message passing model.

Some of the techniques we apply, e.g. the idea of connecting independent isomorphic components with a cycle in order to obtain a graph of desired multiplicity (that we use in Lemma 4.1 and Proposition 5.1), are similar to those present in [6], [32].