Reducing the computation time of existing algorithms

July 13, 2023

How to avoid undesirable deadlocks in mathematical graphs

A graph is a mathematical notion that can be used to represent relations or connections between certain objects, called vertices. For instance, a road network can be seen as a graph with cities as vertices and roads as connections between cities. Another example is the part of an operating system which aims to schedule processes to be executed, where so called deadlocks can occur. In his thesis, Jari de Kroon researched how to prevent these from happening. He defended his thesis on July 4.

In the case of an operating system which aims to schedule processes to be executed, a graph has processes as its vertices, while connections could for instance indicate that one process is waiting for another one to be completed before it can be executed. In this example, any cyclic ordering of processes that are waiting on each other to be completed - called a deadlock - is undesirable. De Kroon studied the following class of graph modification problems: for a specific graph property, what is the minimum number of vertices that need to be deleted to obtain a graph with this property? In the operating system example, this equates to aborting the minimum number of processes that together remove all deadlocks from the graph.

PhD student Jari de Kroon

Bound running time

An algorithm is a sequence of steps that can be used to solve a well-defined task. The time it takes to complete these tasks typically increases as the input becomes larger. The analysis of these algorithms therefore aims to bound their running time in terms of the number of steps by a function of the input size. There is good evidence that no algorithm can optimally solve these graph modification problems in time that grows only moderately with the size of the input. Results from the area of parameterized complexity has shown that inputs with small solutions or inputs whose graph has some tree-like structure, can still be solved efficiently. In his thesis, De Kroon extends results from this area in two directions.

In the first direction, he takes a hybrid approach, by showing that instances where certain parts of the graphs have a small solution, whereas other parts of the graph have this tree-like structure, can still be solved efficiently. In a second direction, he provides algorithms that can detect vertices that need to be part of every solution that does not cost much more than an optimal solution. By deleting these vertices in a preprocessing phase, De Kroon reduced the computation time of the existing algorithms.

The main contributions are the following: Firstly, providing a framework for obtaining FPT algorithms for graph modification problems parameterized by hybrid parameters rather than the natural solution size parameter. Secondly, providing several preprocessing algorithms that allow the detection of so-called c-essential vertices for graph modification problems: those vertices that need to be part of all solutions of size at most c times the size of an optimal solution. These preprocessing algorithms reduce the computation time of existing algorithms for these problems.

Title of PhD thesis: Parameterized Graph Modification Beyond the Natural Parameter

Supervisors: dr. Bart Jansen and prof.dr. Mark de Berg