Cover Image

Algorithms and Hardness for Geodetic Set on Tree-like Digraphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Foucaud, Florent, Ghareghani, Narges, Lorieau, Lucas, Mohammad-Noori, Morteza, Oskuei, Rasa Parvini, Tale, Prafullkumar
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Metric Dimension and Geodetic Set Parameterized by Vertex Cover
by: Foucaud, Florent, et al.
Published: (2024)

Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover
by: Chakraborty, Dipayan, et al.
Published: (2024)

Parameterized complexity of isometric path partition: treewidth and diameter
by: Chakraborty, Dibyayan, et al.
Published: (2025)

A Finer View of the Parameterized Landscape of Labeled Graph Contractions
by: Mathur, Yashaswini, et al.
Published: (2025)

Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
by: Foucaud, Florent, et al.
Published: (2023)

Path Contraction Faster than $2^n$
by: Agrawal, Akanksha, et al.
Published: (2025)

Algorithms and complexity for path covers of temporal DAGs: when is Dilworth dynamic?
by: Chakraborty, Dibyayan, et al.
Published: (2024)

Polynomial-time algorithms for PATH COVER and PATH PARTITION on trees and graphs of bounded treewidth
by: Foucaud, Florent, et al.
Published: (2025)

Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number
by: Tale, Prafullkumar
Published: (2025)

Structural Parameterization of Locating-Dominating Set and Test Cover
by: Chakraborty, Dipayan, et al.
Published: (2024)

Robust Contraction Decomposition for Minor-Free Graphs and its Applications
by: Bandyapadhyay, Sayan, et al.
Published: (2024)

Algorithms and complexity for monitoring edge-geodetic sets in graphs
by: Foucaud, Florent, et al.
Published: (2024)

Feedback Vertex Set for pseudo-disk graphs in subexponential FPT time
by: Berthe, Gaétan, et al.
Published: (2024)

Towards Transitive-free Digraphs
by: Abhinav, Ankit, et al.
Published: (2025)

On graphs coverable by k shortest paths
by: Dumas, Maël, et al.
Published: (2022)

Isometric path complexity of graphs
by: Chakraborty, Dibyayan, et al.
Published: (2022)

Total Domination, Separated Clusters, CD-Coloring: Algorithms and Hardness
by: Antony, Dhanyamol, et al.
Published: (2023)

Greedy Algorithms for Shortcut Sets and Hopsets
by: Bals, Ben, et al.
Published: (2025)

Minimum Sum Set Cover: Structures and Algorithm
by: Zhang, Zhongyi, et al.
Published: (2026)

Stable Approximation Algorithms for Dominating Set and Independent Set
by: de Berg, Mark, et al.
Published: (2024)

Extremal digraphs for open neighbourhood location-domination and identifying codes
by: Foucaud, Florent, et al.
Published: (2023)

Tight Localizations of Feedback Sets
by: Hecht, Michael, et al.
Published: (2020)

Parameterized Complexity of Path Set Packing
by: Aravind, N. R., et al.
Published: (2022)

Refining the Complexity Landscape of Speed Scaling: Hardness and Algorithms
by: Antoniadis, Antonios, et al.
Published: (2025)

Partially Ordered Sets Corresponding to the Partition Problem
by: Kubo, Susumu
Published: (2024)

The Parameterized Complexity Landscape of Two-Sets Cut-Uncut
by: Bentert, Matthias, et al.
Published: (2024)

Max Weight Independent Set in sparse graphs with no long claws
by: Abrishami, Tara, et al.
Published: (2023)

Subexponential and Parameterized Mixing Times of Glauber Dynamics on Independent Sets
by: Marin, Malory
Published: (2025)

Approximation Algorithms for Optimal Hopsets
by: Dinitz, Michael, et al.
Published: (2025)

Algorithmic Aspects of Temporal Betweenness
by: Buß, Sebastian, et al.
Published: (2020)

Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees
by: Efthymiou, Charilaos, et al.
Published: (2023)

Minsum Problem for Discrete and Weighted Set Flow on Dynamic Path Network
by: Manna, Bubai, et al.
Published: (2024)

Discrepancy Minimization via Regularization
by: Pesenti, Lucas, et al.
Published: (2022)

An Approximation Algorithm for Monotone Submodular Cost Allocation
by: Mizutani, Ryuhei
Published: (2025)

Terminal Steiner tree problem : Complexity and Algorithms
by: S, Jyothish, et al.
Published: (2026)

Matching Algorithms in the Sparse Stochastic Block Model
by: Brandenberger, Anna, et al.
Published: (2024)

Hardness of Burning Number Problem on Regular Graphs
by: Antony, Dhanyamol, et al.
Published: (2026)

Revisiting Tree Isomorphism: An Algorithmic Bric-à-Brac
by: Ingels, Florian
Published: (2023)

Improved Streaming Algorithm for Fair $k$-Center Clustering
by: Guo, Longkun, et al.
Published: (2025)

Parameterized Algorithms for Balanced Cluster Edge Modification Problems
by: Madathil, Jayakrishnan, et al.
Published: (2024)