\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}