Cover Image

On the Complexity of Target Set Selection in Simple Geometric Networks

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dvořák, Michal, Knop, Dušan, Schierreich, Šimon
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Host Community Respecting Refugee Housing
by: Knop, Dušan, et al.
Published: (2023)

Solving Multiagent Path Finding on Highly Centralized Networks
by: Fioravantes, Foivos, et al.
Published: (2024)

Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures
by: Fioravantes, Foivos, et al.
Published: (2024)

Exact Algorithms for Distance to Unique Vertex Cover
by: Fioravantes, Foivos, et al.
Published: (2025)

Parameterized Critical Node Cut Revisited
by: Knop, Dušan, et al.
Published: (2025)

A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity
by: Dvořák, Pavel, et al.
Published: (2024)

Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
by: Dvořák, Pavel, et al.
Published: (2017)

Balancing the Spread of Two Opinions in Sparse Social Networks
by: Knop, Dušan, et al.
Published: (2021)

Hedonic Diversity Games: A Complexity Picture with More than Two Colors
by: Ganian, Robert, et al.
Published: (2022)

Information-Based Complexity vs Computational Complexity in Phaseless Polynomial Interpolation
by: Przybyłek, Michał R., et al.
Published: (2026)

Exponential Separation Between Powers of Regular and General Resolution Over Parities
by: Bhattacharya, Sreejata Kishor, et al.
Published: (2024)

Generalized minimum 0-extension problem and discrete convexity
by: Dvorak, Martin, et al.
Published: (2021)

Individual Rationality in Topological Distance Games is Surprisingly Hard
by: Deligkas, Argyrios, et al.
Published: (2024)

The Parameterized Complexity of Geometric 1-Planarity
by: Firbas, Alexander
Published: (2026)

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

Optimal Proof Systems for Complex Sets are Hard to Find
by: Egidy, Fabian, et al.
Published: (2024)

Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs
by: Eagling-Vose, Tala, et al.
Published: (2025)

On the Complexity of Discounted Robust MDPs with $L_p$ Uncertainty Sets
by: Asadi, Ali, et al.
Published: (2026)

Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity
by: Knop, Dušan, et al.
Published: (2017)

On the Complexity of Problems on Tree-structured Graphs
by: Bodlaender, Hans L., et al.
Published: (2022)

The Complexity of Verifying Feedforward Neural Networks in Quantised Settings
by: Alsmann, Eric, et al.
Published: (2026)

Practical approach to $2$-Euclidean Preferences
by: Dvořák, Michal, et al.
Published: (2025)

Reachability In Simple Neural Networks
by: Sälzer, Marco, et al.
Published: (2022)

Hexasort -- The Complexity of Stacking Colors on Graphs
by: Klocker, Linus, et al.
Published: (2026)

Pathways to Tractability for Geometric Thickness
by: Depian, Thomas, et al.
Published: (2024)

The Parameterized Complexity of Terminal Monitoring Set
by: Aravind, N. R., et al.
Published: (2024)

A Complexity Dichotomy for Semilinear Target Sets in Automata with One Counter
by: Shakiba, Yousef, et al.
Published: (2025)

Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity
by: Mackenzie, Simon, et al.
Published: (2024)

A Structural Complexity Analysis of Hierarchical Task Network Planning
by: Brand, Cornelius, et al.
Published: (2024)

Additive Models Explained: A Computational Complexity Approach
by: Bassan, Shahaf, et al.
Published: (2025)

Simple Circuit Extensions for XOR in PTIME
by: Carmosino, Marco, et al.
Published: (2025)

Complexity of Manipulation and Bribery in Premise-Based Judgment Aggregation with Simple Formulas
by: Bredereck, Robert, et al.
Published: (2024)

Simple general magnification of circuit lower bounds
by: Atserias, Albert, et al.
Published: (2025)

Set Descriptive Complexity of Solvable Functions
by: Gozzi, Riccardo, et al.
Published: (2024)

NISQ Security and Complexity via Simple Classical Reasoning
by: Cojocaru, Alexandru, et al.
Published: (2025)

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

Hardness of SetCover Reoptimization
by: Jansen, Klaus, et al.
Published: (2025)

Stability in Distance Preservation Games on Graphs
by: Deligkas, Argyrios, et al.
Published: (2026)

Dividing Indivisible Items for the Benefit of All: It is Hard to Be Fair Without Social Awareness
by: Deligkas, Argyris, et al.
Published: (2025)

Balanced and Fair Partitioning of Friends
by: Deligkas, Argyrios, et al.
Published: (2025)