Cover Image

Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chakraborty, Dipayan, Foucaud, Florent, Majumdar, Diptapriyo, Tale, Prafullkumar
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Computational Complexity Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

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

Algorithms and Hardness for Geodetic Set on Tree-like Digraphs
by: Foucaud, Florent, et al.
Published: (2026)

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

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

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

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

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

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

Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration
by: Hirahara, Shuichi, et al.
Published: (2024)

On the Structural Parameterizations of 2-Club with Triangle Constraints
by: Jacob, Ashwin, et al.
Published: (2025)

On the Parameterized Complexity of Grundy Domination and Zero Forcing Problems
by: Scheffler, Robert
Published: (2025)

Polynomial Kernels for Spanning Tree with Diversity Requirements
by: Golovach, Petr A., et al.
Published: (2026)

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

Double Exponential Lower Bound for Telephone Broadcast
by: Tale, Prafullkumar
Published: (2024)

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

On the Polynomial Kernelizations of Finding a Shortest Path with Positive Disjunctive Constraints
by: Bandopadhyay, Susobhan, et al.
Published: (2023)

Lower Bounds for Linear Operators
by: Ko, Young Kun
Published: (2025)

On Approximate Reconfigurability of Label Cover
by: Ohsaka, Naoto
Published: (2023)

Distance Vector Domination
by: Cordasco, Gennaro, et al.
Published: (2024)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
by: Fei, Yumou, et al.
Published: (2025)

Alphabet Reduction for Reconfiguration Problems
by: Ohsaka, Naoto
Published: (2024)

The Days On Days Off Scheduling Problem
by: Nießen, Fabien, et al.
Published: (2024)

Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turzík Bound
by: Lill, Jonas, et al.
Published: (2024)

A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs
by: Hamm, Thekla, et al.
Published: (2026)

Nearly Tight Bounds on Testing of Metric Properties
by: Bao, Yiqiao, et al.
Published: (2024)

Parameterized Complexity of Streaming Diameter and Connectivity Problems
by: Oostveen, Jelle J., et al.
Published: (2022)

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

(Independent) Roman Domination Parameterized by Distance to Cluster
by: Ashok, Pradeesha, et al.
Published: (2024)

Testing Juntas and Junta Subclasses with Relative Error
by: Chen, Xi, et al.
Published: (2025)

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

On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
by: DeHaan, Ian, et al.
Published: (2025)

The Parameterized Complexity of Independent Set and More when Excluding a Half-Graph, Co-Matching, or Matching
by: Dreier, Jan, et al.
Published: (2026)

Parameterized Complexity of (d,r)-Domination via Modular Decomposition
by: Cordasco, Gennaro, 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)

U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited
by: Kratochvíl, Jan, et al.
Published: (2020)

Solving NP-hard Problems on \textsc{GaTEx} Graphs: Linear-Time Algorithms for Perfect Orderings, Cliques, Colorings, and Independent Sets
by: Hellmuth, Marc, et al.
Published: (2023)

Dichotomies for Maximum Matching Cut: $H$-Freeness, Bounded Diameter, Bounded Radius
by: Lucke, Felicia, et al.
Published: (2023)