Efficient Approximation of Fractional Hypertree Width
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912051701481472 |
|---|---|
| author | Korchemna, Viktoriia Lokshtanov, Daniel Saurabh, Saket Surianarayanan, Vaishali Xue, Jie |
| author_facet | Korchemna, Viktoriia Lokshtanov, Daniel Saurabh, Saket Surianarayanan, Vaishali Xue, Jie |
| contents | We give two new approximation algorithms to compute the fractional hypertree width of an input hypergraph. The first algorithm takes as input $n$-vertex $m$-edge hypergraph $H$ of fractional hypertree width at most $ω$, runs in polynomial time and produces a tree decomposition of $H$ of fractional hypertree width $O(ω\log n \log ω)$. As an immediate corollary this yields polynomial time $O(\log^2 n \log ω)$-approximation algorithms for (generalized) hypertree width as well. To the best of our knowledge our algorithm is the first non-trivial polynomial-time approximation algorithm for fractional hypertree width and (generalized) hypertree width, as opposed to algorithms that run in polynomial time only when $ω$ is considered a constant. For hypergraphs with the bounded intersection property we get better bounds, comparable with that recent algorithm of Lanzinger and Razgon [STACS 2024].
The second algorithm runs in time $n^ωm^{O(1)}$ and produces a tree decomposition of $H$ of fractional hypertree width $O(ω\log^2 ω)$. This significantly improves over the $(n+m)^{O(ω^3)}$ time algorithm of Marx [ACM TALG 2010], which produces a tree decomposition of fractional hypertree width $O(ω^3)$, both in terms of running time and the approximation ratio.
Our main technical contribution, and the key insight behind both algorithms, is a variant of the classic Menger's Theorem for clique separators in graphs: For every graph $G$, vertex sets $A$ and $B$, family ${\cal F}$ of cliques in $G$, and positive rational $f$, either there exists a sub-family of $O(f \cdot \log^2 n)$ cliques in ${\cal F}$ whose union separates $A$ from $B$, or there exist $f \cdot \log |{\cal F}|$ paths from $A$ to $B$ such that no clique in ${\cal F}$ intersects more than $\log |{\cal F}|$ paths. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_20172 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Efficient Approximation of Fractional Hypertree Width Korchemna, Viktoriia Lokshtanov, Daniel Saurabh, Saket Surianarayanan, Vaishali Xue, Jie Data Structures and Algorithms Databases Discrete Mathematics G.2.2; G.2.0; F.2.0; F.2.2 We give two new approximation algorithms to compute the fractional hypertree width of an input hypergraph. The first algorithm takes as input $n$-vertex $m$-edge hypergraph $H$ of fractional hypertree width at most $ω$, runs in polynomial time and produces a tree decomposition of $H$ of fractional hypertree width $O(ω\log n \log ω)$. As an immediate corollary this yields polynomial time $O(\log^2 n \log ω)$-approximation algorithms for (generalized) hypertree width as well. To the best of our knowledge our algorithm is the first non-trivial polynomial-time approximation algorithm for fractional hypertree width and (generalized) hypertree width, as opposed to algorithms that run in polynomial time only when $ω$ is considered a constant. For hypergraphs with the bounded intersection property we get better bounds, comparable with that recent algorithm of Lanzinger and Razgon [STACS 2024]. The second algorithm runs in time $n^ωm^{O(1)}$ and produces a tree decomposition of $H$ of fractional hypertree width $O(ω\log^2 ω)$. This significantly improves over the $(n+m)^{O(ω^3)}$ time algorithm of Marx [ACM TALG 2010], which produces a tree decomposition of fractional hypertree width $O(ω^3)$, both in terms of running time and the approximation ratio. Our main technical contribution, and the key insight behind both algorithms, is a variant of the classic Menger's Theorem for clique separators in graphs: For every graph $G$, vertex sets $A$ and $B$, family ${\cal F}$ of cliques in $G$, and positive rational $f$, either there exists a sub-family of $O(f \cdot \log^2 n)$ cliques in ${\cal F}$ whose union separates $A$ from $B$, or there exist $f \cdot \log |{\cal F}|$ paths from $A$ to $B$ such that no clique in ${\cal F}$ intersects more than $\log |{\cal F}|$ paths. |
| title | Efficient Approximation of Fractional Hypertree Width |
| topic | Data Structures and Algorithms Databases Discrete Mathematics G.2.2; G.2.0; F.2.0; F.2.2 |
| url | https://arxiv.org/abs/2409.20172 |