Start with a free group on $n$ generators, $F=\langle a_1,\ldots, a_n\rangle$. If I write a word, $w$, in these generators, is there an efficient algorithm to determine whether or not $w$ can be extended to a free basis of $F$?
I have some comments and partial results, but no efficient algorithm.
If any letter appears only once (and raised to the first power), then we can extend the word to a basis (just take the rest of the basis as the other generators). This is not necessary as $c^2bcabab$ can be extended to a basis of $F_3$.
If the word is part of a basis, then the projection to the abelianization must be a primitive vector. Another way to say this is that if the vector in $\mathbb{Z}^n$ with the $i$-th entry equal to the sum of the exponents of $a_i$ in $w$ must not be a $\mathbb{Z}$-multiple of another vector in $\mathbb{Z}^n$. This is not sufficient because $a^2b^2a$ is not part of a basis of $F_2$.
Edit: Given a group $H=\langle w_1,w_2,\ldots,w_k\rangle\leq F_n$, there is an algorithm, due to Stallings, to determine a free basis for $H$. A (terribly inefficient) algorithm is to list all possible bases formed out of reduced words of length less than $w$, and running Stallings' algorithm on each one. I'm asking for an algorithm that can be reasonably implemented.
If $F$ is a free group and $a$ and $b$ are two elements of $F$, it is decidable whether there is an automorphism of $F$ which maps $a$ to $b$. See Combinatorial Group Theory by Roger C. Lyndon, Paul E. Schupp, Proposition I.4.19.
This implies, in particular, that it is decidable whether an element of $F$ is part of a basis.