We consider the deduction problem in the fragment of first-order logic (FOL) composed of existentially closed conjunctions of literals (without functions), denoted FOL$\{\exists,\wedge,\neg_a\}$. This problem can be recast as several fundamental problems in artificial intelligence and databases, namely query containment for conjunctive queries with negation, clause entailment for clauses without functions and query answering with incomplete information for boolean conjunctive queries with negation over a fact base. Deduction in FOL$\{\exists,\wedge,\neg_a\}$ is $\Pi_2^P$-complete, whereas it is only NP-complete when the formulas contain no negation. We investigate the role of specific literals in this complexity increase. These literals have the property of being ``exchangeable'', with this notion taking the structure of the formulas into account. To focus on the structure of formulas, we see them as labeled graphs. Graph homomorphism, which provides a sound and complete proof procedure for positive formulas, is at the core of this study. Let Deduction$_k$ be the following family of problems: given two formulas $g$ and $h$ in FOL$\{\exists,\wedge,\neg_a\}$, such that $g$ has at most $k$ pairs of exchangeable literals, can $g$ be deduced from $h$? The main results are that Deduction$_k$ is NP-complete if $k \leq 1$, and in $P^{NP}$ for any value of $k$; moreover, it is both NP-difficult and co-NP-difficult for $k \geq 3$. As a corollary of our proofs, we are able to classify exactly previous problems when $g$ is decomposable into a tree. Finally, several complementary results and extensions are provided.