Some classical planning problems become tractable when their variable-dependency structure is simple. Classical planning means finding a sequence of actions that drives a set of state variables from a start assignment to a goal. The structure in question is the causal graph, which has one node per variable and an edge whenever changing one variable depends on another. When this graph is a shallow tree and each variable takes only a few values, a planning task can be rewritten as a tree-shaped constraint satisfaction problem (CSP) and solved in polynomial time. A separate theory, kernelization, asks a related question: can a fast preprocessing step shrink every instance down to a size that depends only polynomially on a structural parameter, and not on the input length? Its main tool for proving "no" is cross-composition. A cross-composition packs the logical OR of many hard instances into one instance whose parameter stays small. If that packing exists, polynomial-size preprocessing is impossible unless a standard complexity assumption fails.
This proposal asks which causal-graph parameters admit such shrinking. Our central observation is that the question splits cleanly in two. Parameters measured as a maximum over the graph, such as depth, domain size, or down-depth, are closed under disjoint union. They therefore fall to short OR-gadgets, and we will state these lower bounds as a first, deliberately modest result. Parameters that add up across the graph behave differently. The main example is the size of an action-deletion backdoor, meaning a small set of actions whose removal splits the causal graph into tiny independent pieces. For these parameters a disjoint union inflates the parameter, so the easy argument fails. The real open question lives there. We propose to settle it, either by proving a cross-composition lower bound that encodes each instance's index in which subset of backdoor actions touches it, or by finding a kernel whose size the lower-bound attempt cannot beat.
Where the gap is and what already exists
Bäckström, Jonsson and Ordyniak showed that cost-optimal planning over polytree causal graphs is solvable in time $O((B\cdot s^{B+1})^6\|\mathbb{P}\|)$. Here a polytree is a directed graph whose undirected version is a tree, $s$ is the maximum domain size, $d$ is the depth, and $B=B(s,d)$ is a tower-of-exponents bound on how often any variable needs to change. The method bounds those value changes and then compiles the task into a tree-structured CSP (A Refined Understanding of Cost-optimal Planning with Polytree Causal Graphs). The same group extended fixed-parameter tractability to arbitrary acyclic graphs of bounded domain size and bounded down-depth, which is the depth of an embedding into a tree whose edges point from root to leaves (Novel Structural Parameters for Acyclic Planning Using Tree Embeddings). These two papers supply the tractable fragments we study, and neither asks whether those fragments can be compressed.
On the preprocessing side, Parameterized Complexity and Kernel Bounds for Hard Planning Problems proved that planning parameterized by plan length has no polynomial kernel, even in fixed-parameter tractable fragments such as actions with no preconditions and two effects. It explicitly points to causal-graph parameters as the next thing to examine. Limits of Preprocessing built the cross-composition toolkit for AI reasoning. It showed that CSP parameterized by treewidth and SAT parameterized by strong-backdoor size have no polynomial kernels, and it motivates our backdoor question by analogy. Backdoors to planning introduced causal-graph backdoors. It showed that evaluation with action-deletion backdoors is fixed-parameter tractable when domains are bounded, which is the only such result for unbounded plan length. Evaluation with variable-deletion backdoors is W[1]-hard, so kernels are moot there. The action-backdoor case is the one fragment where a kernel question is both meaningful and genuinely open, and that paper does not raise it.
Core Claim
Our first claim concerns maximum-type parameters. Polytree planning parameterized by $s+d$, and acyclic planning parameterized by $s+dep^\downarrow$, both lack polynomial kernels unless NP $\subseteq$ coNP/poly.
For polytrees the OR-gadget is a single new binary sink variable $g$, which is the only goal. It has one action per source instance $i$, and that action sets $g$ to true when instance $i$'s own goal holds. The underlying graph remains a tree, the depth grows by one, and domains are unchanged. The source problem is chain planning with domains of size 5, which is NP-hard (Planning over Chain Causal Graphs for Variables with Domains of Size 5 Is NP-Hard). Its parameter is at most polynomial in the size of one instance.
For down-depth the sink gadget fails, because a sink with $t$ parents forces all components onto one root-to-leaf path. We instead use $\lceil\log t\rceil$ one-way selector variables, each with values unset, 0 and 1. Every component gets "skip" actions that satisfy its goal when some selector bit disagrees with that component's index. Exactly one component must therefore genuinely be solved. This raises down-depth by only $O(\log t)$, which is precisely the allowance in the cross-composition parameter bound $k^*\le p(\max_i|x_i|)+c\log t$. A corollary is that the tower size of the compiled CSP cannot be avoided by any polynomial preprocessing guarantee in these parameters.
Our second and main claim concerns an additive parameter. We conjecture that planning parameterized by action-backdoor size $k$, with domain size $s$ and component size $c$ both constant, also has no polynomial kernel. We further conjecture that the obstruction is combinatorial interface diversity. After deleting the backdoor, each small component is characterized by its local type together with the subset of the $k$ backdoor actions that touch it. There can be up to $2^k\cdot f(s,c)$ distinct such characterizations, where $f$ depends only on $s$ and $c$.
Research Program
The work has three linked parts.
First, we prove the maximum-type lower bounds above in full. This includes verifying that the gadgets preserve cost-optimality semantics once each instance's cost bound is normalized within an equivalence class.
Second, we build the reduction side for backdoors. Components touched by no backdoor action have at most $s^c$ states, so each can be solved independently and deleted. Components with identical type and identical touching set are interchangeable in plan-existence terms, because each must be driven by the same backdoor-action history. All but one can therefore be removed, with a stored multiplicity used when costs matter. This gives a kernel of size $2^k\cdot f(s,c)$. We then test whether a sunflower-style argument can shrink it to $\mathrm{poly}(k)$. That argument would show that only polynomially many touching sets can be pairwise "essential".
Third, we attack the matching lower bound by cross-composition. We assign each of $t$ source instances a distinct subset of size $\ell$ drawn from $m=O(\ell+\log t)$ shared backdoor actions, so that $\binom{m}{\ell}\ge t$. Instance $i$'s components are wired only to its subset. The technical obstacle is that shared actions must act in every instance they touch without letting one instance's preconditions block another's plan. Resolving this coupling, or proving it cannot be resolved, is the substance of the project.
If neither direction closes, a third outcome is still informative. Given a guess of the backdoor-action order, the components are independent. That is the shape of a Turing kernel, meaning a polynomial number of small adaptive queries rather than one compressed instance. We would then test whether planning sits on the same side of this divide as the CSP problems analyzed by Szeider.
Baselines
The baselines for the empirical arm all run on the same benchmark files, under the 30-minute limit and 8 GB memory cap used in the cited evaluations, with no extra tuning given to our reduction.
The naive reference point is Fast Downward's standard translation of the task description into multi-valued variables, followed directly by a search planner with no added structural reduction.
The strongest existing competitors are the optimal planners Scorpion and SYMBA. On the 780 structured tasks of Katz, Lee and Sohrabi, 232 tasks were unsolved by any evaluated planner within 30 minutes (Generating SAS+ Planning Tasks of Specified Causal Structure). Our method beats them if planner-plus-reduction solves a non-trivial number of those 232 tasks without losing coverage elsewhere.
A second structural competitor is the custom variable-encoding approach of Fišer et al. It uses an integer program to pick groupings of mutually exclusive facts and so reshape the causal graph. On 1,233 IPC tasks the conflict-based design solved 950 against a baseline of 953 (Custom-Design of FDR Encodings: The Case of Red-Black Planning). Matching 953 while adding structural gains would count as a positive result.
The key ablation separates the two halves of the backdoor reduction. It compares deleting untouched components alone against deleting them plus collapsing duplicate types. This shows whether the interface-diversity idea carries any practical weight. No reported result was found on Lacuna for backdoor-based preprocessing on any benchmark, and none for the evaluation algorithm of Kronegger et al.
Why not just…?
Why not just stop at the easy OR-gadgets, since they already answer the question the literature posed? They answer it only for parameters measured as a maximum. A disjoint union of $t$ instances multiplies backdoor size by $t$, so the gadget proof says nothing about the one fixed-parameter tractable structural fragment with unbounded plan length. We present the gadgets as a lemma precisely so that they do not crowd out the harder question.
Why not just transfer Szeider's CSP-by-treewidth lower bound by a parameter-preserving reduction? The CSP produced by polytree compilation has treewidth 1, so that lower bound does not apply to it. The tension between the two results is resolved by our maximum-type lemma, not by any transfer. Planning parameterized by causal-graph treewidth alone is not known to be fixed-parameter tractable, since acyclicity does not even rescue polynomial space (When Acyclicity Is Not Enough: Limitations of the Causal Graph). A kernel lower bound there would therefore add little.
Why not just rely on heuristic planners and skip kernel theory? This is a fair objection for practice. Our empirical arm tests it directly by asking whether the reduction ever helps Scorpion or SYMBA on the 232 hard structured tasks. If it never does, we will report that the theory guides preprocessing design without changing current coverage. Planner rankings already shift sharply with causal structure: Scorpion ranks first on generated sets but fourth on the Autoscale IPC set (Generating SAS+ Planning Tasks of Specified Causal Structure). That shift suggests structural reductions may matter on exactly the topologies where search struggles.
Why not aim directly for a Turing kernel? It may well be the right answer, and it is a real threat to the many-one lower-bound conjecture. We pursue both directions in parallel. A many-one lower bound together with a Turing kernel would be the most informative possible outcome.
Proposed Experiments
We will measure action-backdoor size, component size and domain size on the 1,233 IPC 1998–2018 tasks, the 780 structured tasks and the 1,204 IPC-mimicking synthetic tasks. Backdoor size will be computed by exact search for small sizes and by an upper-bound heuristic otherwise. We will then apply the reduction and record shrinkage. Finally, we will run Fast Downward-based search, Scorpion and SYMBA on reduced and unreduced versions, using the limits stated above.
The decisive check is to generate, with the IBM FDR generator, the instance families produced by our attempted cross-composition. If the lower bound is right, these instances should resist duplicate-type collapse, with reduced size growing exponentially in $k$. If a polynomial kernel exists, their reduced size should grow only polynomially, which would immediately falsify the subset-encoding route.
References
- A Refined Understanding of Cost-optimal Planning with Polytree Causal Graphs
- Novel Structural Parameters for Acyclic Planning Using Tree Embeddings
- Parameterized Complexity and Kernel Bounds for Hard Planning Problems
- Limits of Preprocessing
- Backdoors to Planning
- Planning over Chain Causal Graphs for Variables with Domains of Size 5 Is NP-Hard
- Generating SAS+ Planning Tasks of Specified Causal Structure
- Custom-Design of FDR Encodings: The Case of Red-Black Planning
- When Acyclicity Is Not Enough: Limitations of the Causal Graph