Širinski parametri in barvanje grafov / Widths and coloring of graphs

Številne praktične probleme na področju računalništva, načrtovanja urnikov ali splošneje operacijskih raziskav je mogoče modelirati z grafi, matematičnimi strukturami, ki predstavljajo interakcije med objekti. Večina praktično zanimivih algoritmičnih problemov na grafih je žal težkih (so NP-polni). Veliko raziskav je bilo zato namenjenih razumevanju, v katerem razredu grafov je določen problem mogoče rešiti učinkovito, in s kakšnim parametrom lahko izmerimo, kako zapleten je graf glede na kompleksnost velikega razreda algoritmov, ki jih je na grafu mogoče izvajati.

Zanimajo nas številni problemi na grafih, vendar pa zaradi preprostosti razlage na tem mestu omenimo le problema največje neodvisne množice in barvanja grafov. Dobro je znano, da je te probleme mogoče učinkovito rešiti za razrede grafov, ki so omejeni za enega od več klasičnih parametrov, kot so drevesna širina, klična širina ali rangovna širina, glej npr. [2,4,6]. (V nadaljevanju bomo uporabili preprosto besedo širina, ko želimo podati neko izjavo o poljubnem od teh treh širinskih paramterov.) Še vedno pa so odprti za znane razrede, na primer za grafe brez sodih lukenj (glej npr. [7]), ki so v zadnjem času pritegnili nekaj pozornosti. Tudi za sloviti razred popolnih grafov povsem kombinatorični algoritmi za te probleme niso znani (glej npr. [1]).

Cilj našega projekta je združiti raziskovalce z različnim znanjem in izkušnjami, da bi raziskali, kako te parametre uporabiti za pridobivanje novih algoritmov.

ANG

Many practical problems in computer science, scheduling, or more generally operations research can be modeled by graphs, mathematical structures representing interaction between objects. However, most algorithmic problems of practical interest for graphs are intractable (NP-complete), so there has been a lot of research devoted to understanding in what class of graphs a given problem can be solved efficiently, or what parameter can measure how complex a graph is regarding the complexity of large classes of algorithms that can be run for them.

We are interested in many problems for graphs, but for simplicity of the explanation of project, we just mention here the maximum stable set and graph coloring. It is well known that these problems are tractable for graph classes that are bounded for several classical parameters such that treewidth, cliquewidth, or rankwidth, see, e.g., [2,4,6] (we simply use the word width when want to write a statement about these three widths in what follows). And they remain open for famous classes, such as even-hole-free graphs (see, e.g., [7]), that attracted some attention lately. Also, for the famous class of perfect graphs, these problems are not known to be solved by a polynomial-time purely combinatorial algorithm (see, e.g., [1]).

The goal of our project is to bring together researchers with different expertise to work on how these parameters might be used to obtain new algorithms.