Demo Data from VLDB 2026 / reviewers in the wild / expert
Amit Zivan
dblp:405/6206
· DBLP profile ↗
1ranked-venue papers
0as first author
1since 2021 · last 2025
—ORCID · none
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 1 · 1 since 2021
Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.
| Theoretical computer science
1 paper |
Graph algorithms and graph theory · 50% Computational complexity · 50% |
Topics — the 4 heaviest of 4, each with the papers that count most for it
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Computational complexity › parameterized complexity
feedback vertex set |
0.9 | 1 | 2025 | Treewidth Parameterized by Feedback Vertex Number · ICALP 2025 |
Computational complexity
parameterized complexity |
0.9 | 1 | 2025 | Treewidth Parameterized by Feedback Vertex Number · ICALP 2025 |
Graph algorithms and graph theory › graph decomposition
tree decomposition |
0.9 | 1 | 2025 | Treewidth Parameterized by Feedback Vertex Number · ICALP 2025 |
Graph algorithms and graph theory › graph theory › graph parameters › graph width parameters
treewidth |
0.9 | 1 | 2025 | Treewidth Parameterized by Feedback Vertex Number · ICALP 2025 |
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2025 | Treewidth Parameterized by Feedback Vertex NumberabstractWe provide the first algorithm for computing an optimal tree decomposition for a given graph $G$ that runs in single exponential time in the feedback vertex number of $G$, that is, in time $2^{O(\text{fvn}(G))}\cdot n^{O(1)}$, where $\text{fvn}(G)$ is the feedback vertex number of $G$ and $n$ is the number of vertices of $G$. On a classification level, this improves the previously known results by Chapelle et al. [Discrete Applied Mathematics '17] and Fomin et al. [Algorithmica '18], who independently showed that an optimal tree decomposition can be computed in single exponential time in the vertex cover number of $G$. One of the biggest open problems in the area of parameterized complexity is whether we can compute an optimal tree decomposition in single exponential time in the treewidth of the input graph. The currently best known algorithm by Korhonen and Lokshtanov [STOC '23] runs in $2^{O(\text{tw}(G)^2)}\cdot n^4$ time, where $\text{tw}(G)$ is the treewidth of $G$. Our algorithm improves upon this result on graphs $G$ where $\text{fvn}(G)\in o(\text{tw}(G)^2)$. On a different note, since $\text{fvn}(G)$ is an upper bound on $\text{tw}(G)$, our algorithm can also be seen either as an important step towards a positive resolution of the above-mentioned open problem, or, if its answer is negative, then a mark of the tractability border of single exponential time algorithms for the computation of treewidth. Hendrik Molter, Meirav Zehavi, Amit Zivan |
ICALP | 3 |