\documentstyle[a4,12pt]{article}
\newcommand{\Ff}{{\bf F}}
\newcommand{\Rr}{{\bf R}}
\newcommand{\eps}{\epsilon}
\newcommand{\lam}{\lambda}
\newcommand{\mod}{{\rm mod ~}}
\newcommand{\rk}{{\rm rk}}
\newcommand{\tr}{{\rm tr}}
\newcommand{\im}{{\rm im\,}}
\newcommand{\adj}{\,\sim\,}
\newcommand{\nadj}{\,\not\sim\,}

\newtheorem{Theorem} {Theorem} [section]
\newtheorem{Proposition} [Theorem] {Proposition}
\newtheorem{Lemma} [Theorem] {Lemma}
\newtheorem{Corollary} [Theorem] {Corollary}
\newcommand{\Proof}{ \noindent{\bf Proof:}\quad }
\newcommand{\Remark}{ \noindent{\bf Remark:}\quad }
\newcommand{\qed  }{\hfill$\Box$\medskip}

\title{Partitioning into induced trees is NP-complete}
\author{A.E. Brouwer}
\date{30 October 1998}
\begin{document}
\maketitle

\medskip

S.M. Madani asked whether the following question is NP-complete:

\medskip
{\bf Question} {\it Given a graph $G$ (possibly with multiple edges),
is there a partition of the vertex set into at most $k$ parts
such that each part induces a tree?}

\medskip
The answer is affirmative for each $k \ge 2$, even when the
question is restricted to graphs without multiple edges.

Indeed, Garey \& Johnson \cite{GJ} list as problem LO3
`not all equal 3-satisfiability', and mention that Schaefer
proved its NP-completeness.

Now the above question (for $k = 2$) can be easily reduced
to LO3 as follows:

Given a set $U$ of variables and a collection $C$ of clauses
over $U$ such that each clause $c \in C$ has size 3,
construct a graph $G$ with $2 |U| + |C| + 3$ vertices as follows:
For each variable $x_i \in U$, construct two vertices, joined by
an edge, and call them $x_i$ and $\bar{x_i}$.
For each clause $c \in C$ construct a vertex,
and call it $c$. Join $c$ to the three literals it contains.
Finally, construct two vertices and call them $A$ and $B$
and join both to all $x_i$ and $\bar{x_i}$; construct
one more vertex called $D$ and join $A$, $B$, $D$ in a triangle.

We claim that $G$ has a partition into two induced trees
if and only if there is a truth assignment for $U$ such that
each clause in $C$ has at least one true literal and at least
one false literal.

Indeed, given such an assignment, let one part consist of
A, all true literals and all clauses with exactly one true
literal. This part induces a tree and so does its complement.

Conversely, given a partition into two induced trees,
$A$ and $B$ must belong to different trees (unless $U$ and $C$
are empty, in which case the claim is true), and each tree
contains precisely one of each pair of literals $x_i$ and $\bar{x_i}$,
so that we find a truth assignment if we call the literals in the
tree containing $A$ true. Now each clause in the tree of $A$
has precisely one true literal, and each clause in the tree of $B$
has precisely one false literal.

\begin{thebibliography}{}

\bibitem{GJ} M.R. Garey \& D.S. Johnson,
{\it Computers and Intractability}, Freeman, 1979.

\end{thebibliography}

\end{document}
