Tree-Independence Number of Graphs

Project presentation

Title: Tree-Independence Number of Graphs

Project Code: J1-4008

Leading institution: UP FAMNIT

Principal investigator at UP FAMNIT: prof. dr. Martin Milanič

Partner institutions: 

• UL Faculty of Mathematics and Physics
• UM Faculty of natural sciences and math (UM FNM)
• Faculty of information studies (FIŠ)

Funding organization: Slovenian Research and Innovation Agency (ARRS) 

Research field (ARRS): 1.01.00 - Natural sciences and mathematics

Project type: Basic research project

Duration: 1. 10. 2022 - 30. 9. 2025

Various algorithmic problems on graphs have been extensively studied in Mathematics and Computer Science due to their many application areascrossing disciplinary boundaries. However, for many practically relevant problems the theory of computational complexity suggests -- relying amongother things on the notorious P!= NP conjecture -- that efficient computation or approximation might in general not be possible. One of theapproaches of dealing with an algorithmically hard problem is to identify restrictions on the input instances under which the problem becomesefficiently solvable. In the case of graph problems, one of the central tools for this task have become various measures of structural complexity ofgraphs, commonly known as graph width parameters. A number of algorithmic metatheorems have been developed in the literature for various graphwidth parameters, including treewidth, branchwidth, clique-width, rank-width, Boolean-width, mim-width, and more recently also twin-width.

Despite a growing variety of graph width parameters and associated algorithmic results, there exist some well-structured graph classes in which all of the above width parameters remain unbounded, such as the class of chordal graphs. This class has an interesting property regarding a classical graph width parameter, treewidth. Roughly speaking, this parameter measures how similar the graph is to a tree. Graphs with large cliques necessarily have large treewidth; in chordal graphs the converse holds, too. Recently, Dallard, Milanič, and Štorgel initiated a systematic study of (treewidth, omega)-bounded graph classes, classes in which this sufficient condition for large treewidth—the presence of a large clique—is also necessary. The family of (treewidth, omega)-bounded graph classes provides a unifying framework for a variety of very different families of graph classes studied in the literature and enjoys some good algorithmic properties related to clique and coloring problems. An interesting open problem is whether (treewidth, omega)-boundedness has any further algorithmic implications, for example for problems related to independent sets.

In order to address this question, Dallard, Milanič, and Štorgel recently introduced the tree-independence number, a min-max graph width parameter related to tree decompositions. It follows from Ramsey's theorem that bounded tree-independence number implies (treewidth, omega)- boundedness. Graph classes of bounded tree-independence number include various families of graph classes, inherit all the good algorithmic properties of (treewidth, omega)-bounded graph classes, and have additional good properties regarding the independent set and related problems. Indeed, our initial results indicate that the tree-independence number is a worthy addition to the toolbox of structural and algorithmic graph theory. It not only forms a common generalization of treewidth and chordality, but is also related to the famous Erdős-Hajnal conjecture and to the flourishing theory of chi-boundedness. All these motivations lead to the main objective of the proposed project: a thorough and continued study of the treeindependence number, with the ultimate goal of developing a theory of this novel graph invariant. We plan to investigate a number of relevant questions split into two interrelated research themes (Theme 1: foundations of the tree-independence number, Theme 2: refinements of the treeindependence number), each with a number of subtasks. We expect the proposed research to further demonstrate the usefulness of the treeindependence number and related graph width parameters, resulting thus in increased understanding of structural properties of (treewidth, omega)- bounded graph classes and the computational complexity of various graph optimization problems on such classes.