Report
Tree independence number V. Walls and claws
| العنوان: | Tree independence number V. Walls and claws |
|---|---|
| المؤلفون: | Chudnovsky, Maria, Codsi, Julien, Lokshtanov, Daniel, Milanič, Martin, Sivashankar, Varun |
| سنة النشر: | 2025 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, Computer Science - Discrete Mathematics, Computer Science - Data Structures and Algorithms, 05C75 (Primary) 05C40, 05C85 (Secondary) |
| الوصف: | Given a family $\mathcal{H}$ of graphs, we say that a graph $G$ is $\mathcal{H}$-free if no induced subgraph of $G$ is isomorphic to a member of $\mathcal{H}$. Let $S_{t,t,t}$ be the graph obtained from $K_{1,3}$ by subdividing each edge $t-1$ times, and let $W_{t\times t}$ be the $t$-by-$t$ hexagonal grid. Let $\mathcal{L}_t$ be the family of all graphs $G$ such that $G$ is the line graph of some subdivision of $W_{t \times t}$. We prove that for every positive integer $t$ there exists $c(t)$ such that every $\mathcal{L}_t \cup \{S_{t,t,t}, K_{t,t}\}$-free $n$-vertex graph admits a tree decomposition in which the maximum size of an independent set in each bag is at most $c(t)\log^4n$. This is a variant of a conjecture of Dallard, Krnc, Kwon, Milani\v{c}, Munaro, \v{S}torgel, and Wiederrecht from 2024. This implies that the Maximum Weight Independent Set problem, as well as many other natural algorithmic problems, that are known to be NP-hard in general, can be solved in quasi-polynomial time if the input graph is $\mathcal{L}_t \cup \{S_{t,t,t},K_{t,t}\}$-free. As part of our proof, we show that for every positive integer $t$ there exists an integer $d$ such that every $\mathcal{L}_t \cup \{S_{t,t,t}\}$-free graph admits a balanced separator that is contained in the neighborhood of at most $d$ vertices. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2501.14658 |
| رقم الانضمام: | edsarx.2501.14658 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |