Daniel Vaz
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Daniel Vaz has a total of 43 co-authors. Here are the top co-authors by number of shared publications:
- Bundit Laekhanukit
Shanghai University of Finance and Economics
2 shared publications - Luís Paquete
University of Coimbra, CISUC
2 shared publications - Ana Barroso
Thoracic Tumors Multidisciplinary Unit, Centro Hospitalar Vila Nova de Gaia/Espinho
1 shared publication Aníbal Ponte
CISUC, Department of Informatics Engineering, University of Coimbra, Portugal and ESTSETíBAL, Polytechnic Institute of Setúbal, Portugal
1 shared publication- Bundit Laekhanukit
Weizmann Institute of Science Israel
1 shared publication - Carlos M. Fonseca
Univ Coimbra, Dept Informat Engn, CISUC, P-3030290 Coimbra, Portugal
1 shared publication
Latest Publications
- Open Access
- 6 November 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
Broadcasting Under Structural Restrictions
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}) \) .- 6 November 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
Open AccessBroadcasting Under Structural Restrictions
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}) \) . - 1 October 2025
- Published by Springer Nature
- p. 172-186
Buy-at-Bulk Facility Location on Trees
- Open Access
- 22 January 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 20 (1) , 1-20
Approximating Sparsest Cut in Low-treewidth Graphs via Combinatorial Diameter
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.- 22 January 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 20 (1) , 1-20
Open AccessApproximating Sparsest Cut in Low-treewidth Graphs via Combinatorial Diameter
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. - 24 January 2022
- Published by Springer Nature in Algorithmica
- Vol. 84 (5) , 1252-1278
On Approximating Degree-Bounded Network Design Problems
- 24 January 2022
- Published by Springer Nature in Algorithmica
- Vol. 84 (5) , 1252-1278
On Approximating Degree-Bounded Network Design Problems
- Open Access
- 30 November 2018
- Published by Taylor & Francis in Pulmonology
- Vol. 24 (6) , 330-336
Undernutrition risk at hospital admission and length of stay among pulmonology inpatients
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.
- 30 November 2018
- Published by Taylor & Francis in Pulmonology
- Vol. 24 (6) , 330-336
Open AccessUndernutrition risk at hospital admission and length of stay among pulmonology inpatients
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.
- 1 September 2018
- Published by Elsevier in Artificial Intelligence
- Vol. 262, 222-247
Dynamics in matching and coalition formation games with structural constraints
- 1 September 2018
- Published by Elsevier in Artificial Intelligence
- Vol. 262, 222-247
Dynamics in matching and coalition formation games with structural constraints
- Open Access
Survivable Network Design for Group Connectivity in Low-Treewidth Graphs
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.Open AccessSurvivable Network Design for Group Connectivity in Low-Treewidth Graphs
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. - 7 January 2017
- Published by Springer Nature
- p. 65-77
New Integrality Gap Results for the Firefighters Problem on Trees
- 7 January 2017
- Published by Springer Nature
- p. 65-77
New Integrality Gap Results for the Firefighters Problem on Trees
- 4 January 2017
- Published by Society for Industrial & Applied Mathematics (SIAM)
Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs
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.
- 4 January 2017
- Published by Society for Industrial & Applied Mathematics (SIAM)
Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs
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.
- 1 November 2016
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 55, 113-116
A Note on Fractional Coloring and the Integrality gap of LP for Maximum Weight Independent Set
- 1 November 2016
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 55, 113-116
A Note on Fractional Coloring and the Integrality gap of LP for Maximum Weight Independent Set