\documentclass[12pt]{article}
%proof
\usepackage{latexsym} %for Box symbol
\def\QED{$\Box$}
\newenvironment{proof}
{\begin{trivlist}\item[\hskip\labelsep{\textbf{Proof\,}}]}
{\leavevmode\unskip\nobreak\quad\hspace*{\fill}\QED\end{trivlist}}
%\emergencystretch=2em
%\usepackage{times}
\usepackage{eepic,epic}
\usepackage{latexsym}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
% \usepackage{comment}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{trick}[theorem]{Trick Result}
%Declare hyphenations
\hyphenation{theory theoretical area areas theorem theorems par-allel par-allelize par-allelized threshold Hemaspaan-dra}
\newcommand{\sharpp}{{\rm \#P}}
\newcommand{\sharpsat}{{\rm \#SAT}}
\newcommand{\sat}{\mbox{\rm SAT}}
\newcommand{\qbf}{\mbox{\rm QBF}}
\newcommand{\parityp}{{\rm \oplus P}}
\newcommand{\up}{\mbox{\rm UP}}
\newcommand{\us}{\mbox{\rm US}}
\newcommand{\fewnp}{\mbox{\rm FewNP}}
\newcommand{\fewp}{\mbox{\rm FewP}}
\newcommand{\coup}{\mbox{\rm coUP}}
\newcommand{\e}{\mbox{\rm E}}
\renewcommand{\exp}{{\rm EXP}}
\newcommand{\NE}{\mbox{\rm NE}}
\renewcommand{\ne}{\mbox{\rm NE}}
\newcommand{\nexp}{\mbox{\rm NEXP}}
\newcommand{\p}{\mbox{\rm P}}
\newcommand{\littlep}{{\rm p}}
\newcommand{\NP}{\mbox{\rm NP}}
\newcommand{\DP}{\mbox{\rm DP}}
\newcommand{\np}{\mbox{\rm NP}}
\newcommand{\nt}{\mbox{\rm NT}}
\newcommand{\nnt}{\mbox{\rm NNT}}
\newcommand{\parityoptp}{{\rm \oplus{}OptP}}
\newcommand{\optp}{{\rm OptP}}
\newcommand{\diffp}{{\rm D^P}}
\newcommand{\pp}{\mbox{\rm PP}}
\newcommand{\bpp}{\mbox{\rm BPP}}
\newcommand{\zpp}{\mbox{\rm ZPP}}
\newcommand{\cor}{\mbox{\rm coR}}
\newcommand{\npc}{$\np$-com\-plete}
\newcommand{\conp}{\mbox{\rm coNP}}
\newcommand{\pspace}{\mbox{\rm PSPACE}}
\newcommand{\eespace}{{\rm EESPACE}}
\newcommand{\dspace}{{\rm DSPACE}}
\newcommand{\psp}{{\pspace}}
\newcommand{\pnexp}{{\p^\nexp}}
\newcommand{\npnexp}{{\np^\nexp}}
\newcommand{\nenp}{{\ne^\np}}
\newcommand{\enp}{{\e^\np}}
\newcommand{\pnp}{{\p^{\rm NP}}}
\newcommand{\npnp}{{\np^{\rm NP}}}
\newcommand{\pnplog}{{\p^{\np[\log ]}}}
\newcommand{\nexpnp}{{\nexp^\np}}
\newcommand{\coNP}{{\rm coNP}}
\newcommand{\cone}{{\rm CONE}}
\newcommand{\sigmatwozero}{{\Sigma_2^0}}
\newcommand{\pitwozero}{{\Pi_2^0}}
\newcommand{\pithreezero}{{\Pi_3^0}}
\newcommand{\sigmathreezero}{{\Sigma_3^0}}
\newcommand{\sigmatwo}{{\Sigma_2^p}}
\newcommand{\sigmak}{{\Sigma_k^p}}
\newcommand{\pitwo}{{\Pi_2^p}}
\newcommand{\thetatwo}{{\Theta_2^p}}
\newcommand{\deltatwo}{{\Delta_2^p}}
\newcommand{\poly}{{\rm poly}}
\newcommand{\ph}{{\rm PH}}
\newcommand{\few}{{\rm Few}}
\newcommand{\fewch}{{\rm FewCH}}
\newcommand{\eh}{{\rm EH}}
\newcommand{\blob}{\mbox{\rule[-1.5pt]{5pt}{10.5pt}}}
\newcommand{\lindent}{\qquad}
\newcommand{\magicnum}{{ n^{\frac{1-\epsilon}{\epsilon}+\delta}}}
\newcommand{\fsup}{{\,f_{super}\,}}
\newcommand{\fred}{{\,f_{reduced}\,}}
\newcommand{\pne}{{\p^\ne}}
\newcommand{\npne}{{\np^\ne}}
\newcommand{\nnexarg}{{\nxx^\nexx (x) }}
\newcommand{\nnexx}{{\nxx^\nexx }}
\newcommand{\nnex}{{\nxx^\nexx }}
\newcommand{\expnp}{{\exp^\np }}
\newcommand{\nxx}{{\rm N_{17}}}
\newcommand{\nexx}{{\rm NE_{21}}}
\newcommand{\seh}{{\rm SEH}}
\newcommand{\sexph}{{\rm SEXPH}}
\newcommand{\pstar}{{\p_\star}}
\newcommand{\nestar}{{\ne_{\,\star}}}
%%% Replace these with the AMS stuff below
\newcommand{\supersetproper}{ \stackrel{\scriptscriptstyle\superset}{\scriptscriptstyle\not-}}
\newcommand{\subsetproper}{ \stackrel{\scriptscriptstyle\subset}{\scriptscriptstyle\not-}}
%%% actually, the AMS stuff works, but is not too portable, so let us
%%% stick for now with the above hack!
%%%\input amssym.def
%%%\newsymbol\subsetneq 2328
%%%\newsymbol\supsetneq 2329
%%%\def\subsetproper{\subsetneq}
%%%\def\supersetproper{\supsetneq}
\newcommand{\superset}{\supset}
\newcommand{\superseteq}{\supseteq}
\def\unionfromc{\,\textstyle\bigcup_{\scriptstyle c}\,}
\def\unionfromk{\,\textstyle\bigcup_{\scriptstyle k}\,}
% Dijkstra--style box: as tall as an ``f'' and 5pt wide.
% \fboxsep is set to 0 so that \framebox doesn't leave extra space.
\newcommand{\newlozenge}{\setlength{\fboxsep}{0pt}\setlength{\fboxrule}{.7pt}\framebox[6pt]{\rule{0pt}{9pt}}}
%macros for 1-way-vs-iso-robust-stoc-draft
%\newcommand{\pairs}[1]{\mbox{$\langle\!\!~#1~\!\!\rangle$}}
%\newcommand{\pair}[1]{\mbox{$\langle\!\!~#1~\!\!\rangle$}}
%\def\pair#1{{\mbox{$\langle\!\!~#1~\!\!\rangle$}}}
\def\pair#1{{{\langle\!\!~#1~\!\!\rangle}}}
\def\pairs#1{{{\langle\!\!~#1~\!\!\rangle}}}
\newcommand{\piso}{\mbox{$\littlep$-iso\-mor\-phic}}
\newcommand{\manyonea}{\mbox{$\,\leq_{\rm m}^{{\littlep},\,A}\,$}}
\newcommand{\manyone}{\mbox{$\,\leq_{\rm m}^{{\littlep}}$\,}}
\newcommand{\paiso}{\mbox{$\littlep^A$-iso\-mor\-phic}}
\newcommand{\pisoa}{\paiso}
\newcommand{\pisoam}{\mbox{$\littlep^A$-iso\-mor\-phism}}
\newcommand{\pisom}{\mbox{$\littlep$-iso\-mor\-phism}}
\newcommand{\pselective}{\mbox{$\p$-selec\-tive}}
\newcommand{\sigmastar}{\mbox{$\Sigma^\ast$}}
\newcommand{\pisnp}{\mbox{$\p=\np$}}
\newcommand{\usuba}{\mbox{$U_A$}}
\newcommand{\univsuba}{\mbox{$Univ_A$}}
\newcommand{\pisnotnp}{\mbox{$\p\neq\np$}}
\newcommand{\lb}{\mbox{\{}}
\newcommand{\rb}{\mbox{\}}}
\newcommand{\pa}{\mbox{$\p^A$}}
\newcommand{\calf}{\mbox{$\cal F$}}
\newcommand{\calc}{\mbox{$\cal C$}}
\newcommand{\dr}{{\tt DodgsonRanking}}
\newcommand{\dw}{{\tt DodgsonWinner}}
\newcommand{\kw}{{\tt KemenyWinner}}
\newcommand{\score}{{\mbox{\it{}Score}}}
\newcommand{\dsum}{{\mbox{\it{}DodgsonSum}}}
\newcommand{\ds}{{\tt DodgsonScore}}
\newcommand{\xthreec}{{\tt ExactCoverByThreeSets}}
\newcommand{\satisfiability}{{\tt Satisfiability}}
\newcommand{\clique}{{\tt Clique}}
\newcommand{\threedm}{{\tt ThreeDimensionalMatching}}
\newcommand{\merge}{\mbox{\it{}Merge}}
\newcommand{\mergeprime}{\mbox{{\it{}Merge}$'$}}
\newcommand{\ncertifiesdefeat}{{\tt CertifiesTieOrDefeat}}
\newcommand{\specialdpproblem}{{\tt SpecialProblem}}
\newcommand{\kcolor}{{{\tt \mbox{K-}Color\-a\-bil\-i\-ty}}}
\newcommand{\threecolor}{{{\tt 3\mbox{-}Color\-a\-bil\-i\-ty}}}
\newcommand{\algthreecolor}{{{\tt A\mbox{-}3\mbox{-}Color\-a\-bil\-i\-ty}}}
\newcommand{\ddseqthreecolor}{{{\tt
DD\mbox{-}SEQ\mbox{-}3\mbox{-}Color\-a\-bil\-i\-ty}}}
\newcommand{\slseqthreecolor}{{{\tt
SL\mbox{-}SEQ\mbox{-}3\mbox{-}Color\-a\-bil\-i\-ty}}}
\newcommand{\ddseqint}{{{\tt DD\mbox{-}SEQINT}}}
\newcommand{\slseqint}{{{\tt SL\mbox{-}SEQINT}}}
\newcommand{\threesat}{{{\tt 3\mbox{-}SAT}}}
\newcommand{\voter}{\pair}
\newcommand{\npa}{\mbox{$\np^A$}}
\newcommand{\conpa}{\mbox{$\conp^A$}}
\newcommand{\upa}{\mbox{$\up^A$}}
\newcommand{\sparses}{\mbox{ sparse $S\,$}}
\newcommand{\bigo}{\mbox{$\cal O$}}
\newcommand{\condition}{\,\nottoobig{|}\:}
\def\land{{\; \wedge \;}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%% END: GLOBMAC.TEX
%%%%%%%%%%%%%%%%%%%%%%%%%%%%% START: LOCMAC.TEX
\newcommand{\scriptnp}{\mbox{\protect\scriptsize\rm NP}}
\newcommand{\parallelnp}{\mbox{$\p_{||}^{\scriptnp}$}}
\newcommand{\mis}{\mbox{\it mis}}
\newcommand{\mdg}{\mbox{\it mdg}}
\newcommand{\misequals}{\mbox{\tt MIS$_{\mbox{\footnotesize\tt equal}}$}}
\newcommand{\sone}{\mbox{${\cal S}_1$}}
\newcommand{\ar}{\mbox{${\cal A}_r$}}
\newcommand{\sr}{\mbox{${\cal S}_r$}}
\newcommand{\truthtable}{\mbox{$\,\leq_{\rm tt}^{{\littlep}}$\,}}
\newcommand{\turing}{\mbox{$\,\leq_{\rm T}^{{\littlep}}$\,}}
\newcommand\seq{\subseteq}
\renewcommand\.{\cdot}
\newcommand\<{\langle}
\renewcommand\>{\rangle}
\newcommand\la{\ \leftarrow \ }
\newcommand\ra{\ \rightarrow \ }
\newcommand\lra{\ \leftrightarrow \ }
\newcommand\La{\ \Leftarrow \ }
\newcommand\Ra{\ \Rightarrow \ }
\newcommand\Lra{\ \Leftrightarrow \ }
\newcommand\lola{\ \longleftarrow \ }
\newcommand\lora{\ \longrightarrow \ }
\newcommand\lolra{\ \longleftrightarrow \ }
\newcommand\Lola{\ \Longleftarrow \ }
\newcommand\Lora{\, \Longrightarrow \ }
\newcommand\Lolra{\ \Longleftrightarrow \ }
\newcommand\Lolradef{\ :\Longleftrightarrow \ }
\newcommand{\equalsdef}{\stackrel{\mbox{\protect\scriptsize df}}{=}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%
%%%%%%%%%% Jim's construction macros.
%%%%%%%%%%
%%% The follow are macros for displaying block structured programs and
%%% constructions. Basically, they are dressed up lists, like the
%%% enumerate and itemize environments. Use the construction environment
%%% for the outermost ``list'' of instruction and for ``sublists'' of
%%% instructions use the block environment. E.g.,
%%%
%%% \begin{construction}
%%% \item {\bf Program for} $M_{p,a}$.
%%% \begin{block}
%%% \item Input $x$.
%%% \item Instructions. Instructions. Instructions. Instructions.
%%% Instructions. Instructions. Instructions. Instructions.
%%% \begin{block}
%%% \item More instructions. More instructions. More
%%% instructions. More instructions.
%%% \item More instructions. More instructions. More
%%% instructions. More instructions.
%%% \end{block}
%%% \item Instructions. Instructions. Instructions. Instructions.
%%% \item Instructions. Instructions. Instructions. Instructions.
%%% \end{block}
%%% \item {\bf End program for} $M_{p,a}$.
%%% \end{construction}
\newenvironment{construction}{\bigbreak\begin{block}}{\end{block}
\bigbreak}
\newenvironment{block}{\begin{list}{\hbox{}}{\leftmargin 1em
\itemindent -1em \topsep 0pt \itemsep 0pt \partopsep 0pt}}{\end{list}}
%%% If you want to label the statements/blocks in your construction, use
%%% the lblock environment instead of the block environment and for each
%%% item macro, use \item[YOUR_LABEL]. Note that labels are
%%% do-it-yoursel.
%%%
%%% Note that in the following, the basic indentation of an lblock at
%%% level i of nesting (i>0) is (\dimen15 + i * \dimen16). The default
%%% value of both \dimen15 and \dimen16 is 0.75em.
\dimen15=0.75em
\dimen16=0.75em
\newcommand{\lblocklabel}[1]{\rlap{#1}\hss}
\newenvironment{lblock}{\begin{list}{}{\advance\dimen15 by \dimen16
\leftmargin \dimen15
\itemindent -1em
\topsep 0pt
\labelwidth 0pt
\labelsep \leftmargin
\itemsep 0pt
\let\makelabel\lblocklabel
\partopsep 0pt}}{\end{list}}
%%% The lconstruction is an alternative to the construction environment
%%% which lets you temporarily change the values of \dimen15 and \dimen16.
\newenvironment{lconstruction}[2]{\dimen15=#1 \dimen16=#2
\bigbreak\begin{block}}{\end{block}\bigbreak}
\newcommand{\Comment}[1]{{\sl (\ #1\ )}}
%%%%%%%%%%
%%%%%%%%%% End of Jim's construction macros.
%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%% END: LOCMAC.TEX
%%%%%%%%%%%%%%%%%%%%%%%%%%%%% START: TITLE.TEX
\title{Heuristics versus Completeness for Graph Coloring}
\author{
J\"{o}rg Rothe \\
%Institut f\"ur Informatik \\
%Friedrich-Schiller-Universit\"at Jena \\
%07740 Jena, Germany \\
rothe@informatik.uni-jena.de
}
\date{29 February 2000}
\begin{document}
%%
%%
%% CJTCS frontmatter, Insert after \begin{document}
%%
\def\registered{\({}^{\ooalign%
{\hfil\raise.07ex\hbox{{\tiny\textup{R}}}%
\hfil\crcr\scriptsize\mathhexbox20D\cr}}\)}
\begin{titlepage}
\pagenumbering{roman}
\null\vfil\vskip 60pt
\begin{center}
{\Huge\bf Chicago\nolinebreak[1] Journal of Theoretical Computer\nolinebreak[1] Science\par}
\vskip 3em
{\huge\it The MIT Press\par}
\end{center}
\par\vskip 1.5em
{\Large
\begin{center}
Volume 2000, Article 1\\
\textit{Heuristics versus Completeness for Graph Coloring}
\end{center}
}
\par\noindent
ISSN 1073--0486. MIT Press Journals, Five Cambridge Center, Cambridge, MA
02142-1493 USA; (617)253-2889;
\emph{journals-orders@mit.edu, journals-info{\allowbreak}@mit.edu}.
Published one article at a time in \LaTeX\ source form on the
Internet. Pagination varies from copy to copy. For more
information and other articles see
\begin{itemize}
\item \emph{http://mitpress.mit.edu/CJTCS/}
\item \emph{http://www.cs.uchicago.edu/publications/cjtcs/}
\item \emph{ftp://mitpress.mit.edu/pub/CJTCS}
\item \emph{ftp://cs.uchicago.edu/pub/publications/cjtcs}
\end{itemize}
\par\noindent
The \emph{Chicago Journal of Theoretical Computer Science} is
abstracted or indexed in \emph{
Research Alert\registered,
SciSearch\registered,
Current Contents\registered/Engineering
Computing \& Technology}, and \emph{CompuMath Citation Index\registered.}
\par\noindent\copyright 1999 The Massachusetts Institute of Technology.
Subscribers are licensed to use journal articles in a variety of
ways, limited only as required to ensure fair attribution to authors
and the journal, and to prohibit use in a competing commercial
product. See the journal's World Wide Web site for further
details. Address inquiries to the Subsidiary Rights Manager, MIT
Press Journals; (617)253-2864;
\emph{journals-rights@mit.edu}.\pagebreak[2]
\par\noindent The \emph{Chicago Journal of Theoretical Computer Science}
is a peer-reviewed scholarly journal in theoretical computer
science. The journal is committed to providing a forum for
significant results on theoretical aspects of all topics in computer
science.
\par
\begin{trivlist}
\item[\emph{Editor-in-Chief:}] Janos Simon
\item[\emph{Consulting Editors:}]
Joseph Halpern, Eric Allender, Raimund Seidel
\item[\emph{Editors:}]
\begin{tabular}[t]{lll}
Martin Abadi & Greg Frederickson & John Mitchell \\
Pankaj Agarwal & Andrew Goldberg & Ketan Mulmuley \\
Eric Allender & Georg Gottlob & Gil Neiger \\
Tetsuo Asano & Vassos Hadzilacos & David Peleg \\
Laszl\'o Babai & Juris Hartmanis & Andrew Pitts \\
Eric Bach & Maurice Herlihy & James Royer \\
Stephen Brookes & Ted Herman & Alan Selman \\
Jin-Yi Cai & Stephen Homer & Nir Shavit \\
Anne Condon & Neil Immerman & Eva Tardos \\
Cynthia Dwork & Howard Karloff & Sam Toueg \\
David Eppstein & Philip Klein & Moshe Vardi \\
Ronald Fagin & Phokion Kolaitis & Jennifer Welch \\
Lance Fortnow & Stephen Mahaney & Pierre Wolper \\
Steven Fortune & Michael Merritt
\end{tabular}
\vspace{1ex}
\item[\emph{Managing Editor:}] Michael J.\ O'Donnell
\vspace{1ex}
\item[\emph{Electronic Mail:}] \emph{chicago-journal@cs.uchicago.edu}
\end{trivlist}
\vfil\null
\end{titlepage}
\maketitle
\pagenumbering{arabic}
%%
%% End frontmatter code
%%
%%
\maketitle
%}
%\vspace{-0.1in}
%abstract spacing
%\niceonespacing
\begin{abstract}
We study the complexity of the problem $\threecolor$
when restricted to those input graphs on which a given graph coloring
heuristic is able to solve the problem. The heuristics we consider
include the sequential algorithm traversing the vertices of the graph
in various orderings (e.g., by decreasing degree or in the recursive
smallest-last order) as well as Wood's algorithm. For each heuristic
considered here, we prove that the corresponding restriction of
$\threecolor$ remains NP-complete.
\end{abstract}
\section{Introduction}
Graph coloring problems are of great importance in both theory and
applications and have been intensely studied during the past century.
Applications of constructing a graph coloring with as few colors as
possible arise, for instance, in scheduling and partitioning problems
(see Garey and Johnson~\cite{gar-joh:b:int}).
Unfortunately, the (optimization) problem
of finding the chromatic number of a given graph is very complex, and
even the (decision) problem of determining whether or not a given
graph is 3-colorable (i.e., the vertices of the graph can be colored
with three colors such that no two adjacent vertices have the same
color) is one of the standard NP-complete problems
(\cite{sto:j:planar-3color}; see
also~\cite{gar-joh-sto:j:simplified-np-completeness,gar-joh:b:int}),
thus being not efficiently solvable by current methods. However, due
to the great amount of practical interest in finding efficient
solutions---or at least good efficient approximate solutions---for
these problems, it is not surprising that a large body of graph
coloring heuristics have been proposed to date.
Such heuristic algorithms have been analyzed in depth both from a practical
and a theoretical point of view; see, for example, the
paper~\cite{mat-mar-isa:b:graph-coloring}, which compares certain
heuristics by empirical tests on random graphs, and the work of
Johnson~\cite{joh:c:graph-coloring}, which proves a number of prominent
heuristics to have quite poor worst-case behavior in terms of their
approximation ratio for the chromatic number. In fact, Feige and
Kilian~\cite{fei-kil:c:chromatic-number} recently proved that no
deterministic polynomial-time algorithm can approximate the chromatic
number within a factor of ${\cal O}(n^{1 - \epsilon})$ for any fixed
constant $\epsilon > 0$, unless $\np = \zpp$.
Johnson's results~\cite{joh:c:graph-coloring} are to be taken as a
warning that the success or failure of a specific graph coloring
heuristic strongly depends on the form of the given input graph. In
this paper, we study the complexity of the problem $\threecolor$ when
restricted to those input graphs for which a given heuristic is able
to solve it.\footnote{Usually, NP-complete
graph problems are restricted with respect to certain ``structural''
graph properties such as planarity, bounded maximum degree,
bipartiteness, and so on. For instance, it is known that the problem
$\threecolor$ is in P when restricted to
% interval graphs~\cite{gol:b:perfect-graphs}
perfect graphs~\cite{gro-lov-sch:b:perfect-graphs},
but remains NP-complete when
restricted to planar graphs~\cite{sto:j:planar-3color}. In contrast,
we restrict the problem with respect to the usefulness of a given
heuristic.
}
For any fixed
heuristic algorithm ${\tt A}$ for graph coloring, define the
restriction of $\threecolor$ that is induced by~${\tt A}$:
Given a graph~$G$,
can ${\tt A}$ on input $G$ find a proper 3-coloring of~$G$?
We denote this problem by $\algthreecolor$.
This approach is not quite new. Bodlaender, Thilikos, and
Yamazaki \cite{bod-thi-yam:j:greedy-for-maximum-independent-sets}
showed that the problem ${\tt Independent\mbox{ }Set}$
% (the problem of whether, given a graph $G$ and a constant~$k$,
% $G$ has an independent set of size at least~$k$)
remains NP-complete when restricted to those input graphs on which a
simple heuristic for finding independent sets (the so-called
minimum-degree greedy algorithm, MDG for short) performs well. They also
proved that the complexity of recognizing those input graphs for which
MDG approximates the independence number
(i.e., the size of a maximum independent set) within a
certain fixed factor of optimality resides between the complexity
classes coNP and~$\p^{\mbox{\protect\scriptsize $\np$}}$.
Solving the questions left open by Bodlaender, Thilikos, and
Yamazaki \cite{bod-thi-yam:j:greedy-for-maximum-independent-sets},
Hemaspaandra and
Rothe~\cite{hem-rot:j:max-independent-set-by-greed} determined the
exact complexity of this recognition problem by proving it complete
for the class $\parallelnp$
of problems solvable
in polynomial time via parallel access to~$\np$.
In this note, we investigate the above problem $\algthreecolor$ for a
number of graph coloring heuristics ${\tt A}$, all of which are based
on the sequential (or greedy) algorithm applied to a certain vertex
ordering, such as the order by decreasing degree or the recursive
smallest-last order of Matula, Marble, and Isaacson
\cite{mat-mar-isa:b:graph-coloring}. Other heuristics that we
consider, for
instance, Wood's algorithm~\cite{woo:j:graph-coloring},
combine the sequential method with certain other strategies.
We prove that the problem $\algthreecolor$ remains NP-complete for
each heuristic ${\tt A}$ considered in this paper.
\section{Preliminaries}
All graphs considered in this paper are undirected graphs without
reflexive edges. For any graph~$G$, let $V(G)$ denote the set of
vertices of $G$ and let $E(G)$ denote the set of edges of~$G$. For
any set~$A$, let $||A||$ denote the cardinality of~$A$. For any vertex
$v \in V(G)$, the {\em neighborhood\/} of $v$ (denoted~$N(v)$) is the
set of vertices in $G$ that are adjacent to~$v$. For any vertex $v \in
V(G)$, the {\em degree\/} of $v$ is defined by~$\mbox{\it deg}(v)
\equalsdef ||N(v)||$.
% For any subset $W \subseteq V(G)$, let $G[W]$
% denote the subgraph of $G$ induced by $W$.
Given two disjoint graphs
$G$ and~$H$, their {\em union\/} is defined to be the graph $F = G
\cup H$ with vertex set $V(F) = V(G) \cup V(H)$ and edge set $E(F) =
E(G) \cup E(H)$.
Given a graph~$G$, a {\em coloring\/} of $G$ is a mapping from $V(G)$
to the positive integers, which represent the colors. A coloring
$\psi$ of $G$ is called {\em proper\/} if, for any two vertices $x$ and
$y$ in~$V(G)$, if $\{x,y\} \in E(G)$ then $\psi(x) \neq \psi(y)$. The
{\em chromatic number\/} of graph $G$ (denoted $\chi(G)$) is the
minimum number of colors needed to properly color~$G$. Given a fixed
constant $k \geq 1$, graph $G$ is said to be {\em $k$-colorable\/} if
and only if there exists a proper coloring of $G$ using no more than
$k$ colors.
\section{Complexity of graph coloring when heuristics do well}
Numerous heuristics for graph coloring problems have been proposed.
Typically, such a heuristic consists of two parts: In the first part,
a suitable ordering of the vertices of the graph is fixed. In the
second part, the actual coloring algorithm is applied to the vertices
in the fixed order to color the graph. A very basic coloring
procedure is the {\em sequential algorithm\/} (sometimes
called {\em greedy algorithm\/}), which proceeds as follows. Assume
the vertices of the graph are given in the order $v_1, v_2 , \ldots ,
v_n$. Assign color 1 to~$v_1$. For each of the remaining vertices
$v_i$ in order, assign to $v_i$ the minimum color available, that is, the
smallest color that, so far, has not been assigned to any vertex
adjacent to~$v_i$. The sequential algorithm is denoted by~${\tt
SEQ}$.
Though the local action of the sequential algorithm appears to be
quite reasonable, {\em globally\/} it may fail miserably, depending on
the vertex ordering chosen. Johnson~\cite{joh:c:graph-coloring}
exhibited a sequence $G_3, \ldots , G_m, \ldots$ of graphs such that
each $G_m$ is 2-colorable, the size of $G_m$ is linear in~$m$, and yet
the number of colors used by the sequential algorithm on input $G_m$
is at least $m$ for some (unfortunate) vertex ordering. Thus, for some
ordering, the sequential algorithm achieves the worst approximation
ratio (of the chromatic number) possible.
Johnson~\cite{joh:c:graph-coloring} proved similar results for a
number of prominent graph coloring heuristics, most of which apply the
sequential coloring algorithm to various vertex orderings that are
obtained by seemingly reasonable procedures.
One such order-finding procedure is to order the vertices by {\em
decreasing degree}. However, this is a rather static approach, since
the place of any vertex in this ordering is independent of previously
ordered vertices. A more flexible way of obtaining a vertex ordering
is the recursive {\em smallest-last\/} ordering proposed by
Matula, Marble, and Isaacson
\cite{mat-mar-isa:b:graph-coloring}, which dynamically proceeds as
follows. Given a graph $G$ with $n$ vertices, choose any vertex of
minimum degree to be the last vertex, $v_n$. For $i>1$, let $v_i,
\ldots , v_n$ be those vertices that have already been ordered. Choose
any vertex of minimum degree in the subgraph of $G$ induced by
$V(G) - \{v_i, \ldots , v_n\}$ to be the next vertex, $v_{i-1}$, and proceed
inductively backward until all vertices are ordered. Note that, in
both orderings, there are nondeterministic choices to be made whenever
there are more vertices than one of minimum degree at any point of the
procedure.
We write ${\tt DD}$ to denote (the obvious nondeterministic procedure to
obtain) any ordering by decreasing degree, and we write ${\tt SL}$ to
denote (the above nondeterministic procedure to obtain) any
smallest-last ordering. Combining the ordering and coloring
algorithms to one algorithm, ${\tt A}$, then specifies the
metaproblem $\algthreecolor$ defined in the introduction. For
instance, combining the smallest-last ordering with the sequential
algorithm gives the following:
\begin{quote}
{Decision problem}: $\slseqthreecolor$. \\%[1mm]
{Instance}: A
% 3-colorable
graph $G$. \\
{Question}: Does there exist a sequence of
nondeterministic choices (between vertices of minimum degree) in the
smallest-last ordering of $V(G)$ such that the sequential algorithm
traversing $V(G)$ in that order properly 3-colors graph~$G$?
\end{quote}
First we show that the $\threecolor$ problem, restricted to those
input graphs on which the sequential algorithm applied to some ${\tt
DD}$ vertex ordering finds a solution, is no easier to solve than
the general problem.\footnote{Proposition~\ref{prop:dd} clearly
holds for the more general problem
$\kcolor$ (``Given a graph $G$ and a constant $k \leq ||V(G)||$, is
it true that $\chi(G) \leq k$?'')
with $k \geq 3$ as well; we focus on $\threecolor$
for simplicity.}
\begin{proposition}
\label{prop:dd}
$\ddseqthreecolor$ is $\np$-complete.
\end{proposition}
\begin{proof}
To reduce
% the NP-complete problem
$\threecolor$ to its
restriction $\ddseqthreecolor$, fix any graph $G$ and a vertex of
largest degree, say~$w$, in~$G$.
Without loss of generality, assume $\mbox{\it deg}(w)
\geq 1$. For each vertex $v \in V(G) -\{w\}$, add $\mbox{\it deg}(w) -
\mbox{\it deg}(v)$ new vertices $x_{v,1}$, $x_{v,2}$, $\ldots $,
$x_{v,\mbox{\it\scriptsize deg}(w) - \mbox{\it\scriptsize deg}(v)}$
to~$G$, and connect $v$ with each $x_{v,i}$ by an edge. Call the
resulting graph~$G'$. Then all vertices in $G'$ that are also
vertices of $G$ have the same degree, $\mbox{\it deg}(w)$, in~$G'$.
All new vertices $x_{v,i}$ in $G'$ have degree~1.
%fyi%
%fyi% Assuming $G \in
%fyi% \threecolor$, fix some proper 3-coloring, $\psi$, of~$G$ and define
%fyi% the three color classes $V_i \equalsdef \{ v \in V(G) \mid \psi(v) =
%fyi% i\}$, for $i \in \{1, 2, 3\}$, that correspond to~$\psi$. Let $V_4
%fyi% \equalsdef V(G') - V(G)$ be the new vertices of~$G'$. Since all
%fyi% vertices in $V_1 \, \cup\, V_2 \, \cup\, V_3$ have the same degree
%fyi% in~$G'$ and since all vertices in $V_4$ have degree~1,
%fyi% % there exists an order $<$ that orders all
%fyi% % vertices in $V(G')$ by decreasing degree and such that, for all $i,j
%fyi% % \in \{1, 2, 3, 4\}$ and for all $u,v \in V(G')$, if $u \in V_i$ and $v
%fyi% % \in V_j$ and $u < v$, then $i \leq j$.
%fyi% $V(G')$ can be ${\tt DD}$-ordered such that the vertices of $V_i$ come
%fyi% before those of $V_j$ whenever $i < j$. This property ensures that the
%fyi% sequential algorithm, applied to the vertices of $G'$ in this order,
%fyi% properly 3-colors~$G'$. Conversely, if $G$ is not 3-colorable then, by
%fyi% construction, $G'$ is not 3-colorable. Hence, $G' \not\in
%fyi% \ddseqthreecolor$.~\qed
It follows that $G \in \threecolor$ if and only if $G' \in
\ddseqthreecolor$.
\end{proof}
The construction given in the proof of Proposition~\ref{prop:dd} fails
for the smallest-last ordering, since the new vertices~$x_{v,i}$,
which are added in order to suitably increase the degree of any given
vertex $v$ relative to other vertices in~$G'$, themselves have only
degree~1. Thus, in general, they occur after $v$ in any
smallest-last ordering, and, as soon as they are ${\tt SL}$-ordered,
they are deleted from the graph and no longer increase the degree of
$v$ relative to other vertices still to be ordered.
\begin{figure}[tbh]
\begin{center}
\input{sl.eepic}
\end{center}
\caption{\label{fig:sl}
Graph~$D_{u,4}$ for Lemma~\ref{lem:sl}}
\end{figure}
The key construct to avoid this difficulty is given in
Lemma~\ref{lem:sl} and is illustrated for a special case by graph
$D_{u,4}$ shown in
Figure~\ref{fig:sl}. Consider any graph $E'$ and
suppose that some ${\tt SL}$ ordering of $V(E')$ is currently being
computed, $E$ is the subgraph of $E'$ induced by the vertices still to
be ordered, and that two vertices $u, v \in V(E)$ have a degree in $E$
such that, say, $u$ would be ranked above $v$ in any ${\tt SL}$
ordering. The purpose of Lemma~\ref{lem:sl} is to show how to flip
$u$ and $v$ in the ${\tt SL}$ ordering, assuming that the structure of
$E'$ requires such a flip for the sequential algorithm to find a
proper 3-coloring of $E'$ (if one exists).
\begin{lemma}
\label{lem:sl} Let $E$ be any given graph. Let $u, v \in V(E)$ be
vertices such that $\mbox{\it deg}(v) > \mbox{\it deg}(u) > 0$
in~$E$, and let $s = \mbox{\it deg}(v)$. There exists a
graph $D_{u,s}$ with $V(E) \cap V(D_{u,s}) = \{u\}$ and such that
\begin{enumerate}
\item[\rm (i)] $\mbox{\it deg}(u) > \mbox{\it deg}(v)$ in $E \cup
D_{u,s}$,
\item[\rm (ii)] $V(D_{u,s}) \cup \{v\}$ can be ${\tt SL}$-ordered such
that each element of $V(D_{u,s}) - \{u\}$ is ranked above $v$ and
below~$u$, and
\item[\rm (iii)] algorithm ${\tt SEQ}$ applied to this order properly
3-colors~$D_{u, s}$, regardless of which color $i \in \{1, 2, 3\}$ it
starts with to color~$u$.
\end{enumerate}
\end{lemma}
\begin{proof}
Define graph $D_{u, s}$ by the vertex set
\[
V(D_{u, s}) \equalsdef
\{u\} \cup \{d_{u,i} \mid 1 \leq i \leq 2(s-1) \}
\]
and the edge set
\[
E(D_{u, s}) \equalsdef
\{\{u, d_{u,i}\} \mid 1 \leq i \leq 2(s-1)\} \cup
\{\{d_{u,i}, d_{u,j}\} \mid i \not\equiv j \bmod 2\}.
\]
Note that the degree of $u$ (relative to~$v$) has increased in $E \cup
D_{u,s}$ by $2(s-1)$. Since $\mbox{\it deg}(v) = s > 1$, this proves
property~(i). Property~(ii) follows from property~(i) and the fact
that for each $d_{u,i}$ in $D_{u, s}$, $\mbox{\it deg}(d_{u,i}) = s$
in $E \cup D_{u,s}$: the vertex set $V(D_{u, s}) \cup \{v\}$ can be ${\tt
SL}$-ordered as $u, d_{u,1} , d_{u,2} , \ldots , d_{u,2(s-1)} , v$
in~$E \cup D_{u,s}$. In particular, the sequential algorithm traversing
$V(D_{u, s})$ in this order properly 3-colors $D_{u, s}$ no matter which
color it starts with to color~$u$. If color $i \in \{1, 2, 3\}$ is
assigned to~$u$, then color $1 + (i \bmod 3)$ is assigned to all
vertices $d_{u,j}$ with odd~$j$, and color $2 + (i \bmod 3)$ is
assigned to all vertices $d_{u,j}$ with even~$j$. This establishes
property~(iii) and proves the lemma.
\end{proof}
\begin{theorem}
\label{thm:sl}
$\slseqthreecolor$ is $\np$-complete.
\end{theorem}
\begin{proof}
Instead of directly reducing
$\threecolor$ to \slseqthreecolor\
%%%Copyed had to take out of math to get hyphenation.
as in Proposition~\ref{prop:dd},
% (in which case we would have to argue about any instance of
% $\threecolor$ of arbitrary form).
it is useful to base our reduction on one ``generic''
instance of $\threecolor$, namely, on the graph $G$ constructed by
Stockmeyer to reduce
$\threesat$ to $\threecolor$~(\cite{sto:j:planar-3color}; see
also~\cite{gar-joh-sto:j:simplified-np-completeness}).
Simplifying the technical proof
details, this approach provides a reduction from $\threesat$ to
$\slseqthreecolor$.
% For completeness and self-containment, we recall
% the Stockmeyer reduction, denoted $r$, in Appendix~\ref{app:gjs}.
First we recall the Stockmeyer reduction.
Let $\phi$ be any given instance of $\threesat$ with $n$ variables,
$x_1 , x_2, \ldots , x_n$, and
$m$ clauses, $C_1 , C_2 , \ldots , C_m$. The
reduction maps $\phi$ to the graph $G$ constructed as follows. The
vertex set of $G$ is defined by
$$
V(G) \equalsdef
\{v_1, v_2, v_3 \} \cup \{x_i , \bar{x}_i \mid 1 \leq i \leq
n\} \cup \{y_{jk} \mid 1 \leq j \leq m \ \wedge\ 1 \leq k \leq 6\},
$$
where the $x_i$ and $\bar{x}_i$ are vertices representing the literals
$x_i$ and~$\bar{x}_i$. The edge set of $G$ is defined by
\begin{eqnarray*}
E(G) & \equalsdef & \{\{v_1, v_2\}, \{v_2, v_3\}, \{v_1, v_3\}\} \\
& & \cup\ \{\{x_i , \bar{x}_i\} \mid 1 \leq i \leq n\} \\
& & \cup\ \{\{v_3 , x_i\}, \{v_3 , \bar{x}_i\} \mid 1 \leq i \leq n\} \\
& & \cup\ \{\{a_j , y_{j1}\}, \{b_j , y_{j2}\}, \{c_j , y_{j3}\} \mid
1 \leq j \leq m\} \\
& & \cup\ \{\{v_2 , y_{j6}\}, \{v_3 , y_{j6}\} \mid
1 \leq j \leq m\} \\
& & \cup\ \{\{y_{j1} , y_{j2}\}, \{y_{j1} , y_{j4}\}, \{y_{j2} ,
y_{j4}\} \mid 1 \leq j \leq m\} \\
& & \cup\ \{\{y_{j3} , y_{j5}\}, \{y_{j3} , y_{j6}\}, \{y_{j5} ,
y_{j6}\} \mid 1 \leq j \leq m\} \\
& & \cup\ \{\{y_{j4} , y_{j5}\} \mid 1 \leq j \leq m\},
\end{eqnarray*}
where $a_j , b_j , c_j \in \bigcup_{1 \leq i \leq n} \{x_i ,
\bar{x}_i\}$ are vertices representing the literals occuring in clause
$C_j = (a_j \vee b_j \vee c_j)$.
\begin{figure}[tbh]
\begin{center}
\input{key.eepic}
\end{center}
\caption{\label{fig:key}
Graph $H$ of the Stockmeyer reduction}
\end{figure}
The graph $H$ shown in
Figure~\ref{fig:key} is the key construct in this reduction, which
uses $m$ disjoint copies of $H$ (with corresponding subscripts), one
for each clause $C_j$ of~$\phi$. Crucially, the correctness of the
reduction (i.e., $\phi$ is satisfiable if and only if $G$ is
3-colorable) results from the following two properties of graph~$H$:
\begin{eqnarray}
\begin{minipage}[t]{4.5in}
Any coloring of the vertices $a$, $b$, and $c$ that assigns color~1
to one of $a$, $b$, and $c$ can be extended to a proper 3-coloring
of $H$ that assigns color~1 to~$y_6$.
\end{minipage}\label{key1}
\end{eqnarray}
\begin{eqnarray}
\begin{minipage}[t]{4.5in}
If $\psi$ is a proper 3-coloring of $H$ with
$\psi(a) = \psi(b) = \psi(c) = i$, then $\psi(y_6) = i$.
\end{minipage}
\end{eqnarray}
Now we transform $G$ into a new graph $F$ such that
$F \in\ $\slseqthreecolor\ if and only if $G \in \threecolor$
(if and only if $\phi \in \threesat$).
For each vertex $u \in V(G) - \{y_{j6} \mid 1 \leq j \leq m\}$, we
define a graph $D_{u,s}$ associated with $u$ as in Lemma~\ref{lem:sl},
for some suitable~$s$. Lemma~\ref{lem:sl} merely explains
one local part of the overall construction; globally, the size of
graph $D_{u,s}$ may affect the size of some other graph $D_{u',s'}$.
The respective values of $s$ for the various graphs $D_{u,s}$ are
chosen so as to ``guide'' the ${\tt SL}$ algorithm so that an ordering
can be obtained for which the ${\tt SEQ}$ algorithm can properly
3-color $F$, assuming $F$ {\em is\/} 3-colorable.
The vertex set of graph $F$ is given by
\begin{eqnarray*}
V(F) & \equalsdef &
V(D_{v_1, 128})
\cup V(D_{v_2, 64}) \cup V(D_{v_3, 128}) \\
& & \cup \bigcup_{1 \leq i \leq n} V(D_{x_i, 32})
\cup \bigcup_{1 \leq i \leq n} V(D_{\bar{x}_i, 32}) \\
& & \cup \bigcup_{1 \leq j \leq m} V(D_{y_{j1}, 16})
\cup \bigcup_{1 \leq j \leq m} V(D_{y_{j2}, 16})
\cup \bigcup_{1 \leq j \leq m} V(D_{y_{j4}, 8}) \\
& & \cup \bigcup_{1 \leq j \leq m} V(D_{y_{j3}, 4})
\cup \bigcup_{1 \leq j \leq m} V(D_{y_{j5}, 4})
\cup \{y_{j6} \mid 1 \leq j \leq m\}.
\end{eqnarray*}
Note that $V(G) \seq V(F)$. The edge set of graph $F$ is given by
\begin{eqnarray*}
E(F) & \equalsdef &
E(G)
\cup E(D_{v_1, 128})
\cup E(D_{v_2, 64}) \cup E(D_{v_3, 128}) \\
& & \cup \bigcup_{1 \leq i \leq n} E(D_{x_i, 32})
\cup \bigcup_{1 \leq i \leq n} E(D_{\bar{x}_i, 32}) \\
& & \cup \bigcup_{1 \leq j \leq m} E(D_{y_{j1}, 16})
\cup \bigcup_{1 \leq j \leq m} E(D_{y_{j2}, 16})
\cup \bigcup_{1 \leq j \leq m} E(D_{y_{j4}, 8}) \\
& & \cup \bigcup_{1 \leq j \leq m} E(D_{y_{j3}, 4})
\cup \bigcup_{1 \leq j \leq m} E(D_{y_{j5}, 4}).
\end{eqnarray*}
This construction yields only a linear blow-up in the size of graph
$F$ (relative to the size of~$G$), and the reduction is
polynomial-time computable.
We now argue that the construction is
correct. Suppose $\phi$ is satisfiable (and thus $G$ is 3-colorable).
Fix some satisfying assignment $\vec{\alpha} = (\alpha_1 , \alpha_2 ,
\ldots , \alpha_n)$, where $\alpha_i = 1$ if variable $x_i$ is set to true
under this assignment, and $\alpha_i = 0$ otherwise.
For any literal~$\ell$, let $\vec{\alpha}(\ell)$ denote the value
assigned to $\ell$ by $\vec{\alpha}$; that is, $\vec{\alpha}(\ell) =
\alpha_i$ if $\ell = x_i$, and $\vec{\alpha}(\ell) =
1 - \alpha_i$ if $\ell = \bar{x}_i$.
By construction and by properties~(i) and (ii) of Lemma~\ref{lem:sl},
the vertex set of $F$ can be ${\tt SL}$-ordered according to
conditions~(a)--(d) below. For convenience, we write $\vec{D}_{u,s}$
to denote the vertex set of graph $D_{u,s}$ given in the order
$u, d_{u,1} , d_{u,2} , \ldots , d_{u,2(s-1)}$.
\begin{enumerate}
\item[(a)] $V(F)$ is ordered in three blocks: The first block contains
the vertices
\[
V(D_{v_1, 128}) \cup V(D_{v_2, 64}) \cup
V(D_{v_3, 128})
\]
in the order specified by~(b); the second block contains the vertices
\[
\bigcup_{1 \leq i \leq
n} \left( V(D_{x_i, 32}) \cup V(D_{\bar{x}_i,32}) \right)
\]
in the order specified by~(c); and the third block contains
% \[
% \{y_{jk} \mid 1 \leq j \leq m \ \wedge\ 1 \leq k \leq 6\} \cup
% \bigcup_{1 \leq j \leq m} V(D_{y_{j1}, 16}) \cup \bigcup_{1 \leq j
% \leq m} V(D_{y_{j2}, 16}) \cup \bigcup_{1 \leq j \leq m}
% V(D_{y_{j4}, 8}) \cup \bigcup_{1 \leq j \leq m} V(D_{y_{j3}, 4}) \cup
% \bigcup_{1 \leq j \leq m} V(D_{y_{j5}, 4})
% \]
all the remaining vertices of $F$ in the order specified by~(d).
\item[(b)] The first block is ordered as $\vec{D}_{v_3,128} ,
\vec{D}_{v_1,128} , \vec{D}_{v_2,64}$.
\item[(c)] For each~$i$, $1 \leq i \leq n$, the vertex set $V(D_{x_i,
32}) \cup V(D_{\bar{x}_i, 32})$ can be ${\tt SL}$-ordered as
$\vec{D}_{x_i, 32} , \vec{D}_{\bar{x}_i, 32}$ if $\alpha_i = 1$, and
it can be ${\tt SL}$-ordered as $\vec{D}_{\bar{x}_i, 32} ,
\vec{D}_{x_i, 32}$ if $\alpha_i = 0$.
\item[(d)] For each~$j$, $1 \leq j \leq m$, let $C_j = (a_j \vee b_j
\vee c_j)$ be the $j$th clause of~$\phi$, with literals $a_j , b_j ,
c_j \in \bigcup_{1 \leq i \leq n} \{x_i , \bar{x}_i\}$. Let
$\vec{\alpha}(C_j)$ be a shorthand for $(\vec{\alpha}(a_j),
\vec{\alpha}(b_j), \vec{\alpha}(c_j))$. Note that since
$\vec{\alpha}$ satisfies~$\phi$, $\vec{\alpha}(C_j) \neq (0,0,0)$
for each~$j$. Recall that the literals $a_j$, $b_j$, $c_j$
in $C_j$ are identified with
the corresponding vertices of~$G$. For each~$j$, let $Y_j$ denote
the vertex set
associated with~$C_j$, that is, $Y_j \equalsdef V(D_{y_{j1}, 16}) \cup
V(D_{y_{j2}, 16}) \cup V(D_{y_{j3}, 4}) \cup V(D_{y_{j4}, 8}) \cup
V(D_{y_{j5}, 4}) \cup \{y_{j6}\}$. Depending on $\vec{\alpha}(C_j)$,
$Y_j$ can be ${\tt SL}$-ordered as
follows:
\begin{enumerate}
\item[(d1)] If $\vec{\alpha}(C_j) \in \{(1,1,1),\allowbreak (1,1,0),
(0,1,1),(0,1,0)\}$, then $Y_j$ is ordered as $\vec{D}_{y_{j1}, 16}$,
$\vec{D}_{y_{j2}, 16}$, $\vec{D}_{y_{j4}, 8}$, $\vec{D}_{y_{j3}, 4}$,
$\vec{D}_{y_{j5}, 4}$, $y_{j6}$.
\item[(d2)] If $\vec{\alpha}(C_j) \in \{(1,0,1),(1,0,0)\}$, then $Y_j$
is ordered as $\vec{D}_{y_{j2}, 16}$, $\vec{D}_{y_{j1}, 16}$,
$\vec{D}_{y_{j4}, 8}$, $\vec{D}_{y_{j3}, 4}$, $\vec{D}_{y_{j5}, 4}$,
$y_{j6}$.
\item[(d3)] If $\vec{\alpha}(C_j) \in \{(0,0,1)\}$, then $Y_j$ is
ordered as $\vec{D}_{y_{j1}, 16}$, $\vec{D}_{y_{j2}, 16}$,
$\vec{D}_{y_{j4}, 8}$, $\vec{D}_{y_{j5}, 4}$, $\vec{D}_{y_{j3}, 4}$,
$y_{j6}$.
\end{enumerate}
\end{enumerate}
The relative order between vertices not specified by
conditions~(a)--(d) is irrelevant for the argument and may be fixed
arbitrarily (consistent with the rules of the ${\tt SL}$-ordering).
The correctness of the reduction follows from the next
property, which holds for each~$j$, $1 \leq j \leq m$:
\begin{eqnarray}
\begin{minipage}[t]{4.5in}
Assume
that the vertices representing the literals of $C_j$ are colored
such that only colors~2 and~3 are assigned, and color~2 is assigned
to at least one of $a_j$, $b_j$, and~$c_j$. Then, the ${\tt SEQ}$
algorithm (traversing $Y_j$ in one of the orders given by (d1), (d2), or
(d3), depending on $\vec{\alpha}(C_j)$)
properly 3-colors the subgraph of $F$ induced by
$\{a_j\} \cup \{b_j\} \cup \{c_j\} \cup Y_j$
such that color~2 is assigned to~$y_{j6}$.
\end{minipage}
\label{seqkey1}
\end{eqnarray}
Property~(\ref{seqkey1}) is similar to
property~(\ref{key1}) of the Stockmeyer reduction,
suitably tailored to the specifics of the ${\tt SEQ}$ algorithm,
and it straightforwardly follows from property~(iii) of
Lemma~\ref{lem:sl} and the vertex order of $Y_j$ given in~(d) above.
Observe that in the current case ($\phi$ is satisfiable), there exists
a vertex ordering of $F$ consistent with
conditions~(a)--(d) so that the ${\tt SEQ}$ algorithm can properly
3-color graph~$F$. In
particular,
it computes a coloring $\psi$ of $F$ such that
\begin{itemize}
\item
$\psi(v_3) = 1$, $\psi(v_1) = 2$, $\psi(v_2) = 3$;
\item
for each $i$ with $1 \leq i\leq n$,
\begin{itemize}
\item
if $\alpha_i = 1$, then $\psi(x_i) = 2$ and
$\psi(\bar{x}_i) = 3$,
\item
if $\alpha_i = 0$, then $\psi(x_i) = 3$ and
$\psi(\bar{x}_i) = 2$.
\end{itemize}
\end{itemize}
Since $\vec{\alpha}$ is a satisfying assignment of~$\phi$,
coloring $\psi$ assigns color~2 to at least one (vertex representing
a) literal of~$C_j$, for each~$j$, $1 \leq j \leq m$. By
property~(\ref{seqkey1}), for each~$j$, $\psi$ is a proper 3-coloring
of the subgraph of $F$ induced by
$\{a_j\} \cup \{b_j\} \cup \{c_j\} \cup Y_j$ and satisfies $\psi(y_{j6}) =
2$. Property~(iii) of Lemma~\ref{lem:sl} implies that $\psi$ (as
specified so far) can be extended to a proper 3-coloring of~$F$.
Conversely, suppose $\phi$ is not satisfiable, so $G$ is not
3-colorable. By construction, $G$ is a subgraph of~$F$; so $F$ is not
3-colorable.
Thus, in particular, $F \not\in \slseqthreecolor$.
\end{proof}
Matula, Marble, and Isaacson
\cite{mat-mar-isa:b:graph-coloring} and
Johnson~\cite{joh:c:graph-coloring} proposed generalizations of
the sequential algorithm that allow the occasional {\em
interchange\/} of two colors (in the coloring being computed)
subject to certain sets of constraints.
% Johnson's algorithm, here
% denoted ${\tt SEQINT}_1$, is somewhat more general than the one of
% Matula et al., denoted ${\tt SEQINT}_2$, since the set of conditions
% under which an interchange is allowed in ${\tt SEQINT}_2$ is slightly
% more restrictive than the set of conditions required in ${\tt
% SEQINT}_1$ for an interchange to be performed.
Both
sequential-with-interchange algorithms may be combined with any vertex
ordering; we focus on the ${\tt DD}$ and ${\tt SL}$ orderings.
% Matula
% et al.~\cite{mat-mar-isa:b:graph-coloring} provided empirical evidence
% that the $\slseqint_2$ algorithm requires significantly fewer colors
% than various other heuristic algorithms on random graphs.
%
% The problems $\ddseqint_i\mbox{-}\threecolor$ and
% $\slseqint_i\mbox{-}\threecolor$, for $i \in \{1,2\}$, each are
% in~$\np$. It should be noted that the nondeterminism here not only
% underlies the order-finding procedure, where more than one vertex of
% minimum degree may exist, but also occurs in the coloring algorithm,
% where more than one bichromatic interchange may be possible.
Since the ${\tt SEQINT}_i$ algorithms include the
sequential algorithm as a special case (in which no interchange is
performed), we immediately have the following corollaries from,
respectively, Proposition~\ref{prop:dd} and Theorem~\ref{thm:sl}.
\begin{corollary}
\label{cor:ddseqint}
Both $\ddseqint_1\mbox{-}\threecolor$ and
$\ddseqint_2$-\threecolor\ are $\np$-complete.
\end{corollary}
\begin{corollary}
\label{cor:slseqint}
Both $\slseqint_1\mbox{-}\threecolor$ and
$\slseqint_2$-\threecolor\ are $\np$-complete.
\end{corollary}
The last heuristic considered in this
%% section
paper is the algorithm of
Wood \cite{woo:j:graph-coloring} which, given an input graph $G$ with
$n$ vertices, proceeds in two stages as follows. In the first stage,
all $n(n-1)/2$ pairs of distinct vertices are ordered by decreasing
similarity, where the {\em similarity\/} of two distinct vertices $x$
and $y$ is defined to be
\[
\mbox{\it sim\/}(x,y) \equalsdef \left\{
\begin{array}{ll}
0 & \mbox{if $\{x,y\} \in E(G)$} \\
||N(x) \cap N(y)|| & \mbox{otherwise.}
\end{array}
\right.
\]
Given this order, $G$ is partially colored in the first stage by
executing the following steps for each pair $\{x,y\}$ in turn. In what
follows, let $c$ be a variable whose value gives the number of colors
used so far.
% , and let $\psi$ be the partial coloring being computed.
\begin{enumerate}
\item[(1)] If $\mbox{\it sim\/}(x,y) = 0$, then halt.
\item[(2)] If both $x$ and $y$ are colored, then go to next pair.
\item[(3)] If one vertex, say, $x$, is colored, and the other one, $y$,
is uncolored, then do the following:
\begin{enumerate}
\item[(3a)] if $\mbox{\it deg}(y) < c$, then go to next pair;
\item[(3b)] if some vertex adjacent to $y$ has the same color as~$x$,
then go to next pair;
\item[(3c)] otherwise, assign to $y$ the color assigned to~$x$.
\end{enumerate}
\item[(4)] If both $x$ and $y$ are uncolored, then do the following:
\begin{enumerate}
\item[(4a)] if both $\mbox{\it deg}(x) < c$ and $\mbox{\it deg}(y) <
c$, then go to next pair;
\item[(4b)] otherwise, assign to both $x$ and $y$ the minimum color
available (i.e., the smallest color $j \geq 1$ such that neither $x$
nor $y$ is adjacent to a vertex colored~$j$).
\end{enumerate}
\end{enumerate}
After the first stage, there may remain some uncolored vertices. If
so, the coloring of $G$ is completed in the second stage using
the ${\tt DD}\mbox{-}{\tt SEQ}$ algorithm. Wood's algorithm is
denoted by ${\tt WOOD}$. Note that both stages of Wood's algorithm
contain some amount of nondeterminism: In the first stage, we may
choose between different vertex pairs of the same similarity (when
there are more than one); in the second stage, we may choose among
several vertices of minimum degree.
\begin{theorem}
\label{thm:wood}
${\tt WOOD}\mbox{-}\threecolor$ is $\np$-complete.
\end{theorem}
\begin{proof}
The proof is similar to the proof of
Proposition~\ref{prop:dd}, the difference being that now we have to
equalize the similarity between pairs of vertices instead of the
degree of vertices. Let $G$ be any given graph. We transform $G$ into
a new graph $H$ such that $G$ is 3-colorable if and only if $H$ can be
3-colored by Wood's algorithm.
Let $s' \equalsdef \max \{\mbox{\it
sim\/}(x,y) \mid x, y \in V(G) \mbox{ with } x \neq y\}$ be the
maximum similarity of all vertex pairs in~$G$, and let $s \equalsdef
\max\{3, s'\}$.
The vertex set of $H$ is given by
\begin{eqnarray*}
V(H) & \equalsdef & V(G) \cup \{v' \mid v \in V(G)\} \cup \{x_{v,i} \mid v
\in V(G) \ \wedge\ 1 \leq i \leq s\},
\end{eqnarray*}
where the $||V(G)||$ vertices $v'$ and the $s||V(G)||$ vertices
$x_{v,i}$ are new. The edge set of $H$ is given by
\begin{eqnarray*}
E(H) & \equalsdef & E(G) \cup \{\{v, x_{v,i}\} \mid v \in
V(G) \ \wedge\ 1 \leq i \leq s\} \\
& & {}\cup \{\{x_{v,i}, v'\} \mid v \in
V(G) \ \wedge\ 1 \leq i \leq s\}.
\end{eqnarray*}
This reduction is polynomial-time computable, since the similarity of
all vertex pairs in~$G$ (and hence~$s$) can be computed in time
polynomial in the size of (the encoding of)~$G$. By construction,
$\mbox{\it sim\/}(v,v') = s$ for all vertices $v \in V(G)$, and the
similarity of all other vertex pairs of $H$ is at most~$s$. Thus,
all vertex pairs of the form $\{v, v'\}$, for $v \in V(G)$, can be
ranked above all other vertex pairs of $H$ in the first stage of
Wood's algorithm. Suppose $G$ is 3-colorable. Let $\psi$ be any fixed
proper 3-coloring of~$G$, and define the three color classes $V_i
\equalsdef \{ v \in V(G) \mid \psi(v) = i\}$, for $i \in \{1, 2, 3\}$,
that correspond to~$\psi$. Let $v_1 , v_2 , \ldots , v_n$ be an
ordering of $V(G)$ such that all vertices from $V_1$ come first,
followed by all vertices from $V_2$, which in turn are followed by all
vertices from~$V_3$. Consider the corresponding order $\{v_1 , v'_1\} ,
\{v_2 , v'_2\} , \ldots , \{v_n , v'_n\}$ of the first $n$ vertex
pairs of~$H$. Since $\mbox{\it deg}(v) \geq s \geq 3$ for all $v \in
V(G)$ and since $\mbox{\it deg}(v') = s \geq 3$ for the corresponding
vertices~$v'$, line~(4b) of the first stage of Wood's algorithm is
executed $n$ times and assigns color $\psi(v)$ in $G$ to both
$v$ and $v'$ in~$H$. The only vertices of $H$ as yet uncolored are
those of the form~$x_{v,i}$. It is then not hard to see that $\psi$
can be extended by Wood's algorithm to a proper 3-coloring of~$H$.
Conversely, if $G$ is not 3-colorable, then $H$ is not 3-colorable,
and consequently $H \not\in {\tt WOOD}\mbox{-}\threecolor$.
\end{proof}
Finally, we mention some open questions. What is the
complexity of the related problem of recognizing those graphs $G$ for which
a fixed heuristic can {\em find\/} the chromatic number $\chi(G)$
(instead of merely
deciding whether $\chi(G) \leq k$
%% with constant $k$ being part of the input
as with $\kcolor$)? What about
the recognition problem for {\em approximating\/} $\chi(G)$ within a fixed
factor $r \geq 1$ ($r$ rational) of optimal? As mentioned in the
introduction, these questions were successfully
resolved~\cite{hem-rot:j:max-independent-set-by-greed} for the case of
approximating the independence number with respect to the minimum-degree
greedy heuristic. However,
lower bounds for graph coloring
problems in general tend to be harder to achieve than those for
independent set problems. (But note that
$\parallelnp$ also is an upper bound for these chromatic
number problems---just like $\parallelnp$ is an upper bound for the
independence number problems.)~~The results of the present paper may be seen as
a first step toward resolving the more demanding questions raised
above. In fact, the
construction given in~\cite{hem-rot:j:max-independent-set-by-greed} is
based on the NP-completeness result
of~\cite{bod-thi-yam:j:greedy-for-maximum-independent-sets} for the
restriction of ${\tt Independent\mbox{ }Set}$ to those input graphs on
which MDG works well.
Thus, one may hope that the results of the present paper will lead
to progress regarding the above questions.
\section*{Acknowledgments}
I am very grateful to Lane Hemaspaandra
and Dieter Kratsch for helpful comments on an earlier draft of this
paper and for pointers to the literature.
\subsection*{Acknowledgment of support}
Author was supported
in part by grant NSF-INT-9815095/DAAD-315-PPP-g\"{u}-ab
and a Hei\-sen\-berg Fellowship of the Deut\-sche
For\-schungs\-ge\-mein\-schaft.
\bibliography{rothe}
\bibliographystyle{alpha}
\end{document}