Cover Image

Why Districting Becomes NP-hard

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Jost, Niklas, Escobedo, Adolfo, Kirchheim, Alice
Format:	Preprint
Published:	2025
Subjects:	Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Hierarchy of Hub Covering Problems
by: Jost, Niklas
Published: (2025)

Broadcast Graph Is NP-complete
by: Xu, Jinghan, et al.
Published: (2024)

Facet-Defining Inequalities for the Angle-Based DC Optimal Transmission Switching Formulation
by: Jabbari-Marand, Behnam, et al.
Published: (2026)

Weighted Treedepth is NP-complete on Graphs of Bounded Degree
by: Dirks, Jona, et al.
Published: (2025)

Crossing Number is NP-hard for Constant Path-width (and Tree-width)
by: Hliněný, Petr, et al.
Published: (2024)

A note on hardness of promise hypergraph colouring
by: Wrochna, Marcin
Published: (2022)

Recognizing Leaf Powers and Pairwise Compatibility Graphs is NP-Complete
by: la Tour, Max Dupré, et al.
Published: (2025)

Graceful coloring is computationally hard
by: Antony, Cyriac, et al.
Published: (2024)

Fixed-parameter tractability and hardness for Steiner rooted and locally connected orientations
by: Bérczi, Kristóf, et al.
Published: (2025)

Algorithms and hardness for Metric Dimension on digraphs
by: Dailly, Antoine, et al.
Published: (2023)

Determining the Outerthickness of Graphs Is NP-Hard
by: Lee, Pin-Hsian, et al.
Published: (2026)

On expectations and variances in the hard-core model on bounded degree graphs
by: Davies, Ewan, et al.
Published: (2025)

Bakry-Émery-Ricci curvature: An alternative network geometry measure in the expanding toolbox of graph Ricci curvatures
by: Mondal, Madhumita, et al.
Published: (2024)

Chemically inspired Erdős-Rényi oriented hypergraphs
by: Garcia-Chung, Angel, et al.
Published: (2023)

Recognizing Sumsets is NP-Complete
by: Abboud, Amir, et al.
Published: (2024)

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)

Reducibility among NP-Hard graph problems and boundary classes
by: Hassan, Syed Mujtaba, et al.
Published: (2024)

On 3-Connected Cubic Planar Graphs and their Strong Embeddings on Orientable Surfaces
by: Weiß, Meike, et al.
Published: (2025)

On 3-Connected Planar Graphs with Unique Orientable Circuit Double Covers
by: Weiß, Meike, et al.
Published: (2026)

On the hardness of recognizing graphs of small mim-width and its variants
by: la Tour, Max Dupré, et al.
Published: (2025)

Slant/Gokigen Naname is NP-complete, and Some Variations are in P
by: Lynch, Jayson, et al.
Published: (2025)

Benders decomposition for congested partial set covering location with uncertain demand
by: Calamita, Alice, et al.
Published: (2024)

Recoverable systems and the maximal hard-core model on the triangular lattice
by: Wang, Geyang, et al.
Published: (2026)

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
by: Johnson, Matthew, et al.
Published: (2022)

Loop corrections for hard spheres in Hamming space
by: Ramezanpour, Abolfazl, et al.
Published: (2024)

The maximal hard-core model as a recoverable system: Gibbs measures and phase coexistence
by: Wang, Geyang, 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)

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

Boxicity of Zero Divisor Graphs
by: Chandran, L. Sunil, et al.
Published: (2025)

Pairwise similarity method for majority domination problem
by: Shushko, N. I., et al.
Published: (2025)

Stereotype graph: A mathematical framework of category stereotypes via graph theory
by: Yan, Yijia
Published: (2025)

Efficient Algorithms for Minimizing the Kirchhoff Index via Adding Edges
by: Zhou, Xiaotian, et al.
Published: (2025)

Temporal Orienteering with Changing Fuel Costs
by: Corsini, Timothée, et al.
Published: (2025)

Spectral Moment of Order Four and the Uniqueness of the CCZ class of Dublin APN Permutation
by: Gillot, Valérie, et al.
Published: (2025)

CAZAC sequence generation of any length with iterative projection onto unit circle: principle and first results
by: Amis, Karine, et al.
Published: (2025)

Optimal Average Disk-Inspection via Fermat's Principle
by: Georgiou, Konstantinos
Published: (2025)

Word-representability and comparability: Minimal forbidden induced subgraphs and cover number bounds
by: Kenkireth, Benny George, et al.
Published: (2025)

Near-optimal edge partitioning via intersecting families
by: Yakunin, Alexander, et al.
Published: (2025)

The Power of Amortization on Minimizing Total Completion Time with Explorable Uncertainty
by: Krekelberg, Bob, et al.
Published: (2025)

The LLLR generalised Langton's ant
by: Lutfalla, Victor
Published: (2025)