Constrained ear decompositions in graphs and digraphs

NEW

Problem: Literal reconstruction: for every fixed set $\mathcal A\subseteq \mathbb Z$, let $L_{\mathcal A}$ be the language of finite digraphs having a directed handle/ear decomposition in which every handle has length in $\mathcal A$. The conjecture asserts that $L_{\mathcal A}$ is NP-complete unless $\mathcal A=\{1,\dots,h\}$ for some $h\in\mathbb N$. This reconstruction follows the quoted phrase “for every set $\mathcal A$ of integers”; no finiteness or decidability condition on $\mathcal A$ is stated.

Result: The literal conjecture is false.

Let $K\subseteq \{3,4,\dots\}$ be a nonrecursive set, for example a shifted halting set, and set $\mathcal A=K$. Then $\mathcal A$ is not equal to any finite initial interval $\{1,\dots,h\}$.

For $n\ge 3$, let $C_n$ be the directed cycle of length $n$. Under the standard handle-decomposition convention, the first handle is a directed cycle and is constrained by $\mathcal A$. The only directed cycle contained in $C_n$ is $C_n$ itself. Hence

Indeed, if $n\in\mathcal A$, the one-handle decomposition consisting of $C_n$ is valid; conversely, any valid decomposition of $C_n$ must start with the whole cycle $C_n$, whose length is $n$, so $n\in\mathcal A$.

If $L_{\mathcal A}$ were NP-complete, then in particular $L_{\mathcal A}\in\mathrm{NP}$, hence $L_{\mathcal A}$ would be decidable. But then membership in the nonrecursive set $\mathcal A$ would be decidable by mapping $n$ to $C_n$ and deciding whether $C_n\in L_{\mathcal A}$, a contradiction.

Thus the conjecture, as literally stated for arbitrary sets of integers, is false.

The defect is the missing effectiveness/finiteness hypothesis on $\mathcal A$. A natural repair would restrict $\mathcal A$ to finite or at least decidable sets of positive integers; if infinite sets are allowed, one should also treat $\mathbb N_{>0}$ as the infinite initial interval exception.

Citation: No literature counterexample is needed; the proof uses only the standard undecidability of the halting problem.