1
A Comprehensive Study on Pathfinding in Dynamic Graphs Using Automaton and Two-Way Depth-First Search

Ajayaditya L.1 and Anitha N.2*

1Department of Mechatronics, Kumaraguru College of Technology, Coimbatore, India

2Department of Mathematics, Kumaraguru College of Technology, Coimbatore, India

Abstract

Efficient pathfinding in time-varying directed acyclic graphs is crucial for numerous applications, necessitating incremental updates and maintenance of connectivity. This paper presents a formal automata-theoretic approach combining graph automata, graph transducers, and two-way search techniques. Graph automata model the dynamic acyclic graph evolution, transitioning between configurations. Graph transducers apply transformation rules to handle dynamic changes such as node and edge additions, removals, and property modifications. Two-way breadth-first and depth-first searches augmented with graph walking automata explore the dynamic acyclic graphs, computing potential paths and reconnecting affected routes. Incremental path update algorithms identify impacted regions, apply transducer rules, and reconnect paths via localized two-way searches. Path optimization strategies further enhance efficiency. Comprehensive mathematical formulations, algorithms, and complexity analyses demonstrate the approach's rigor and applicability to resilient pathfinding in evolving dynamic acyclic graphs.

Keywords: Directed acyclic graphs (DAGs), dynamic graphs, incremental pathfinding, graph automata, graph transducers, two-way search, graph walking automata

1.1 Introduction

Directed acyclic graphs (DAGs) are a type of directed graph with no cycles, meaning that there are no paths that start and end at the same vertex while traversing the same set of edges. DAGs have numerous applications in fields such as task scheduling, data processing pipelines, and network routing. In many real-world scenarios, these DAGs are not static but rather evolve over time, with vertices (nodes) and edges being added, removed, or modified. We refer to such structures as time-varying or dynamic DAGs.

Efficiently finding and maintaining paths in these dynamic DAGs is a critical problem with applications in areas like network routing, where the network topology may change due to link failures or additions, necessitating the recomputation or update of existing paths. Traditional pathfinding algorithms like Dijkstra's or breadth-first search (BFS) can be employed to compute paths from scratch after each change, but this approach can be computationally expensive, especially for large graphs or frequent changes.

In this paper, we present a formal automata-theoretic approach that combines graph automata, graph transducers, and two-way search techniques to enable efficient incremental pathfinding in time-varying DAGs. Our approach aims to update and maintain existing paths in response to dynamic changes, rather than recomputing them from scratch, thereby reducing computational overhead and improving overall efficiency.

1.1.1 Literature Review

The problem of finding and maintaining paths in dynamic graphs has been extensively studied in various domains, including computer networks, transportation systems, and task scheduling. Several approaches have been proposed to address this challenge, ranging from classical algorithms to more sophisticated techniques involving automata theory and formal methods.

Conventional pathfinding techniques, like BFS [2] and Dijkstra's algorithm [1], are typically utilized for recalculating paths whenever there is a modification in the graph's configuration. However, these approaches can be computationally expensive, especially for large graphs or scenarios with frequent dynamic changes [3].

To address this limitation, incremental pathfinding algorithms have been developed, which aim to update and maintain existing paths more efficiently by exploiting the structural properties of the graph and the locality of changes. King's algorithm [4] and its variants [5, 6] are notable examples of incremental pathfinding techniques for dynamic graphs.

In recent years, researchers have explored the use of automata theory and formal methods for modeling and reasoning about dynamic graph structures. Graph automata [7, 8] and graph transducers [9, 10] have emerged as powerful tools for representing and transforming graph structures, respectively.

Eppstein et al. [11] introduced the concept of incremental graph automata, which can efficiently update their state in response to dynamic changes in the graph. This work laid the foundation for subsequent research on automata-based approaches to incremental pathfinding.

Approaches based on graph grammars and graph transformation systems have also been proposed for modeling and analyzing dynamic graphs [12, 13].

These techniques allow for the specification of graph rewriting rules and the implication of transformations to update the graph.

The concept of two-way search, which involves exploring the graph from both the source and target vertices simultaneously, has been employed to improve the efficiency of pathfinding algorithms [14, 15]. Bidirectional search techniques have been shown to be particularly effective for dynamic graphs, as they can leverage previously computed paths and reconnect them after changes in the graph structure [16, 17].

In the domain of network routing, techniques such as the Routing Information Protocol [18] and the Open Shortest Path First protocol [19] have been developed to handle dynamic changes in network topologies. These protocols utilize incremental updates and dissemination of routing information to efficiently maintain paths and routing tables.

While the above-mentioned works have made significant contributions to the field of dynamic graph pathfinding, the integration of automatatheoretic concepts, graph transducers, and two-way search techniques has received limited attention. Our proposed approach aims to combine these formal methods to enable efficient incremental pathfinding in time-varying DAGs.

1.2 Preliminaries

1.2.1 Directed Acyclic Graphs (DAGs)

A DAG G = (V, E, S, ?) is a labeled directed graph, where

• V: the set of vertices (nodes),
• E ? V × V: the set of directed edges,

  Figure 1.1 Directed acyclic graph.

• S: the set of vertex labels, and
• ?: V S is the vertex labeling function, assigning labels to vertices.

A DAG contains directed edges with no cycles, meaning that there are no paths that start and end at the same vertex while traversing the same set of edges. Formally, a DAG satisfies the following condition:

where E+ represents the transitive closure of the edge relation 5, representing all possible paths present in the given graph G.

Figure 1.1 illustrates an example of a DAG with labeled vertices. In this graph, there are no paths that start and end at the same vertex, ensuring the acyclicity property. DAGs have numerous applications in fields such as task scheduling, data processing pipelines, and network routing, where the absence of cycles is a desirable property.

In many real-world scenarios, DAGs are not static but rather evolve over time, with vertices and edges being added, removed, or modified. We refer to such structures as time-varying or dynamic DAGs. Efficiently finding and maintaining paths in these dynamic DAGs is a critical problem with applications in areas like network routing, where the network topology may change due to link failures or additions, necessitating the recomputation or update of existing paths.

1.2.2 Dynamic Graphs

A dynamic graph G´ = (Gt)t?