Cover Image

On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bilò, Davide, Colli, Giordano, Forlizzi, Luca, Leucci, Stefano
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the (In)Approximability of the Monitoring Edge Geodetic Set Problem
by: Bilò, Davide, et al.
Published: (2025)

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

Tight Inapproximability of Target Set Reconfiguration
by: Ohsaka, Naoto
Published: (2024)

Treedepth Inapproximability and Exponential ETH Lower Bound
by: Bonnet, Édouard, et al.
Published: (2025)

From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity
by: Frei, Fabian, et al.
Published: (2025)

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

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
by: S., Karthik C., et al.
Published: (2024)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
by: Guruswami, Venkatesan, et al.
Published: (2023)

Graph Spanners for Group Steiner Distances
by: Bilò, Davide, et al.
Published: (2024)

Inapproximability of Maximum Diameter Clustering for Few Clusters
by: Fleischmann, Henry, et al.
Published: (2023)

Finding a Minimum Spanning Tree with a Small Non-Terminal Set
by: Hanaka, Tesshu, et al.
Published: (2023)

Superconstant Inapproximability of Decision Tree Learning
by: Koch, Caleb, et al.
Published: (2024)

Asymptotically Optimal Inapproximability of Maxmin $k$-Cut Reconfiguration
by: Hirahara, Shuichi, et al.
Published: (2024)

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems
by: Hirahara, Shuichi, et al.
Published: (2023)

Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
by: Hirahara, Shuichi, et al.
Published: (2025)

Temporal queries for dynamic temporal forests
by: Bilò, Davide, et al.
Published: (2024)

Finding Minimum Distance Preservers: A Parameterized Study
by: Simonov, Kirill, et al.
Published: (2026)

Minimum Stable Cut and Treewidth
by: Lampis, Michael
Published: (2021)

Pseudodeterministic Algorithms for Minimum Cut Problems
by: Agarwala, Aryan, et al.
Published: (2025)

Fast Leaf-to-Ancestor Minimum Query in the Oracle Model
by: Upirvitskiy, Aleksey, et al.
Published: (2026)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs
by: Adriaens, Florian, et al.
Published: (2024)

A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow
by: Gholizadeh, Hossein, et al.
Published: (2025)

The Complexity of Finding and Counting Subtournaments
by: Döring, Simon, et al.
Published: (2025)

The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time
by: Stoian, Mihail
Published: (2024)

Knapsack with Vertex Cover, Set Cover, and Hitting Set
by: Dey, Palash, et al.
Published: (2024)

Dominating Set Knapsack: Profit Optimization on Dominating Sets
by: Singh, Sipra
Published: (2025)

Quantum Algorithms on Edge Lists: Hiding, Shuffling, and Cycle Finding
by: Gilani, Amin Shiraz, et al.
Published: (2024)

Testing Properties of Edge Distributions
by: Fei, Yumou
Published: (2026)

Finding Maximum Common Contractions Between Phylogenetic Networks
by: Marchand, Bertrand, et al.
Published: (2024)

Optimal Parallel Basis Finding in Graphic and Related Matroids
by: Khanna, Sanjeev, et al.
Published: (2025)

Matching and Edge Cover in Temporal Graphs
by: Cioni, Lapo, et al.
Published: (2025)

The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
by: Bentert, Matthias, et al.
Published: (2024)

Finding One Local Optimum Is Easy -- but What About Two?
by: Kobayashi, Yasuaki, et al.
Published: (2025)

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
by: Shih, Yu-Sheng, et al.
Published: (2026)

FPT Approximation using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set
by: Chu, Huairui, et al.
Published: (2023)

Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure
by: de Berg, Mark, et al.
Published: (2025)

Rounding Large Independent Sets on Expanders
by: Bafna, Mitali, et al.
Published: (2024)

Hardness and Tractability of T_{h+1}-Free Edge Deletion
by: Gaikwad, Ajinkya, et al.
Published: (2026)

Bounded Independence Edge Sampling for Combinatorial Graph Properties
by: Putterman, Aaron, et al.
Published: (2026)