Basic Research Project J1-4008
Tree-Independence Number of Graphs

 

Project Title: Tree-Independence Number of Graphs

PI: Martin Milanič.

Project Code: J1-4008

Type of the Project: basic research project.

Funding Organization: Slovenian Research Agency (ARRS).

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

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

Project Category: B.

Yearly Range: 1.46 FTE (2.481 research hours).

Sicris profile of the project is avaliable here.

Research Organizations:
Univerza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologije
Univerza v Ljubljani, Fakulteta za matematiko in fiziko
Univerza v Mariboru, Fakulteta za naravoslovje in matematiko
Fakulteta za informacijske študije - FIŠ

 

Project Members:

Martin Milanič (ARRS code 30211)

Nina Chiarelli (ARRS code 35452)

Edward Tauscher Dobson (ARRS code 34109)

Matjaž Krnc (ARRS code 34562)

Štefko Miklavič (ARRS code 21656)

Peter Muršič (ARRS code 53028)

Blas Fernandez (ARRS code 52892)

Nevena Pivač (ARRS code 50673)

Riste Škrekovski (ARRS code 15518)

Mirko Petrushevski (ARRS code 55615)

Slobodan Filipovski (ARRS code 37715)

Boštjan Brešar (ARRS code 17005)

Borut Lužar (ARRS code 31670)

Mirza Krbezlija (ARRS code 55941)

Kenny Štorgel (ARRS code 53598)

Abstract:

 

Various algorithmic problems on graphs have been extensively studied in Mathematics and Computer Science due to their many application areas crossing disciplinary boundaries. However, for many practically relevant problems the theory of computational complexity suggests—relying among other things on the notorious P ≠ NP conjecture—that efficient computation or approximation might in general not be possible. One of the approaches of dealing with an algorithmically hard problem is to identify restrictions on the input instances under which the problem becomes efficiently solvable. In the case of graph problems, one of the central tools for this task have become various measures of structural complexity of graphs, commonly known as graph width parameters. A number of algorithmic metatheorems have been developed in the literature for various graph width 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 tree-independence 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, Theme 2: refinements), each with a number of subtasks. We expect the proposed research to further demonstrate the usefulness of the tree-independence 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.