1. Computing tree decompositions with small independence numberClé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: 256; Downloads: 4
 Full text (1,45 MB)
This document has more files! More... |
2. Induced minor models : Structural properties and algorithmic consequencesNicolas Bousquet, Clément Jean Dallard, Maël Dumas, Claire Hilaire, Martin Milanič, Anthony Perez, Nicolas Trotignon, 2026, original scientific article Abstract: A graph H is an induced minor of G if there exists an induced minor model of H in G, that is, a collection of pairwise disjoint subsets of vertices of G labeled by the vertices of H, each inducing a connected subgraph in G, such that two vertices of H are adjacent if and only if there is an edge in G between the corresponding subsets. In this paper, we investigate structural properties of induced minor models, including bounds on treewidth and chromatic number of the subgraphs induced by minimal induced minor models. As algorithmic applications of our structural results, we make use of recent developments regarding tree-independence number to show that if H is the 4-wheel, the 5-vertex complete graph minus an edge, or a complete bipartite graph K2,q , then there is a polynomial-time algorithm to find in a given graph G an induced minor model of H in G, if there is one. We also develop an alternative polynomial-time algorithm for recognizing graphs that do not contain K2,3 as an induced minor, which revolves around the idea of detecting the induced subgraphs whose presence is forced when the input graph contains K2,3 as an induced minor. It turns out that all these induced subgraphs are Truemper configurations.
Keywords: induced minor, treewidth, chromatic number, tree-independence number, Truemper configuration
Published in RUP: 16.12.2025; Views: 227; Downloads: 3
Full text (1,44 MB)
This document has more files! More... |
3. The independence polynomial of trees is not always log-concave starting from order 26Ohr Kadrawi, Vadim Levit, 2025, original scientific article Abstract: An independent set in a graph is a collection of vertices that are not adjacent to each other. The cardinality of the largest independent set in G is represented by α(G). The independence polynomial of a graph G = (V, E) was introduced by Gutman and Harary in 1983 and is defined as
I(G; x) = Σ_{k = 0}^α(G) s_k x^k = s₀ + s₁x + s₂x² + ... + s_α(G)x^α(G), where sk represents the number of independent sets in G of size k.
The problem raised by Alavi, Malde, Schwenk, and Erdös in 1987 stated that the independence polynomials of trees are unimodal, and many researchers believed that this problem could be strengthened up to its corresponding log-concave version. However, in 2023, this conjecture was shown to be false by Kadrawi, Levit, Yosef, and Mizrachi. In this paper, we provide further evidence against this conjecture by presenting infinite families of trees with independence polynomials that are not log-concave.
Keywords: tree, independent set, independence polynomial, unimodality, log-concavity
Published in RUP: 22.10.2025; Views: 419; Downloads: 1
Full text (352,77 KB) |
4. On relationships between treewidth, clique number, tree-independence number, and induced minors : master’s thesisÐorđe Vasić, 2025, master's thesis Keywords: treewidth, clique number, tree-independence number, induced minor, hered itary graph class, bipartite chain graph
Published in RUP: 11.09.2025; Views: 738; Downloads: 9
Full text (839,36 KB) |
5. |
6. User needs and perspectives on technologies or healthy ageingMateja Erce Paoli, Rok Ovsenik, Dean Lipovac, Michael David Burnard, 2021, published scientific conference contribution abstract Keywords: older adults, building solutions, technology acceptance, well-being, independence
Published in RUP: 24.06.2021; Views: 2836; Downloads: 61
Full text (1,75 MB)
This document has more files! More... |
7. Mind the independence gapTinaz Ekim, Didem Gozüpek, Ademir Hujdurović, Martin Milanič, 2020, original scientific article Keywords: maximal independent set, independent dominating set, well-covered graph, hereditary independence gap, polynomial-time algorithm, NP-hard problem
Published in RUP: 19.05.2020; Views: 4108; Downloads: 63
 Link to full text |
8. |
9. |
10. Coding theory and applications, solved exercises and problems of linear codesEnes Pašalić, 2013, other educational material Keywords: Gilbert-Eliot channel model, linear code, linear block code, code design, undetected error probability, linear independence, standard form, codeword weight, code rate, systematic code, Binary Hamming code
Published in RUP: 15.10.2013; Views: 6974; Downloads: 105
Link to full text |
