A graceful labeling of a graph with $m$ edges is a labeling of its vertices with some subset of the integers between $0$ and $m$ inclusive, such that no two vertices share a label, and such that each edge is uniquely identified by the positive, or absolute difference between its endpoints.
The Graceful Tree conjecture (all trees are graceful) is a well known open problem.
Finding a graceful labeling seems not so easy; some time ago I made a few tests with a Constraint Programming language and the solver got stuck even for relatively small highly symmetric trees.
A natural variant of the problem is the following:
Graceful Tree Labeling Completion problem: Given a partially labeled tree $T$, is it possible to assign the remaining labels and obtain a graceful labeling?
I'm wondering if there have been attempts to study its complexity?
The conjecture is false for general graphs, furthermore any graph $G$ can be embedded as an induced subgraph of a graceful graph; so the following generalization to graphs could include enough "gears" to allow an NP-complete reduction.
Graceful Graph Labeling Completion problem: Given a partially labeled graph $G$, is it possible to assign the remaining labels and obtain a graceful labeling?
I searched for both, but didn't find anything.