Towards survivable network design using approximation algorithms

July 12, 2024

Algorithms applied by Dylan Hyatt-Denesik strengthen the connectivity of networks and ensure continued operation in the event of node failure

Today's society relies heavily on networks for a great variety of applications. Telecommunications and transportation, for example, cannot be imagined without the use of networks. While networks must first and foremost perform their task of enabling communication or transporting goods or people, on the other hand, they must be resilient enough to meet the challenges that real life presents to them. PhD researcher Dylan Hyatt-Denesik aims to tackle these demands by providing algorithms that take a given network and increase its level of connectivity. He defended his thesis on Wednesday, July 10^th.

PhD researcher Dylan Hyatt-Denesik

Augmenting edge connectivity

Hyatt-Denesik's work focuses primarily on the survivable network design problem of edge connectivity augmentation. In this, additional connections should be added to an existing network by an algorithm. The advantage of the added connections is that when a single node fails, the overall connectivity of the network remains intact. In addition to augmenting the network to be resilient to failures, the goal of the algorithm is to select the fewest number of links possible in order to reach the desired connectivity properties.

Optimizing runtime efficiency

One major stumbling block that occurs when tackling these problems in all but the simplest instances is that of runtime efficiency. This refers to the efficiency of an algorithm concerning the time it takes to execute based on the size of the input. The lower the runtime complexity, the more efficient the algorithm. To optimize runtime complexity, Hyatt-Denesik introduced Approximation Algorithms, which trade finding an optimal solution inefficiently with efficiently finding a solution that is suboptimal but guaranteed to be within some specific fraction of the optimal value.

Flexible edge connectivity

In addition to the connectivity augmentation, Hyatt-Denesik also considered a problem that has been recently introduced in the field of network design: the Edge (or Vertex) Flexible Connectivity problem. This involves identifying a network whose edges (or nodes) are considered safe or unsafe. The researcher then tries to select the smallest number of edges so that the failure of an unsafe edge (or node) does not break the network. To do so, Hyatt-Denesik provided the first better-than-2 approximation for Flexible Vertex Connectivity, and also improved the currently best-known approximation factor for Flexible Edge Connectivity.

Hyatt-Denesik’s work provides a valued contribution to the reliability and safety of networks, which is essential for us all. In the future, other researchers can further build on his work.

Title of PhD thesis: Approximation Algorithms for Connectivity Augmentation and Flexible Graph Connectivity
Supervisors: L. Sanità, prof.dr. F.C.R. Spieksma