DVDaniel Vaz

Daniel Vaz

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Daniel Vaz has a total of 43 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Broadcasting Under Structural Restrictions

    by Yudai Egami, Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Michael Lampis, Valia Mitsou, Edouard Nemery, Yota Otachi, Manolis Vasilakis, Daniel Vaz

    In the Telephone Broadcast problem we are given a graph G = ( V , E ) with a designated source vertex s ∈ V . Our goal is to transmit a message, which is initially known only to s , to all vertices of the graph by using a process where in each round an informed vertex may transmit the message to one of its uninformed neighbors. The optimization objective is to minimize the number of rounds. Following up on several recent works, we investigate the structurally parameterized complexity of Telephone Broadcast . In particular, we first strengthen existing NP-hardness results by showing that the problem remains NP-complete on graphs of bounded tree-depth and also on cactus graphs which are one vertex deletion away from being path forests. Motivated by this (severe) hardness, we study several other parameterizations of the problem and obtain FPT algorithms parameterized by vertex integrity (generalizing a recent FPT algorithm parameterized by vertex cover by Fomin, Fraigniaud, and Golovach [TCS 2024]) and by distance to clique, as well as FPT approximation algorithms parameterized by clique-cover and cluster vertex deletion. Furthermore, we obtain structural results that relate the length of the optimal broadcast protocol of a graph G with its pathwidth and tree-depth. By presenting a substantial improvement over the best previously known bound for pathwidth (Aminian, Kamali, Seyed-Javadi, and Sumedha [ICALP 2025]) we exponentially improve the approximation ratio achievable in polynomial time on graphs of bounded pathwidth from \(\mathcal {O}(4^\mathrm{pw}) \) to \(\mathcal {O}(\mathrm{pw}) \) .

  • Buy-at-Bulk Facility Location on Trees

    by Shamisa Nematollahi, Daniel Vaz

  • Open Access

    Approximating Sparsest Cut in Low-treewidth Graphs via Combinatorial Diameter

    by Parinya Chalermsook, Matthias Kaul, Matthias Mnich, Joachim Spoerhase, Sumedha Uniyal, Daniel Vaz

    The fundamental Sparsest Cut problem takes as input a graph G together with edge capacities and demands and seeks a cut that minimizes the ratio between the capacities and demands across the cuts. For n -vertex graphs G of treewidth k , Chlamtáč, Krauthgamer, and Raghavendra (APPROX’10) presented an algorithm that yields a factor- \(2^{2^k}\) approximation in time \(2^{O(k)} \cdot n^{O(1)}\) . Later, Gupta, Talwar, and Witmer (STOC’13) showed how to obtain a 2-approximation algorithm with a blown-up runtime of \(n^{O(k)}\) . An intriguing open question is whether one can simultaneously achieve the best out of the aforementioned results, that is, a factor-2 approximation in time \(2^{O(k)} \cdot n^{O(1)}\) . In this article, we make significant progress towards this goal via the following results: (i) A factor- \(O(k^2)\) approximation that runs in time \(2^{O(k)} \cdot n^{O(1)}\) , directly improving the work of Chlamtáč et al. while keeping the runtime single-exponential in k . (ii) For any \(\varepsilon \in (0,1]\) , a factor- \(O(1/\varepsilon ^2)\) approximation whose runtime is \(2^{O(k^{1+\varepsilon }/\varepsilon)} \cdot n^{O(1)}\) , implying a constant-factor approximation whose runtime is nearly single-exponential in k and a factor- \(O(\log ^2 k)\) approximation in time \(k^{O(k)} \cdot n^{O(1)}\) . Key to these results is a new measure of a tree decomposition that we call combinatorial diameter , which may be of independent interest.

  • On Approximating Degree-Bounded Network Design Problems

    by Xiangyu Guo, Guy Kortsarz, Bundit Laekhanukit, Shi Li, Daniel Vaz, Jiayi Xian


  • Open Access

    Undernutrition risk at hospital admission and length of stay among pulmonology inpatients

    by I. Maia, S. Xará, D. Vaz, T. Shiang, T.F. Amaral

    There is a lack of evidence regarding the association between the undernutrition risk at hospital admission with adverse clinical outcomes amongst pulmonology inpatients. The aim of this study was to quantify the association between undernutrition risk at hospital admission and time to discharge alive. A retrospective cohort study including patients consecutively admitted to a pulmonology unit was conducted. Undernutrition risk at hospital admission was identified using the Malnutrition Universal Screening Tool. Survival analyses (Kaplan-Meier curves and Cox regression) were carried out. The sample was composed of 683 patients. Patients who presented high undernutrition risk on hospital admission had a longer length of hospital stay (approximately 50% were discharged to home after 14 days of hospitalization). In the multivariable Cox regression, high undernutrition risk was shown to be independently associated with a lower probability of discharge alive over time (adjusted hazard ratio=0.70; 95% confidence interval: 0.55-0.90). Pulmonology inpatients with high undernutrition risk have a longer length of hospital stay and had a lower probability of being discharged to home. In particular, lung cancer patients had a lower probability of being discharged to home, which corroborates a worse prognosis for these patients.


  • Open Access

    Survivable Network Design for Group Connectivity in Low-Treewidth Graphs

    by Parinya Chalermsook, Syamantak Das, Guy Even, Bundit Laekhanukit, Daniel Vaz

    In the Group Steiner Tree problem (GST), we are given a (vertex or edge)-weighted graph $G=(V,E)$ on $n$ vertices, a root vertex $r$ and a collection of groups $\{S_i\}_{i\in[h]}: S_i\subseteq V(G)$. The goal is to find a min-cost subgraph $H$ that connects the root to every group. We consider a fault-tolerant variant of GST, which we call Restricted (Rooted) Group SNDP. In this setting, each group $S_i$ has a demand $k_i\in[k],k\in\mathbb N$, and we wish to find a min-cost $H\subseteq G$ such that, for each group $S_i$, there is a vertex in $S_i$ connected to the root via $k_i$ (vertex or edge) disjoint paths. While GST admits $O(\log^2 n\log h)$ approximation, its high connectivity variants are Label-Cover hard, and for the vertex-weighted version, the hardness holds even when $k=2$. Previously, positive results were known only for the edge-weighted version when $k=2$ [Gupta et al., SODA 2010; Khandekar et al., Theor. Comput. Sci., 2012] and for a relaxed variant where the disjoint paths may end at different vertices in a group [Chalermsook et al., SODA 2015]. Our main result is an $O(\log n\log h)$ approximation for Restricted Group SNDP that runs in time $n^{f(k, w)}$, where $w$ is the treewidth of $G$. This nearly matches the lower bound when $k$ and $w$ are constant. The key to achieving this result is a non-trivial extension of the framework in [Chalermsook et al., SODA 2017], which embeds all feasible solutions to the problem into a dynamic program (DP) table. However, finding the optimal solution in the DP table remains intractable. We formulate a linear program relaxation for the DP and obtain an approximate solution via randomized rounding. This framework also allows us to systematically construct DP tables for high-connectivity problems. As a result, we present new exact algorithms for several variants of survivable network design problems in low-treewidth graphs.

  • Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs

    by Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit, Daniel Vaz

    The Group Steiner Tree (GST) problem is a classical problem in combinatorial optimization and theoretical computer science. In the Edge-Weighted Group Steiner Tree (EW-GST) problem, we are given an undirected graph G = (V, E) on n vertices with edge costs c : E → ℝ≥0, a source vertex s and a collection of subsets of vertices, called groups, S1,…, Sk ⊆ V. The goal is to find a minimum-cost tree H ⊆ G that connects s to some vertex from each group Si, for all i = 1, 2,…, k. The Node-Weighted Group Steiner Tree (NW-GST) problem has the same setting, but the costs are associated with nodes. The goal is to find a minimum- cost node set X ⊆ V such that G[X] connects every group to the source. When G is a tree, both EW-GST and NW-GST admit a polynomial-time O (log n log k) approximation algorithm due to the seminal result of [Garg et al., SODA'98 and J. Algorithm]. The matching hardness of log2−∊n is known even for tree instances of EW-GST and NW-GST [Halperin and Krauthgamer STOC'03]. In general graphs, most of polynomial-time approximation algorithms for EW- GST reduce the problem to a tree instance using the metric- tree embedding, incurring a loss of O(log n) on the approximation factor [Bartal, FOCS'96; Fakcharoenphol et al., FOCS'03 and JCSS]. This yields an approximation ratio of O(log n log k) for EW-GST. Using metric-tree embedding, this factor cannot be improved: The loss of O(log n) is necessary on some input graphs (e.g., grids and expanders). There are alternative approaches that avoid metric-tree embedding, e.g., the algorithm of [Chekuri and Pal, FOCS'05], which gives a tight approximation ratio, but none of which achieves polylogarithmic approximation in polynomial-time. This state of the art shows a clear lack of understanding of GST in general graphs beyond the metric-tree embedding technique. For NW-GST (for which the metric-tree embedding does not apply), not even a polynomial-time polyloga- rithmic approximation algorithm is known. In this paper, we present O(log n log k) approximation algorithms that run in time nÕ(tw(G)2 ‘for both NW-GST and EW-GST1, where tw(G) denotes the treewidth of graph G. The key to both results is a different type of “tree- embedding” that produces a tree of much bigger size, but does not cause any loss on the approximation factor. Our embedding is inspired by dynamic programming, a technique which is typically not applicable to Group Steiner problems.