VLDB 2026 Research / reviewers in the wild / expert
Lucas Keiler
dblp:270/0079
· DBLP profile ↗
2ranked-venue papers
2as first author
2since 2021 · last 2023
0000-0001-6323-0717ORCID · corroborated
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 2 · 2 first-author · 2 since 2021
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2023 | Target set selection with maximum activation time
Lucas Keiler, Carlos V. G. C. Lima, Ana Karolinna Maia, Rudini Menezes Sampaio, Ignasi Sau |
Discret. Appl. Math. | 1 |
| 2021 | Target set selection with maximum activation timeabstractA target set selection model is a graph G with a threshold function τ : V(G) → N upper-bounded by the vertex degree. For a given model, a set S0 ⊆ V(G) is a target set if V(G) can be partitioned into non-empty subsets S0, S1,....,St such that, for all i∈{1,....,t}, Si contains exactly every vertex v having at least τ(v) neighbors in S0∪⋯∪Si−1. We say that t is the activation time tτ(S0) of the target set S0. The problem of, given such a model, finding a target set of minimum size has been extensively studied in the literature. In this article, we investigate its variant, which we call TSS-time, in which the goal is to find a target set S0 that maximizes tτ(S0). That is, given a graph G, a threshold function τ in G, and an integer k, the objective of the TSS-time problem is to decide whether G contains a target set S0 such that tτ(S0)≥k. Let τ*=maxV∈V(G)τ(v). Our main result is the following dichotomy about the complexity of TSS-time when G belongs to a minor-closed graph class C: if C has bounded local treewidth, the problem is FPT parameterized by k and τ*; otherwise, it is NP-complete even for fixed k = 4 and τ* = 2. We also prove that, with τ = 2, the problem is NP-hard in bipartite graphs for fixed k = 5, and from previous results we observe that TSS-time is NP-hard in planar graphs and W[1]-hard parameterized by treewidth. Finally, we present a linear-time algorithm to find a target set S0 in a given tree maximizing tτ(S0). Lucas Keiler, Carlos V. G. C. Lima, Ana Karolinna Maia, Rudini Menezes Sampaio, Ignasi Sau |
LAGOS | 1 |