CLASSIS: The renaissance of graph classes - New algorithmic theory of forbidden induced subgraphs

Algorithms are step-wise precise instructions on how to solve a problem on a computer, and they form the core of the discipline of computer science. Graph algorithms constitute a central part of the algorithms field. Every network, like the Internet, social networks and communication networks, is a graph. Therefore graphs provide the theoretical toolbox to handle all network problems. However, their use is not restricted to networks; graphs naturally model a wide range of computer science problems. Unfortunately, most interesting graph problems are hard, in the sense that we do not know efficient algorithms for them. An example of such a problem is the assignment of frequencies to transmitters in such a way that transmitters that are in the range of each other get different frequencies. We can model this a s a graph where every transmitter is a node and there is a link between pairs of nodes that are in the range of each other. Assigning frequencies to the transmitters and at the same time minimizing the total number of different frequencies can be translated as a graph coloring problem. We want to color the nodes of the graph with as few colors as possible such that the endpoints of every link get different colors. This problem is vary hard even when we try with just 3 colors, and we have no efficient algorithms for solving it on general graphs. However, when we we want to solve it on graphs with particular structure, we have several very efficient algorithms. In this project we have studied many different hard graph problems of the type explained above, and we have solved them efficiently in cases where the input graphs have particular restricted structures. Instead of providing small improvements for various problems on various graph classes with structure, we have systematically worked on drawing the border of when a problem becomes difficult, i.e., the border between graphs that can be handled efficiently and graphs on which the problem remains intractable. To define a good border between when a problem can be solved efficiently and when it is hard, means taking a hard problem and finding as large graph classes as possible with structure on which the problem can be solved efficiently. The better this border is defined the more information we get about the difficulty of the problem and what kind of properties in a graph makes the problem hard. This again gives us algorithms to solve the problem efficiently on most instances. The most famous graph problems we have achieved significant progress in this project are: various types of coloring problems, various types of domination problems, various types of subgraph problems and various types of partitioning problems. Thanks to the results of this project, there are now better possibilities to be able to solve these problems efficiently for most cases.

I dette prosjektet har vi sett på mange ulike vanskelige (såkalt NP-harde) grafproblem, og vi har løst dem effektivt for de tilfeller der inndatagrafene har bestemte strukturer. Vi har vist hvilke algoritmiske metoder gir effektive løsninger for hvilke typer problem og hvilke typer grafer. De mest kjente problemene vi har gjort store fremskritt på er: fargeleggingsproblemer, domineringsproblemer, delgrafproblemer og partisjoneringsproblemer. Takket være resultatene fra prosjektet har man nå bedre muligheter til å kunne løse disse problemene effektivt for de fleste tilfeller. Samtidig gir våre resultater indikasjoner på hvilke typer algoritmiske metoder kan være nyttige for hvilke typer av generelt NP-harde problem.

Algorithms are step-wise precise instructions on how to solve a problem on a computer, and they form the core of computer science. Graph algorithms constitute a central part of the algorithms field. As in many areas of computer science, most important graph problems are NP-hard; hence we do not expect to be able to solve all their instances efficiently. On the other hand, most interesting instances of these problems have structural properties that may be exploited algorithmically. A framework to study this phenomenon systematically is provided by graph classes. Algorithms tailored to exploit properties of various graph classes form an important area within graph algorithms. This project proposes a paradigm shift in algorithmic research on graph classes in computer science. The field holds the potential to push the boundaries of current computational limitations, as well as the key to fundamental understanding of which instances of hard problems are efficiently solvable. However, as of today, it is not equipped to take advantage of major developments that have been made recently, both in algorithms and complexity, and in structural graph theory, to reach this potential. Hence, this is the right moment to redefine the pillars of algorithmic research involving graph classes. We propose to incorporate knowledge that has been gathered through the last decades to develop new algorithmic meta theory that can be applied to large groups of problems and a large number of graph classes. In particular, a complete classification of the computational complexities of graph problems related to graph classes is aimed. The main outcome of the project will be a modern theory of algorithmic research involving graph classes, with a complete set of new tools and methods that can be applied to large areas of problems. More fundamentally, the outcomes will eventually lead to deeper understanding of what is efficiently computable in general, a knowledge we are far from today.