| Naslov: | Computing tree decompositions with small independence number |
|---|
| Avtorji: | ID Dallard, Clément Jean (Avtor)
ID Fomin, Fedor V. (Avtor)
ID Golovach, Petr A. (Avtor)
ID Korhonen, Tuukka (Avtor)
ID Milanič, Martin (Avtor) |
|---|
| Datoteke: |  RAZ_Dallard_Clement_Jean_2026.pdf (1,45 MB)
MD5: 429042850FF9E8EA628A32E483E28311
 https://dl.acm.org/doi/10.1145/3767730
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Članek v reviji |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: | FAMNIT - Fakulteta za matematiko, naravoslovje in informacijske tehnologije
IAM - Inštitut Andrej Marušič
|
|---|
| Opis: | 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. |
|---|
| Ključne besede: | tree-independence number, approximation, parameterized algorithm |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 10.11.2025 |
|---|
| Leto izida: | 2026 |
|---|
| Št. strani: | str. 1-26 |
|---|
| Številčenje: | Vol. 22, no. 1, [article no.] 12 |
|---|
| PID: | 20.500.12556/RUP-22213  |
|---|
| UDK: | 51 |
|---|
| ISSN pri članku: | 1549-6325 |
|---|
| DOI: | 10.1145/3767730 |
|---|
| COBISS.SI-ID: | 261744131 |
|---|
| Datum objave v RUP: | 16.12.2025 |
|---|
| Število ogledov: | 195 |
|---|
| Število prenosov: | 3 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
