Š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.