Tilbake til søkeresultatene

FRINATEK-Fri prosj.st. mat.,naturv.,tek

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

Alternativ tittel: CLASSIS: Renessanse av grafklasser - Ny algoritmisk teori av forbudte induserte delgrafer

Tildelt: kr 9,0 mill.

En algoritme er en rekke med instruksjoner på hvordan et problem skal løses av en datamaskin. Algoritmer former grunnmuren av informatikkfaget. Grafalgoritmer er en sentral del av algoritmefeltet. Ethvert nettverk, som Internett, sosiale nettverk, kommunikasjonsnettverk osv, er en graf, og dermed er grafer gode teoretiske verktøy for å behandle nettverksproblem. Men bruken av grafer begrenser seg ikke til nettverk; grafer gir en naturlig måte å modellere mange interessante problem innen informatikk. Dessverre er de fleste interessante grafproblem meget vanskelige, på den måten at vi ikke har effektive algoritmer for å løse dem. Et eksempel på et slik problem er tildeling av frekvenser til sendere slik at sendere som er innen rekkevidden av hverandre får ulik frekvens. Dette kan vi modellere med å lage en graf der hver node er en sender og vi har en forbindelse mellom par av sendere som er innefor hverandres rekkevidde. Å tildele frekvenser til senderne samtidig holde seg til færrest mulig frekvenser totalt kan oversettes til et fargeleggingsproblem. Vi ønsker å tildele farger til nodene av grafen vår, der vi vil ta færrest mulig farger totalt, og hver forbindelse skal ha ulik farge på sine to endepunkter. Dette problemet er svært vanskelig selv når vi forsøker med kun 3 farger, og vi har ingen effektive algoritmer for å løse det på generelle grafer. Men om vi ser på grafer (nettverk) med bestemte egenskaper, i stedet for generelle, så kan vi løse problemet med meget effektive algoritmer. I dette prosjektet har vi sett på mange ulike vanskelige grafproblem av typen forklart ovenfor, og vi har løst dem effektivt for de tilfeller der inndatagrafene har bestemte strukturer. I stedet for å gjøre små fremskritt på ulike problem og grafklasser med ulik struktur, har vi systematisk gått til verks på mange problem samtidig for å kartlegge grensen på når et problem blir vanskelig, dvs hvor grensen går mellom hvilke typer grafer kan håndteres effektivt og hvilke typer grafer forblir uhåndterbare. Å definere en god grense på når et problem kan løses effektivt og når det blir vanskelig betyr å ta et vanskelig problem og finne så store grafklasser som mulig med struktur der problemet kan løses effektivt. Jo bedre denne grensen er jo mer informasjon får vi angående vanskeligheten av problemet og hva slags egenskaper i en graf gjør problemet vanskelig. Dette igjen gir oss algoritmer for å løse problemet effektivt i de aller fleste tilfeller. De mest kjente problemene vi har gjort store fremskritt på er: flere typer fargeleggingsproblemer, flere typer domineringsproblemer, flere typer delgrafproblemer og flere typer partisjoneringsproblemer. Takket være resultatene fra prosjektet har man nå bedre muligheter til å kunne løse disse problemene effektivt for de fleste tilfeller.

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.

Budsjettformål:

FRINATEK-Fri prosj.st. mat.,naturv.,tek