% Template article for preprint document class `elsart'
% SP 2001/01/05

% Modified 2007/01/09 for CTW 2010
% Please find the original file at http://www.elsevier.com/

\documentclass{ctwart}

% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}

% if you use PostScript figures in your article
% use the graphics package for simple commands
% \usepackage{graphics}
% or use the graphicx package for more complicated commands
% \usepackage{graphicx}
% or use the epsfig package if you prefer to use the old commands
% \usepackage{epsfig}

% The amssymb package provides various useful mathematical symbols
\usepackage{amssymb}
\usepackage{pstricks,pst-node,pst-plot}

\begin{document}
\setcounter{page}{149}

\newtheorem{theorem}{Theorem}

\begin{frontmatter}

% Title, authors and addresses

% use the thanksref command within \title, \author or \address for footnotes;
% use the corauthref command within \author for corresponding author footnotes;
% use the ead command for the email address,
% and the form \ead[url] for the home page:
% \title{Title\thanksref{label1}}
% \thanks[label1]{}
% \author{Name\corauthref{cor1}\thanksref{label2}}
% \ead{email address}
% \ead[url]{home page}
% \thanks[label2]{}
% \corauth[cor1]{}
% \address{Address\thanksref{label3}}
% \thanks[label3]{}

\title{Efficient total domination}

% use optional labels to link authors explicitly to addresses:
% \author[label1,label2]{}
% \address[label1]{}
% \address[label2]{}

\author{Oliver Schaudt}
\ead{schaudt@zpr.uni-koeln.de}
\address{Institut f\"ur Informatik, Arbeitsgruppe Faigle/Schrader, Universit\"at zu K\"oln \\
Weyertal 80, 50931 Cologne, Germany}

\begin{keyword}
% keywords here, in the form: keyword \sep keyword

total domination \sep induced matchings \sep neighborhood hypergraphs

\end{keyword}

\end{frontmatter}

\section{Introduction}

All relevant graph classes and graph class inclusions not defined here are displayed in \cite{Brandstaedt}.
For each graph $G$, $V(G)$ denotes its set of vertices.

Total domination has been introduced 1980 by Cockayne, Dawes and Hedetniemi in \cite{Cockayne} and is intensively studied now.
A good introduction to the theory of (total) domination, giving a broad overview of the important results and applications, is given in \cite{Haynes}.
In the problem of total domination, one is interested in determining the value $\gamma_t(G)$ of a given graph $G$, 
defined as the smallest size of a subset $X \subseteq V(G)$ such that each vertex of $G$ has at least one neighbor in $X$.

Let $G$ be a simple undirected graph. 
A set $X \subseteq V(G)$ is said to be an \emph{efficiently total dominating set} of $G$, or an \textit{etd set}, 
if each $v \in V(G)$ is adjacent to exactly one vertex in $X$. 
$G$ is then said to be an \emph{efficiently total dominatable graph}, or $G$ is \textit{etd}.
The corresponding decision problem is denoted by \textit{ETD}.
Let $\mathbf{1}$ denote the vector with all components equal to 1 of suitable dimension.
ETD can alternatively be defined as the class of graphs whose neighborhood hypergraph has a perfect matching,
as the class of graphs whose adjacency matrix $A$ accepts the equation $Ax=\mathbf{1}$ for some 01-vector $x$,
and as the class of graphs that have an induced matching, such that each vertex is adjacent to exactly one matched vertex.
There is some literature on efficient domination, but in the case of efficient \textit{total} domination,
only a few papers have been published so far (according to our knowledge).

A simple but important result mentioned in \cite{Haynes} is the following

\begin{theorem}[See \cite{Haynes}] \label{the gamma t}
 Let $G$ be an etd graph. Each etd set $X$ of $G$ has cardinality $\gamma_t (G)$.
\end{theorem}

We can therefore understand efficient total domination as an extremal case of total domination.
Furthermore, understanding the structure of efficiently total dominatable graphs and the algorithmical complexity of 
the corresponding decision problem may put some light on total domination, too. 

\section{Main results}

Graph classes on which ETD is $NP$-complete can be obtained by reducing the well known Exact Cover decision problem (EC) to ETD.
Given an arbitrary 01-matrix $A$, EC asks for the 01-solvability of $Ax=1$. 
It is possible to reduce EC to ETD in the following way: Let $I$ denote the identity matrix of suitable dimension. 
Given a 01-matrix $A$, we define a function 
\begin{equation} \label{eqn reduction exact cover bipartite}
	A(X) = 
	\left( \begin{array}{clrrr} %
		X & 0 & 0 & A \\
		0 & 0 & I & I \\
		0 & I & 0 & 0 \\
		A^t & I & 0 & 0
	\end{array}	\right)
\end{equation}
and observe for each $X$, that $A$ is in EC iff $A(X)$ is in EC.
 
As $A(0)$ is the adjacency matrix of a bipartite graph, $A(0)$ is in EC iff this very graph is in ETD.
Let $J$ denote the square matrix with all components equal to 1 of suitable dimension.
$A(J-I)$ is the adjacency matrix of a $(1,2)$-colorable chordal graph, 
i.e. a chordal graph which can be partitioned into a clique and two independent sets, and $A(J-I)$ is in EC iff this very graph is in ETD. 
As EC is well known to be $NP$-complete, we conclude $NP$-completeness of ETD restricted to bipartite graphs and to $(1,2)$-colorable chordal graphs. 
As the class of $(1,2)$-colorable chordal graphs is only slightly bigger than the class of split graphs (which are exactly the $(1,1)$-colorable graphs) 
and ETD restricted to split graphs is trivial, we see that the gap of complexity between the two classes is big compared to their structural differences.

A further result is inspired by an idea stated by Lozin \cite{Lozin} in the context of induced matchings.
Let $\mathcal{F}$ be a (not necessarily finite) set of graphs.
We set $K(\mathcal{F})$ as the supremum over the lengths of all paths in graphs of $\mathcal{F}$, whose inner vertices have degree 2.
For given non negative integers $i , j , k$, a $star_{i,j,k}$ graph is constructed in the following way.
Start with three paths consisting of $i$, $j$ and $k$ vertices.
Choose an endvertex of each path and connect these to a single new vertex $r$.
For example, a $star_{k,0,0}$ is a path of length $k$ and a $star_{1,1,1}$ is a claw.

\begin{theorem} \label{the NP-completeness forbidden subgraphs}
Let $\mathcal{F}$ be a set of graphs with finite $K(\mathcal{F})$ such that there is 
no graph of $\mathcal{F}$ whose every connected component is a $star_{i,j,k}$.
ETD restricted to the class of bipartite $\mathcal{F}$-free graphs is $NP$-complete.
\end{theorem}

Choosing $\mathcal{F} = \{ K_{1,4} \}$, we see that ETD is $NP$-complete on the class of bipartite graphs with maximum degree 3.
Summarizing our results, we obtain the following

\begin{theorem} ETD is $NP$-complete when restricted to the following classes:
\begin{itemize}
\item planar bipartite graphs with maximum degree 3, bipartite graphs, comparability graphs

\item $(1,2)$-colorable chordal graphs, chordal graphs, perfect graphs
\end{itemize}
\end{theorem}

%
% Figure T3
%

\begin{figure}[tbp]
\begin{center}
\begin{pspicture}(0,0)(4,2)

\cnode(0.5,1){0.1cm}{r}
\cnode(1.5,0.5){0.1cm}{u1}
\cnode(2.5,0.5){0.1cm}{u2}
\cnode(3.5,0.5){0.1cm}{u3}
\cnode(1.5,1){0.1cm}{v1}
\cnode(2.5,1){0.1cm}{v2}
\cnode(3.5,1){0.1cm}{v3}
\cnode(1.5,1.5){0.1cm}{w1}
\cnode(2.5,1.5){0.1cm}{w2}
\cnode(3.5,1.5){0.1cm}{w3}

\ncarc[arcangle=0]{-}{r}{u1}
\ncarc[arcangle=0]{-}{u1}{u2}
\ncarc[arcangle=0]{-}{u2}{u3}
\ncarc[arcangle=0]{-}{r}{v1}
\ncarc[arcangle=0]{-}{v1}{v2}
\ncarc[arcangle=0]{-}{v2}{v3}
\ncarc[arcangle=0]{-}{r}{w1}
\ncarc[arcangle=0]{-}{w1}{w2}
\ncarc[arcangle=0]{-}{w2}{w3}

\end{pspicture}
\end{center}
\caption{$T_3$.}
\label{fig T3}
\end{figure}

%
% Figure end
%

In our research we observed that ETD is polynomial time solvable on various classes. 
A first class can be obtained by using the property of each balanced matrix $A$ \cite{Conforti}, 
that the corresponding set partitioning polytope $\{ x : Ax = 1 , 0 \le x \le 1 \}$ only has integral extreme points. 
Therefore ETD is polynomial solvable on the class of graphs with balanced adjacency matrices (\textit{balanced} graphs, \cite{Conforti}), 
i.e. graphs which only induce cycles of length four. 

Our main results are the polynomial solvability of ETD restricted to claw-free graphs \cite{Schaudt1} and to $T_3$-free chordal graphs \cite{Schaudt2}
($T_3$ is displayed in Fig. \ref{fig T3}). 

ETD on claw-free graphs can be reduced to ETD on line graphs in two steps in polynomial time.
ETD on line graphs is reducible to the perfect matching problem in certain auxiliary graphs in linear time.
Therefore, ETD on claw-free graphs is polynomial time solvable. 
Furthermore, etd claw-free graphs are necessarily perfect.
Thus, our result can be seen as an example for the claim stated in \cite{Faudree}, that claw-free perfect graphs
often accept polynomial time algorithms for problems which are $NP$-complete in general. 

In the case of $T_3$-free chordal graphs we use a polynomial time procedure to label the vertices of the graph with 0 and 1,
using the well known \textit{perfect elimination ordering} of chordal graphs. 
Each labeled vertex $v$ is either in every etd set of the graph, if $v$ is labeled with 1, or in no etd set, if $v$ is labeled with 0. 
The etd condition restricted to the unlabeled vertices forms, by $T_3$-freeness, an instance of 2-SAT. 
It therefore is a polynomial solvable problem.

Summarizing our results, we obtain the following

\begin{theorem} ETD is polynomial solvable when restricted to the following classes:
\begin{itemize}
 \item balanced graphs, chordal bipartite graphs, bipartite permutation graphs

 \item claw-free graphs, line graphs, line graphs of bipartite graphs

 \item $T_3$-free chordal graphs, interval graphs, circular arc graphs

 \item strongly chordal graphs, doubly chordal graphs

 \item $\overline{C_4}$-free graphs, co-chordal graphs, split graphs = $(1,1)$-colorable graphs

 \item $P_4$-free graphs = cographs
\end{itemize}
\end{theorem}

If we compare this list with the list of time complexities for total domination given in \cite{Henning}, we see some interesting differences: 
Total domination on the classes of line graphs of bipartite graphs and split graphs is $NP$-complete,
while polynomially solvable in the case of ETD. 
On the other hand, ETD is $NP$-complete restricted to the class of graphs with adjacency matrix $A(0)$ while total domination is trivially decidable on this class.

\begin{thebibliography}{9}

\bibitem{Brandstaedt} A. Brandst\"adt, V.B. Le, J. Spinrad, \textit{Graph classes: a survey}, SIAM Monographs on Discrete Math. Appl., Vol. 3, SIAM, Philadelphia, 1999. 

\bibitem{Cockayne} E.J. Cockayne, R.M. Dawes and S.T. Hedetniemi, \textit{Total domination in graphs}, Networks 10 (1980), pp. 211--219.

\bibitem{Conforti} M. Conforti, G. Cornu\'ejols and K. Vu\u{s}kovi\'c, \textit{Balanced matrices}, Discrete Mathematics 306 (2006), pp. 2411--2437.

\bibitem{Faudree} R. Faudree, E. Flandrin and Z. Ryj\`acek, \textit{Claw-free graphs -- A survey}, Discrete Mathematics 164 (1997), pp. 87--147.

\bibitem{Haynes} T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), \textit{Fundamentals of Domination in Graphs}, Marcel Dekker, Inc., New York, 1998.

\bibitem{Henning} M.A. Henning, \textit{A survey of selected recent results on total domination in graphs}, Discrete Mathematics 309, (2009), pp. 32--63.

\bibitem{Lozin} V.V. Lozin, \textit{On maximum induced matchings in bipartite graphs}, Information Processing Letters 81 (2002), pp. 7--11.

\bibitem{Schaudt1} O. Schaudt, \textit{On weighted efficient total domination}, submitted preprint.

\bibitem{Schaudt2} O. Schaudt, \textit{On efficient total domination}, submitted preprint.

\end{thebibliography}

\end{document}

