Planar subcubic Independent Set → Planar Multipacking Complexity open
Unsolved
Why this question matters
Multipacking links metric packing constraints to domination-type graph parameters; planar hardness would clarify how geometry affects its complexity.
The target imposes packing constraints at every graph radius. Planar Independent Set hardness alone does not supply a reduction respecting those constraints.
The reduction to construct
The source gives a planar graph of maximum degree three and a bound k. Its outputs are independent vertex sets of size at least k, or NO-SOLUTION.
Given a planar graph G and integer t, find at least t vertices M such that every radius-r ball contains at most r members of M for every vertex and every integer 1≤r≤the number of vertices, or report NO-SOLUTION.
Construct deterministic polynomial-time maps F and G: F sends every legal source instance to a legal target instance, and G(x,y) is a valid source output for every valid output y of F(x). Preserve the stated threshold, domain and promises. The requested complexity conclusion is NP-hardness for the stated target problem.
Local gadgets must satisfy constraints at every radius, not just nearest-neighbor exclusions.
What a complete answer must include
Give explicit construction and recovery algorithms, a general proof for every legal input and every valid target output, and polynomial runtime and encoding-size bounds. Specify finite output encodings and handle NO-SOLUTION outputs when applicable. Tests compare recovered source outputs with independent source solutions.
References
Literature checked 2026-09-16. This summarizes the archived literature search on the date above. Unpublished, unindexed and overlooked work remains outside coverage; no new novelty assessment was performed.