Search the repository

Computing tree decompositions with small independence number
Clément Jean Dallard, Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, Martin Milanič, 2026, original scientific article

Abstract: The independence number of a tree decomposition is the maximum of the independence numbers of the subgraphs induced by its bags. The tree-independence number of a graph is the minimum independence number of a tree decomposition of it. Several NP-hard graph problems, like maximum-weight independent set, can be solved in time n^O(k) if the input n-vertex graph is given together with a tree decomposition of independence number k. Yolov, in SODA 2018, gave an algorithm that, given an n-vertex graph G and an integer k, in time n^O(k^3) either constructs a tree decomposition of G whose independence number is O(k^3) or correctly reports that the tree-independence number of G is larger than k. In this article, we first give an algorithm for computing the tree-independence number with a better approximation ratio and running time and then prove that our algorithm is, in some sense, the best one can hope for. Our second result is that the exact computation of the tree-independence number is para-NP-hard: We show that for every constant k ≥ 4 it is NP-complete to decide whether a given graph has the tree-independence number at most k.
Keywords: tree-independence number, approximation, parameterized algorithm
Published in RUP: 16.12.2025; Views: 218; Downloads: 3
Full text (1,45 MB)
This document has more files! More...

Perfect phylogenies via branchings in acyclic digraphs and a generalization of Dilworth's theorem
Ademir Hujdurović, Martin Milanič, Edin Husić, Romeo Rizzi, Alexandru I. Tomescu, 2017, published scientific conference contribution abstract

Keywords: perfect phylogeny, NP-hard problem, branching, acyclic digraph, chain partition, Dilworth's theorem, min-max theorem, approximation algorithm, heuristic
Published in RUP: 17.09.2018; Views: 3795; Downloads: 125
Link to full text

Reconstructing perfect phylogenies via binary matrices, branchings in DAGs, and a generalization of Dilworth's theorem
Martin Milanič, 2018, published scientific conference contribution abstract (invited lecture)

Keywords: perfect phylogeny, NP-hard problem, graph coloring, branching, acyclic digraph, chain partition, Dilworth's theorem, min-max theorem, approximation algorithm, heuristic
Published in RUP: 17.09.2018; Views: 3399; Downloads: 22
Link to full text

The minimum conflict-free row split problem revisited
Ademir Hujdurović, Edin Husić, Martin Milanič, Romeo Rizzi, Alexandru I. Tomescu, 2016, published scientific conference contribution

Keywords: #the #minimum conflict-free row split problem, branching, Dilworth's theorem, min-max theorem, approximation algorithm, APX-hardness
Published in RUP: 14.11.2017; Views: 5030; Downloads: 287
Link to full text
This document has more files! More...