Onkraj redkosti: razredi grafov in širinski parametri / Beyond Sparsity: Graph Classes and Width Parameters

Teorija redkih grafov Nešetřila in Ossone de Mendeza je zelo aktivna in hitro razvijajoča se tema v kombinatoriki in teoriji grafov z aplikacijami naštevilnih področjih, vključno z algoritmično teorijo grafov, teorijo kompleksnosti in testiranjem lastnosti. Nedavno se je strukturna in algoritmičnateorija grafov osredotočila na razširitev teorije redkih grafov na goste razrede grafov. Cilj predlaganega projekta je uvesti nove načine in metode zadosego tega cilja. To bo potekalo v okviru naslednjih dveh med seboj povezanih raziskovalnih smeri:

– prvič, z napredovanjem nedavno nastajajoče in hitro razvijajoče se teorije širinskih in globinskih parametrov grafov prek splošnega okvira, ki temeljina merah grafov in poglobljeni analizi znanih in novih parametrov grafov;

– drugič, z razvojem biparametrične teorije hereditarnih razredov grafov, v katerih je nek parameter omejen s funkcijo drugega, s ciljem identificiratinetrivialne strukturne in algoritmične posledice.

Predlagan pristop dopolnjuje teorijo razredov grafov z omejeno širino obračanja, ki jo je pred kratkim razvil Toruńczyk, in bo vodil do boljšegarazumevanja meja učinkovite rešljivosti problema največje neodvisne množice in več drugih praktično pomembnih optimizacijskih problemov nagrafih.

The Graph Sparsity Theory of Nešetřil and Ossona de Mendez is a highly active and rapidly developing topic in combinatorics and graph theory, withapplications in many areas including algorithmic graph theory, complexity theory, and property testing. A recent focus of structural and algorithmicgraph theory has been to extend the graph sparsity theory to dense graph classes. The proposed project aims at introducing novel ways andmethods of addressing this goal. This will be done along the following two interconnected research lines:

– first, by advancing the recently emerging and fast developing theory of graph width and depth parameters through a general framework based ongraph measures and an in-depth analysis of known and novel graph parameters;

– second, by developing a biparametric theory of hereditary graph classes in which some parameter is bounded by a function of another one, withthe goal of identifying nontrivial structural and algorithmic implications.

Our approach is complementary to the theory of graph classes with bounded flip-width developed recently by Toruńczyk and will lead to an improvedunderstanding of the boundaries of tractability for maximum independent set and several other practically relevant graph optimization problems.