Customized Project N1-0370
Beyond Sparsity: Graph Classes and Width Parameters 

 

Project Title: Beyond Sparsity: Graph Classes and Width Parameters

PI: Martin Milanič

Project Code: N1-0370

Type of the Project: costomized project.

Funding Organization: Slovenian Research and Innovation Agency (ARIS).

Research Field (ARRS): 1.01.00 - Natural Sciences and Mathematics / Mathematics.

Duration: 1. 6. 2024 - 31. 5. 2027.

Project Category: C.

Yearly Range: 0,59 FTE (1.008 research hours per year).

Sicris profile of the project is avaliable here.

Research Organizations:
Univerza na Primorskem, Inštitut Andrej Marušič
University of Primorska, UP FAMNIT

Project Members:

Martin Milanič (ARIS code: 30211)

Matjaž Krnc (ARIS code: 34562)

Nina Chiarelli (ARIS code: 35452)

Peter Muršič (ARIS code: 53028)

Claire Hilaire (ARIS code: 58123)

Kenny Štorgel (ARIS code: 53598)

Abstract:

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, with applications in many areas including algorithmic graph theory, complexity theory, and property testing. A recent focus of structural and algorithmic graph theory has been to extend the graph sparsity theory to dense graph classes. The proposed project aims at introducing novel ways and methods 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 on graph 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, with the 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 improved understanding of the boundaries of tractability for maximum independent set and several other practically relevant graph optimization problems.