Software Engineering Department, Shamoon College of Engineering, Beer-Sheva
84100<EMAIL_ADDRESS>of Computer Science, Ben-Gurion
University, Beer-Sheva 84105<EMAIL_ADDRESS>Department of Computer
Science, Ben-Gurion University, Beer-Sheva 84105<EMAIL_ADDRESS>A. Karim Abu-Affash, Paz Carmi and Adi Krasin[300]Theory of computation Design
and analysis of algorithms This work was partially supported by Grant 2016116
from the United States – Israel Binational Science FoundationJohn Q. Open and
Joan R. Access 2 42nd Conference on Very Important Topics (CVIT 2016) CVIT
2016 CVIT 2016 December 24–27, 2016 Little Whinging, United Kingdom 42 23

# A Linear-Time Algorithm for Minimum $k$-Hop Dominating Set of a Cactus Graph

A. Karim Abu-Affash  Paz Carmi  Adi Krasin

###### Abstract

Given a graph $G=(V,E)$ and an integer $k\geq 1$, a $k$-_hop dominating set_
$D$ of $G$ is a subset of $V$, such that, for every vertex $v\in V$, there
exists a node $u\in D$ whose hop-distance from $v$ is at most $k$. A $k$-hop
dominating set of minimum cardinality is called a _minimum $k$-hop dominating
set_. In this paper, we present linear-time algorithms that find a minimum
$k$-hop dominating set in _unicyclic and cactus graphs._ To achieve this, we
show that the $k$-dominating set problem on unicycle graph reduces to the
_piercing circular arcs problem_ , and show a linear-time algorithm for
piercing sorted circular arcs, which improves the best known $O(n\log n)$-time
algorithm.

###### keywords:

Dominating set, cactus graph, unicyclic graph, piercing circular arcs

###### category:

##  1 Introduction

A _dominating set_ of an undirected graph $G=(V,E)$ is a subset $D\subseteq
V$, such that every vertex in $V\setminus D$ is adjacent to at least one
vertex in $D$. For arbitrary graphs, the problem of computing a minimum
dominating set is NP-complete [9]. Since the problem is a special case of
minimum set cover, it can be approximated within $1+\log{|V|}$ [14] but it
cannot be approximated within $(1-\varepsilon)\log{|V|}$, for any
$\varepsilon>0$ [20]. The problem admits a PTAS on planar graphs [2] and on
unit disk graphs [13, 19]. For trees, cactus, and permutation graphs, the
problem can be solved in linear time [5, 6, 11].

Given a graph $G=(V,E)$ on $n$ vertices and an integer $k\geq 1$, a $k$-_hop
dominating set_ of $G$ is a subset $D\subseteq V$, such that the hop distance
from every vertex in $V\setminus D$ is at most $k$ from at least one vertex of
$D$. Recently, several works devoted to the problem of finding a minimum
$k$-hop dominating set in graphs. The problem has been shown to be NP-complete
[1, 4] in general graphs. Demaine et al. [8] gave an $O(n^{4})$-time (fixed-
parameter) algorithm for the problem on planar and map graphs. Kundu and
Majumder [16] and Barman et al. [3] presented an optimal linear-time algorithm
for the problem on trees and interval graphs, respectively. The
$k$-_dominating number_ of a graph $G$, denoted by $\gamma_{k}(G)$, is the
cardinality of a minimum $k$-_hop dominating set_ of $G$. The $k$-dominating
number has been widely studied in the literature; see for example [7, 10, 12,
18, 21].

Applications on dominating and $k$-hop dominating sets in graphs are known in
several areas such as wireless networks [1] and social networks [4].

Let $G=(V,E)$ be an undirected graph. $G$ is called a _unicyclic_ graph if it
contains exactly one cycle. A vertex $u\in V$ is called a _cut vertex_ if
removing $u$ from $G$ increases the number of components of $G$. A _block_ of
$G$ is a maximal connected subgraph of $G$ without any cut vertex. $G$ is
called a _cactus_ graph if its blocks are either edges or cycles.

In [17], Lan and Chang considered a different variant of $k$-dominating set on
unicyclic and cactus graphs, where the goal is to find a minimum dominating
set $D$, such that each vertex is dominated by at least $k$ vertices from $D$.

In this paper, a linear-time algorithm is presented, which computes a minimum
piercing set for sorted circular arcs, this improves the current $O(n\log
n)$-time algorithm by Katz at al. [15]. We then show how to utilize this
result to obtain linear-time algorithms to the minimum $k$-hop dominating set
in unicyclic and cactus graphs.

##  2 Preliminaries

Let $G=(V,E)$ be an undirected graph. For two vertices $u,v\in V$, let
$d_{G}(u,v)$ denote the hop-distance between $u$ and $v$ in $G$. For a vertex
$u\in V$, let ${{\cal{N}}}_{i}(u)\subset V$ denote the $i$-neighborhood of
$u$, i.e., ${{\cal{N}}}_{i}(u)=\\{v\in V:d_{G}(u,v)\leq i\\}$. For a subset
$D\subseteq V$, let ${{\cal{N}}}_{i}(D)=\bigcup_{u\in D}{{\cal{N}}}_{i}(u)$.
For a subset $D\subseteq V$ and a vertex $u\in V$, let $\delta_{D}(u)$ denote
the distance of $u$ from $D$ (i.e., the distance of $u$ to the closest vertex
in $D$). A $k$-hop dominating set of $G$ is a subset $D\subseteq V$, such that
$\delta_{D}(u)\leq k$, for each vertex $u\in V$. Throughout the rest of the
paper, when we say distance we refer to hop-distance.

######  Problem  (kHDS).

Given an undirected graph $G=(V,E)$ and an integer $k\geq 1$, the goal in the
k-Hop Dominating Set problem is to compute a minimum k-hop dominating set of
$G$.

###  2.1 _kHDS_ on trees

Let $T=(V,E)$ be a tree on $n$ vertices. In [16], Kundu and Majumder presented
a linear-time algorithm that finds a minimum $k$-hop dominating set of $T$.
For completeness, based on their algorithm, we give a simpler (linear-time)
implementation of the algorithm that will be used as a black-box throughout
the rest of the paper.

Let $T_{r}$ be the rooted form of $T$ with an arbitrary vertex $r\in V$. For
each vertex $u\in V$, let $T_{u}$ be the subtree of $T_{r}$ rooted at $u$ and
let $h(T_{u})$ denote the height of $T_{u}$, i.e., $h(T_{u})=\max_{v\in
T_{u}}d_{T_{u}}(u,v)$. Let $\pi(u)$ denote the parent of $u$ in $T_{r}$ and
let $child(u)$ denote the set of children of $u$ in $T_{u}$.

######  Observation .

If $h(T_{r})\leq k$, then $D=\\{r\\}$ is a minimum $k$-hop dominating set of
$T_{r}$.

######  Observation .

There exists a minimum $k$-hop dominating set of $T_{r}$ that does not contain
any leaf of $T_{r}$.

Let $B$ be a subset of $V$. A _partial_ $k$-hop dominating set of $B$, denoted
by $k$-$Dom_{V}(B)$, is a subset $D$ of $V$, such that
$B\subseteq{{\cal{N}}}_{k}(D)$, i.e., for each vertex $v\in B$, there exists a
vertex $u\in D$, such that $d_{T_{r}}(u,v)\leq k$. The partial $k$-hop
dominating number, denoted by $\Gamma_{V}(B)$, is the cardinality of a minimum
$k$-$Dom_{V}(B)$. The following lemma follows from Observation 2.1.

######  Lemma 2.1.

If $T_{r}$ contains a leaf $v\notin B$, then
$\Gamma_{V}(B)=\Gamma_{V\setminus\\{v\\}}(B)$.

######  Lemma 2.2.

Let $T_{u}$ be a subtree of $T_{r}$ of height $k$ rooted at $u$. If there
exists a leaf $v\in B$ of depth $k$ in $T_{u}$, then
$\Gamma_{V}(B)=\Gamma_{V^{\prime}}(B^{\prime})+1$, where
$B^{\prime}=B\setminus{{\cal{N}}}_{k}(u)$ and $V^{\prime}$ is the set obtained
from $V$ by removing all vertices of $T_{u}$.

######  Proof 2.3.

Let $D$ be a minimum $k$-$Dom_{V^{\prime}}(B^{\prime})$. Then, by Observation
2.1, $D\cup\\{u\\}$ is a $k$-$Dom_{V}(B)$. Therefore,
$\Gamma_{V}(B)\leq|D\cup\\{u\\}|=\Gamma_{V^{\prime}}(B^{\prime})+1$. On the
other hand, since there exists a leaf $v\in B$ of depth $k$ in $T_{u}$, any
minimum $k$-$Dom_{V}(B)$ $D$ must contain at least one vertex $w$ in $T_{u}$,
and $D^{\prime}=D\setminus\\{w\\}\cup\\{u\\}$ is also a minimum
$k$-$Dom_{V}(B)$, since each vertex in $B$, that is dominated by $w$, is also
dominated by $u$. Thus, $D^{\prime}\setminus\\{u\\}$ is a
$k$-$Dom_{V^{\prime}}(B^{\prime})$, since ${{\cal{N}}}_{k}(u)\nsubseteq
B^{\prime}$. Therefore,
$\Gamma_{V^{\prime}}(B^{\prime})\leq|D^{\prime}\setminus\\{u\\}|=\Gamma_{V}(B)-1$.

The construction and correctness of the algorithm is based on Lemma 2.1 and
Lemma 2.2. In each iteration, the algorithm finds a subtree $T_{u}$ of height
exactly $k$, adds $u$ to $D$, and removes all the leaves of $T_{r}$ that are
in ${{\cal{N}}}_{k}(u)$. To implement the algorithm in $O(n)$ time, we use a
modified version of the depth first search ($DFS$) algorithm (see Algorithm
2). In each recursive call _ModifiedDFS_ $(u)$, we check whether $h(T_{u})=k$.
If so, we add $u$ to $D$, remove all vertices of $T_{u}$ from $T_{r}$ (since
they are already dominated by $u$), and return $\delta_{D}(u)=0$. Otherwise,
we check whether at least one descendant $v$ of $u$ is added to $D$ and
$d_{T}(u,v)+h(T_{u})\leq k$. If so, we remove all vertices of $T_{u}$ from
$T_{r}$ and return $\delta_{D}(u)=\min\\{\delta_{D}(u),d_{T}(u,v)\\}$.
Otherwise, we check again whether $h(T_{u})=k$ (in case the descendants
reduced the height of $u$ to $k$). If so, we add $u$ to $D$, remove all
vertices of $T_{u}$ from $T_{r}$, and return $\delta_{D}(u)=0$. Otherwise
($h(T_{u})<k$), we return $\infty$.

Algorithm 1 _Solve-kHDS-on-Tree_($T_{r}$)

Input: A tree $T_{r}$ rooted at $r$
Output: A minimum $k$-hop dominating set of $T_{r}$, $k$-$Dom_{V}(V)$

1: $D\leftarrow\emptyset$

2: for each $u\in V$ do compute $h(T_{u})$ $\delta_{D}(u)\leftarrow\infty$

3: $\delta_{D}(r)\leftarrow$ _ModifiedDFS_ $(r)$

4: if $\delta_{D}(r)=\infty$ then $D\leftarrow D\cup\\{r\\}$

5: return $D$

Procedure 2 _ModifiedDFS_($u$)

1: if $h(T_{u})=k$ then $D\leftarrow D\cup\\{u\\}$ $T_{r}\leftarrow
T_{r}\setminus T_{u}$ $h(T_{u})\leftarrow-1$ $\delta_{D}(u)\leftarrow 0$

2: else for each $v\in child(u)$ do if $h(T_{v})\geq k$ then
$\delta_{D}(u)\leftarrow\min\\{\delta_{D}(u),ModifiedDFS(v)+1\\}$
$h(T_{u})\leftarrow\max\\{h(T_{v})+1\ :\ v\in child(u)\\}$ (* updating
$h(T_{u})$ *) if $h(T_{u})+\delta_{D}(u)\leq k$ then $T_{r}\leftarrow
T_{r}\setminus T_{u}$ $h(T_{u})\leftarrow-1$ if $h(T_{u})=k$ then $D\leftarrow
D\cup\\{u\\}$ $T_{r}\leftarrow T_{r}\setminus T_{u}$ $h(T_{u})\leftarrow-1$
$\delta_{D}(u)\leftarrow 0$ else $\delta_{D}(u)\leftarrow\infty$

3: return $\delta_{D}(u)$

Example: Consider the tree $T_{r}$ rooted at $r=1$ and $k=2$; see Figure 1.
The first vertex added to $D$ is $7$ in _ModifiedDFS_ $(7)$, since
$h(T_{7})=2$. In this call, we remove $T_{7}$ from $T_{r}$, update
$h(T_{7})=-1$ and return $\delta_{D}(7)=0$ to _ModifiedDFS_ $(4)$. In
_ModifiedDFS_ $(4)$, we update $\delta_{D}(4)=1$ and, after traversing
vertices 6 and 8, $h(T_{4})=1$, and since $h(T_{4})+\delta_{D}(4)=2$, we
remove $T_{4}$ from $T_{r}$ and return $\delta_{D}(4)=1$ to _ModifiedDFS_
$(2)$. In _ModifiedDFS_ $(2)$, since $h(T_{2})=3>k$, we call _ModifiedDFS_
$(5)$ which adds vertex $5$ to $D$, removes $T_{5}$ from $T_{r}$, and returns
$\delta_{D}(5)=0$. Then, we update $\delta_{D}(2)=1$ and $h(T_{2})=0$, and
since $h(T_{2})+\delta_{D}(2)=1<k$, we remove $T_{2}$ from $T_{r}$ and return
$\delta_{D}(2)=1$ to _ModifiedDFS_ $(1)$. In _ModifiedDFS_ $(1)$, since
$\delta_{D}(1)=2$ and, after traversing vertex 3, $h(T_{1})=1$, we return
$\delta_{D}(1)=\infty$, and therefore, we add vertex $1$ to $D$ as well.

Figure 1: A tree $T_{r}$ rooted at $r=1$. For $k=2$, Algorithm 1 returns
$D=\\{1,5,7\\}$.

######  Theorem 2.4.

Let $T$ be a tree on $n$ vertices. Then, for any integer $k\geq 1$, one can
find a minimum $k$-hop dominating set of $T$ in $O(n)$ time.

###  2.2 Quadratic-time algorithm for unicyclic graphs

In this section, we present a simple $O(n^{2})$-time algorithm that solves
_kHDS_ on unicyclic graphs (in Section 4, we will improve the running time to
$O(n)$). In [16], Kundu and Majumder proved the following theorem.

######  Theorem 2.5 ([16]).

For each optimal $k$-hop dominating set $D$ of a connected graph $G$, there
exists a spanning tree $T$ of $G$, such that $D$ is also an optimal $k$-hop
dominating set of $T$.

Let $G$ be a unicyclic graph on $n$ vertices and let $C$ be the cycle of $G$.
Since there is only one cycle in $G$, there are at most $n$ spanning trees of
$G$. For each spanning tree $T$ of $G$, we find a $k$-hop dominating set of
$T$ in $O(n)$ time, using Algorithm 1. Therefore, we can find a $k$-hop
dominating set of $G$ in $O(n^{2})$ time. The correctness of the algorithm
follows immediately from Theorem 2.5.

######  Theorem 2.6.

Let $G$ be a unicyclic graph on $n$ vertices. Then, for any $k\geq 1$, one can
find a minimum $k$-hop dominating set of $G$ in $O(n^{2})$ time.

###  2.3 Piercing segments on a line

Let ${{\cal{A}}}=\\{a_{1},a_{2},\dots,a_{n}\\}$ be a set of $n$ segments on a
horizontal line $\ell$. For each $a_{i}\in A$, let $s_{i},e_{i}$ be the
starting and the ending points of $a_{i}$, respectively, such that
$s_{i}<e_{i}$. A set ${{\cal{P}}}$ of points on $\ell$ is a piercing set of
${{\cal{A}}}$ if for every segment $a_{i}\in{{\cal{A}}}$,
$a_{i}\cap{{\cal{P}}}\neq\emptyset$, that is, for each $a_{i}\in{{\cal{A}}}$,
there is a point $p\in{{\cal{P}}}$, such that $s_{i}\leq p\leq e_{i}$.
Assuming $e_{i}<e_{j}$, for each $1\leq i<j\leq n$, a minimum piercing set of
${{\cal{A}}}$ can be greedily computed in $O(n)$ time.

######  Theorem 2.7.

Let ${{\cal{A}}}=\\{a_{1},a_{2},\dots,a_{n}\\}$ be a set of $n$ segments on a
horizontal line, such that $e_{i}<e_{j}$, for each $1\leq i<j\leq n$. Then,
one can find a minimum piercing set of ${{\cal{A}}}$ in $O(n)$ time.

##  3 Piercing Circular Arcs

Let
${{\cal{A}}}=\\{a_{1}=[s_{1},e_{1}],a_{2}=[s_{2},e_{2}],\dots,a_{n}=[s_{n},e_{n}]\\}$
be a set of $n$ circular arcs located on a circle $C$. A set ${{\cal{P}}}$ of
points on $C$ is a _piercing set_ for ${{\cal{A}}}$ if, for every arc
$a_{i}\in{{\cal{A}}}$, $a_{i}\cap{{\cal{P}}}\neq\emptyset$. After sorting the
endpoints of the arcs by their polar angle, Katz et al. [15] showed that a
minimum piercing set of ${{\cal{A}}}$ can be computed in $O(n\log{n})$ time,
using a dynamic data structure that supports insertions and deletions to/from
${{\cal{A}}}$. In this section, we present a linear-time algorithm for this
problem.

We assume that no arc $a_{i}$ is contained in another arc $a_{j}$, otherwise,
we remove $a_{j}$ from ${{\cal{A}}}$, since any point that pierces $a_{i}$
also pierces $a_{j}$. Let $S=\\{s_{1},s_{2},\dots,s_{n}\\}$ and
$F=\\{e_{1},e_{2},\dots,e_{n}\\}$ be the sets of the starting and the ending
points of the arcs of ${{\cal{A}}}$, respectively. Let $\mu=s_{1}$ and let
$p_{1},p_{2},\dots,p_{2n}$ be the points of $X=S\cup F$ ordered in clockwise
order with respect to $p_{1}=\mu$. For simplicity of presentation, we say that
$p_{1}\leq p_{2}\leq\dots\leq p_{2n}$; see Figure 2.

Figure 2: The arcs of ${{\cal{A}}}$.
$X_{1}=\\{p_{1},p_{2},p_{3},p_{4},p_{5},p_{6}\\}$. ${{\cal{P}}}_{\mu}(p_{4})$
consists of the red points.

######  Observation 3.1.

There exists a minimum piercing set of ${{\cal{A}}}$ that contains only points
from the set $F$.

######  Proof 3.2.

Let $P$ be a minimum piercing set of ${{\cal{A}}}$. If $P$ contains a point
$p\notin F$, then we can replace $p$ by the point $q=\min\\{e_{i}\in F\ :\
e_{i}>p\\}$, and obtain a set $P\cup\\{q\\}\setminus\\{p\\}$ which is also a
minimum piercing set of ${{\cal{A}}}$.

Let $X_{1}=X\cap a_{1}$. Let ${{\cal{P}}}$ be a minimum piercing set of
${{\cal{A}}}$, and notice that ${{\cal{P}}}$ must contain at least one point
from $X_{1}$. Let $p_{j}\in{{\cal{P}}}\cap X_{1}$. Then, by removing all the
arcs that are pierced by $p_{j}$ and considering the remaining arcs as a set
of segments on a line, we can find a minimum piercing set of ${{\cal{A}}}$ in
$O(n)$ time, using Theorem 2.7. Therefore, we can find a minimum piercing set
of ${{\cal{A}}}$ in $O(|X_{1}|\cdot n)$ time. In the following we show how to
implement this algorithm in $O(n)$ time, regardless of the size of $X_{1}$.

For each point $p_{i}\in X$, let ${{\cal{A}}}_{i}=\\{a_{j}\in{{\cal{A}}}\ :\
p_{i}\text{ pierces }a_{j}\\}$ and let $next(p_{i})$ be the point $e_{j}\in
F$, such that $s_{j}>p_{i}$ and $e_{j}\leq e_{k}$, for each
$a_{k}\in{{\cal{A}}}\setminus{{\cal{A}}}_{i}$; see Figure 2. That is, $e_{j}$
is the ending point of the first arc in ${{\cal{A}}}\setminus{{\cal{A}}}_{i}$
that appears after $p_{i}$ (in clockwise order).

#### Step 1

For each $p_{i}\in X$, we compute $next(p_{i})$ using Algorithm 3.

Procedure 3 _Compute-next_($X$, $S$, $F$)

Input: A set ${{\cal{A}}}$ of arcs sorted in clockwise order by their ending
points
Output: $next(p_{i})$, for each point $p_{i}\in X$

$i\leftarrow 1$

$j\leftarrow 2$

while $i<2n$ do if $p_{j}=s_{k}\in S$ then $next(p_{i})\leftarrow e_{k}$ $i++$
else $j\leftarrow(j+1)\mod 2n$

#### Step 2

For a point $p\in X$ and an integer $i>1$, let $next^{i}(p)$ be
$next(next^{i-1}(p))$; see Figure 2. For two points $p,q\in X$, let
${{\cal{P}}}_{q}(p)=\\{p,next(p),next^{2}(p),\dots,next^{k}(p)\\}$, such that
$next^{k-1}(p)<q\leq next^{k}(p)$. The following observation follows from the
fact that there exists a point $p\in X_{1}$, such that ${{\cal{P}}}_{p}(p)$ is
a minimum piercing set of ${{\cal{A}}}$.

######  Observation 3.3.

A minimum piercing set of ${{\cal{A}}}$ can be computed by taking the minimum
over the sets ${{\cal{P}}}_{p}(p)$, for all $p\in X_{1}$.

To this end, we construct a directed graph $G=(X,E)$, such that
$E=\\{(p,next(p))\ :\ p\in X\\}$. Notice that $|E|=|X|$. Recall that
$\mu=s_{1}$ (the starting point of arc $a_{1}$). For each point $p\in X_{1}$,
we compute ${{\cal{P}}}_{\mu}(p)$ recursively using Algorithm 4.

Procedure 4 _ComputeAll_($G=(X,E)$, $\mu$)

Input: A Directed graph $G=(X,E)$ and a reference point $\mu$
Output: $P_{\mu}(p)$, for each $p\in X_{1}$

1: for each $p\in X$ do ${{\cal{P}}}_{\mu}(p)\leftarrow\emptyset$

2: for each $p\in X_{1}$ do ${{\cal{P}}}_{\mu}(p)\leftarrow$ _RecCompute_($p$,
$\mu$)

zzzzzzZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
Procedure _RecCopmute_ $(p,\mu)$ zzzzzzzzZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ

1: if ${{\cal{P}}}_{\mu}(p)\neq\emptyset$ then return ${{\cal{P}}}_{\mu}(p)$

2: if $next(p)\geq\mu$ then ${{\cal{P}}}_{\mu}(p)\leftarrow\\{p\\}$ else
${{\cal{P}}}_{\mu}(p)\leftarrow\\{p\\}\ \cup$ _RecCompute_($next(p)$, $\mu$)

3: return ${{\cal{P}}}_{\mu}(p)$

For each set ${{\cal{P}}}_{\mu}(p)$, let $lastNext(p)$ be the last point in
${{\cal{P}}}_{\mu}(p)$. We check whether $next(lastNext(p))<p$, which means
that the arc ending at $next(lastNext(p))$ is not pierced by
${{\cal{P}}}_{\mu}(p)$. If so, we add $next(lastNext(p))$ to
${{\cal{P}}}_{\mu}(p)$. Finally, we return the set ${{\cal{P}}}_{\mu}(p)$ of
minimum cardinality. Let ${{\cal{P}}}$ be the set returned by the algorithm.
Thus, by Observation 3.1 and Observation 3.3, ${{\cal{P}}}$ is a minimum
piercing set of ${{\cal{A}}}$. In the following lemma, we bound the running
time of our algorithm.

######  Lemma 3.4.

Computing ${{\cal{P}}}$ takes $O(n)$ time.

######  Proof 3.5.

It is not hard to see that computing $next(p)$, for each $p\in X$, using
Algorithm 3, takes $O(n)$ time. Since each vertex in $G$ has exactly one out-
going edge, the number of edges of $G$ is $2n$, and thus, constructing $G$
takes $O(n)$. Moreover, computing ${{\cal{P}}}_{\mu}(p)$, for all $p\in
X_{1}$, takes $O(n)$, since we traverse each edge in $G$ exactly once during
all the calls to Algorithm 4. Therefore, the running time of the algorithm is
$O(n)$.

The following theorem concludes the result of this section.

######  Theorem 3.6.

Let ${{\cal{A}}}=\\{a_{1},a_{2},\dots,a_{n}\\}$ be a set of $n$ circular arcs
sorted in clockwise order. Then, one can find a minimum piercing set of
${{\cal{A}}}$ in $O(n)$ time.

###  3.1 Piercing circular arcs with additional requirements

In this section, we show how to solve two variants of the piercing circular
arcs problem, while the first variant is interesting by itself, the second is
presented here for future use, since it is needed in Section 5. In both
variants the modifications performed on the algorithm do not affect the
running time, and thus it stays linear.

##### Variant-1: Piercing circular arcs with respect to a point $\rho$

Let $\rho$ be a point in $X$. Given a set $P\subseteq X$, let
$\delta_{P}(\rho)$ be the number of points in $X$ between $\rho$ and the
closest point of $P$. In this variant, we consider the piercing circular arcs
problem with an additional requirement. That is, in addition to the set
${{\cal{A}}}$, we are given a point $\rho\in X$, and the goal is to find a
minimum piercing set ${{\cal{P}}}$ for ${{\cal{A}}}$, such that
$\delta_{{{\cal{P}}}}(\rho)\leq\delta_{{{\cal{P}}}^{\prime}}(\rho)$, for every
minimum piercing set ${{\cal{P}}}^{\prime}$ for ${{\cal{A}}}$.

Assume w.l.o.g., that $\rho\in a_{1}$. We perform the previous algorithm with
the following modification. When we obtain a minimum piercing set
${{\cal{P}}}$, we check the distance of the first and the last selected points
of ${{\cal{P}}}$ from $\rho$, and return the minimum piercing set
${{\cal{P}}}$ that minimizes this distance.

By the correctness of the previous algorithm, ${{\cal{P}}}$ is a minimum
piercing set for ${{\cal{A}}}$, and, by the modification,
$\delta_{{{\cal{P}}}}(\rho)\leq\delta_{{{\cal{P}}}^{\prime}}(\rho)$, for every
minimum piercing set ${{\cal{P}}}^{\prime}$ for ${{\cal{A}}}$.

##### Variant-2: Piercing circular arcs with respect to a point $\rho$ and a
positive integer $k$

Let $\rho$ be a point in $X$ and let $k$ be an integer. For each $1\leq i<k$,
let $B_{i}=\\{a_{j}=[s_{j},e_{j}]\in{{\cal{A}}}:\
\delta_{\\{s_{j}\\}}(\rho)\geq i\ \wedge\ \delta_{\\{e_{j}\\}}(\rho)\geq
i\\}$; see Figure 3. Let ${{\cal{P}}}$ be a minimum piercing set for
${{\cal{A}}}$, and let $m$ be its size (i.e., $m=|{{\cal{P}}}|$). In this
variant, in addition to the set ${{\cal{A}}}$, we are given a point $\rho\in
X$ and an integer $k>1$, and the goal is to find the largest integer $1\leq
i<k$ and a piercing set ${{\cal{P}}}^{\prime}$ for ${{\cal{A}}}\setminus
B_{i}$, such that $|{{\cal{P}}}^{\prime}|=m-1$, if such a set exists.

Figure 3: $B_{1}$ consists of the blue arcs. $X^{+}$ consists of the red
points. A piercing set ${{\cal{P}}}^{\prime}$ for ${{\cal{A}}}\setminus
B_{i}$, for $i=2$, consists of the purple points.

Let ${{\cal{A}}}^{-}={{\cal{A}}}\setminus B_{1}$ and let $X^{+}=\\{x\in
X:\rho<x\leq next(\rho)\\}$; see Figure 3. We perform the previous algorithm
with the following modifications. Instead of going over the points of $X_{1}$
(in clockwise order), we go over the points of $X^{+}$ in sorted order of
distance from $\rho$. Moreover, instead of requiring to pierce all the arcs in
${{\cal{A}}}$, we require to pierce only ${{\cal{A}}}^{-}$.

For each piercing set ${{\cal{P}}}^{\prime}_{q}$ for ${{\cal{A}}}^{-}$ of size
$m-1$, that starts with a point $q\in X^{+}$, we check what is the largest
$i$, such that $B_{1}\setminus A_{{{\cal{P}}}^{\prime}_{q}}=B_{i}\setminus
A_{{{\cal{P}}}^{\prime}_{q}}$, where
$A_{{{\cal{P}}}^{\prime}_{q}}=\\{a\in{{\cal{A}}}:\ a\ \text{is pierced by a
point from }{{\cal{P}}}^{\prime}_{q}\\}$. We return the set
${{\cal{P}}}^{\prime}_{q}$ of size $m-1$ with the largest $i$.

######  Claim 1.

The above algorithm finds the largest integer $1\leq i<k$ and a piercing set
${{\cal{P}}}^{\prime}$ for ${{\cal{A}}}\setminus B_{i}$, such that
$|{{\cal{P}}}^{\prime}|=m-1$, if such a set exists.

######  Proof 3.7.

Assume such a piercing set exists, and let ${{\cal{P}}}_{opt}$ be this
piercing set. Let $q_{opt}$ be the starting point in ${{\cal{P}}}_{opt}$
(i.e., the closest point in ${{\cal{P}}}_{opt}$ to $\rho$ in clockwise order).
Clearly, $q_{opt}\in X^{+}$, otherwise, there is an arc in
${{\cal{A}}}\setminus B_{1}$ that is not pierced by ${{\cal{P}}}_{opt}$. Thus,
we are done, since we consider such a solution that starts with $q_{opt}$.

##  4 Solving _kHDS_ on Unicyclic Graphs

In this section, we present a linear-time algorithm that computes a minimum
$k$-hop dominating set in unicyclic graphs.

Let $G=(V,E)$ be a unicyclic graph on $n$ vertices and let $C$ be the cycle of
$G$. Let $r_{1},r_{2},\dots,r_{m}$ be the vertices of $C$ ordered in clockwise
order with an arbitrary first point $r_{1}$. Since $G$ is a unicyclic graph,
each $r_{i}\in C$ is a root of a tree $T_{i}$. Our algorithm computes a
$k$-hop dominating set $D^{*}$ of $G$ in three steps.

#### Step 1

For each tree $T_{i}$ rooted at $r_{i}$, we compute a $k$-hop dominating set
$D_{i}$ using Algorithm 1. For each $1\leq i\leq m$, let
$\delta_{D_{i}}(r_{i})$ and $h(T_{i})$ be the distance of $r_{i}$ from $D_{i}$
and the height of $T_{i}$ that are computed at the end of Algorithm 1,
respectively.

  * •

If $r_{i}\notin D_{i}$, then $1\leq\delta_{D_{i}}(r_{i})\leq k$ and
$h(T_{i})=-1$.

  * •

If $r_{i}\in D_{i}$, then either $r_{i}$ was added in Algorithm 2 or in
Algorithm 1 (Line 4). If $r_{i}$ was added in Algorithm 2 (when $h(T_{i})=k$),
then $\delta_{D_{i}}(r_{i})=0$. Otherwise, $r_{i}$ was added in Algorithm 1
(Line 4, when $0\leq h(T_{i})<k$), then we remove $r_{i}$ from $D_{i}$ and
$\delta_{D_{i}}(r_{i})=\infty$.

#### Step 2

Let $D=\bigcup_{1\leq i\leq m}D_{i}$. In this step, we consider the roots
$r_{i}\in C$ having $\delta_{D}(r_{i})<k$ in non-decreasing order of
$\delta_{D}(r_{i})$. For each $r_{i}$, we consider its neighbors $r_{i-1}$ and
$r_{i+1}$. If $\delta_{D}(r_{i-1})>\delta_{D}(r_{i})+1$ and
$h(T_{i-1})+\delta_{D}(r_{i})+1\leq k$, then we set
$\delta_{D}(r_{i-1})=\delta_{D}(r_{i})+1$ and update the location of $r_{i-1}$
in the non-decreasing order according to its new $\delta_{D}(r_{i-1})$ value.
Similarly, if $\delta_{D}(r_{i+1})>\delta_{D}(r_{i})+1$ and
$h(T_{i+1})+\delta_{D}(r_{i})+1\leq k$, then we set
$\delta_{D}(r_{i+1})=\delta_{D}(r_{i})+1$ and update the location of $r_{i+1}$
in the non-decreasing order according to its new $\delta_{D}(r_{i+1})$ value.

#### Step 3

Let $B=\\{u\in C:\delta_{D}(u)=\infty\\}$. Recall that a partial $k$-hop
dominating set of $B$, denoted by $k$-$Dom_{C}(B)$, is a subset $D^{\prime}$
of $C$, such that $B\subseteq{{\cal{N}}}_{k}(D^{\prime})$. In this step, we
compute a minimum $k$-$Dom_{C}(B^{+})$ by a reduction to the problem of
piercing circular arcs (Section 3), where $B^{+}$ is the set containing the
vertices of $B$ with their tag along trees. Notice that, each $r_{i}\in B$ has
$0\leq h(T_{i})<k$. For each $r_{i}\in B$, let $m_{i}=k-h(T_{i})$. We produce
a circular arc $a_{i}\subseteq C$ containing the vertices
$\\{r_{i-m_{i}},r_{i-m_{i}+1},\dots,r_{i},r_{i+1},\dots,r_{i+m_{i}}\\}$ of
$C$, where each of them dominates the vertices of $T_{i}$; see Figure 4. Let
${{\cal{A}}}$ be the set of the produced arcs. Therefore, to compute a minimum
$k$-$Dom_{C}(B^{+})$, it is sufficient to compute a minimum piercing set of
${{\cal{A}}}$. We compute a minimum piercing set ${{\cal{P}}}$ of
${{\cal{A}}}$, using Theorem 3.6. At the end of this step, we return the set
$D^{*}=D\cup{{\cal{P}}}$.

Figure 4: The arcs produced in Step 3, for $k=5$.

######  Lemma 4.1.

$D^{*}$ is a minimum $k$-hop dominating set of $G$.

######  Proof 4.2.

After applying Step 1, each $D_{i}$ is a minimum $k$-hop dominating set of
$T_{i}$. Observe that each vertex added to $D_{i}$ (in Algorithm 1) is as
close to the root $r_{i}$ as possible. Therefore, among all the minimum
$k$-hop dominating sets of $T_{i}$, $D_{i}$ is the one that minimizes
$\delta_{D_{i}}(r_{i})$. Moreover, if $r_{i}\in D_{i}$ and $r_{i}$ was added
in Algorithm 1 (Line 4), then $r_{i}$ does not have to be in $D^{*}$, since
$0\leq h(T_{i})<k$ and $T_{i}$ can be dominated by vertices of $G\setminus
T_{i}$ of distance $k-h(T_{i})$ from $r_{i}$. In this case,
$\delta_{D_{i}}(r_{i})=\infty$ and we remove $r_{i}$ from $D_{i}$ at the end
of Step 1.

In Step 2, we update the distances of the vertices in ${{\cal{N}}}_{k}(D)$,
where $D=\bigcup_{1\leq i\leq m}D_{i}$. If $\delta_{D}(r_{i})$ has been
updated in Step 2, then all the vertices of $T_{i}$ are dominated by $D$. Let
$T=\bigcup_{r_{i}\in B}T_{i}$ be the set of the subtrees that are not
dominated yet. At this point, $D$ is a minimum $k$-hop dominating set of
$G\setminus T$, such that the vertices of $D$ are as close to the vertices of
$B$ as possible among all minimum $k$-hop dominating sets of $G\setminus T$.
Thus, it remains to select a minimum subset of $C$ that dominates the vertices
of $T$. By the construction of the arcs in Step 3, each vertex in arc $a_{i}$
dominates the vertices of $T_{i}$. Hence, the minimum piercing set
${{\cal{P}}}$ that is computed in Step 3 is a minimum $k$-hop dominating set
of $T$. Therefore, $D^{*}=D\cup{{\cal{P}}}$ is a minimum $k$-hop dominating
set of $G$.

######  Lemma 4.3.

Computing $D^{*}$ takes $O(n)$ time.

######  Proof 4.4.

Step 1 takes linear time (by Theorem 2.4). We implement Step 2 in linear time
as follows. We maintain $k+1$ lists $L_{0},L_{1},\dots,L_{k-1}$, and
$L_{\infty}$, such that $r_{i}\in L_{j}$ if and only if $\delta_{D}(r_{i})=j$.
We go over the vertices in the lists $L_{0},L_{1},\dots,L_{k-1}$ in the
following way. We consider a vertex $u\in L_{i}$ before a vertex $v\in L_{j}$
if $i<j$. Moreover, when a vertex $u\in L_{i}$ updates $\delta_{D}(v)$ of a
vertex $v$ to $i+1$, we move $v$ from its current list to $L_{i+1}$.

In Step 3, the arcs in ${{\cal{A}}}$ are created in sorted order in clockwise
order in linear time, since the vertices of the cycle $C$ are sorted in
clockwise order. Thus, by Theorem 3.6, computing a minimum piercing set of
${{\cal{A}}}$ takes $O(|{{\cal{A}}}|)$ time, where $|{{\cal{A}}}|\leq|C|\leq
n$. Therefore, $D^{*}$ can be computed in $O(n)$ time.

The following theorem follows from Lemma 4.1 and Lemma 4.3.

######  Theorem 4.5.

Let $G$ be a unicyclic graph on $n$ vertices. Then, for any $k\geq 1$, one can
find a minimum $k$-hop dominating set of $G$ in $O(n)$ time.

###  4.1 _kHDS_ on unicyclic graphs with additional requirements

In this section, we consider two variants of the _kHDS_ problem on unicyclic
graphs. In these variants, in addition to a unicyclic graph $G$, we are given
a point $\rho\in C$, where $C$ is the cycle of $G$. In both variants, we apply
the _kHDS_ algorithm on unicyclic graphs (Section 4) with modifications that
do not affect its running time.

##### Variant-1

In this variant, the goal is to compute a minimum $k$-hop dominating set
$D^{*}$ of $G$, that minimizes $\delta_{D^{*}}(\rho)$, among all minimum
$k$-hop dominating sets of $G$. We apply Steps 1-3 in our algorithm, except
that in Step 3, we do not create an arc for $\rho$. Moreover, instead of
calling the algorithm of piercing circular arcs (Section 3), we call the
algorithm that solves Variant-1 of piercing circular arcs with additional
requirements (Section 3.1).

The correctness of this algorithm follows immediately from Theorem 4.5 and
from the correctness of Variant-1 of piercing circular arcs with additional
requirements (Section 3.1).

##### Variant-2

Let $D^{*}$ be a minimum $k$-hop dominating set of $G$ and let $m$ be its
size. In this variant, the goal is to compute a $k$-hop dominating set $D$ of
$G\setminus{{\cal{N}}}_{k}(\rho)$ of size $m-1$, such that the distance from
$\rho$ to the farthest vertex in $G\setminus{{\cal{N}}}_{k}(D)$ is minimized.
If there is no $k$-dominating set for $G\setminus{{\cal{N}}}_{k}(\rho)$ of
size $m-1$, then return $D^{*}$. We apply Steps 1-3 in our algorithm, except
that, in Step 3, we do not create an arc for $\rho$. Moreover, instead of
calling the algorithm of piercing circular arcs (Section 3), we call the
algorithm that solves Variant-2 of piercing circular arcs with additional
requirements (Section 3.1).

The correctness of this algorithm follows immediately from Theorem 4.5 and
from the correctness of Variant-2 of piercing circular arcs with additional
requirements (Section 3.1).

##  5 Solving _kHDS_ on Cactus Graphs

In this section, we present a linear-time algorithm that computes a minimum
$k$-hop dominating set in cactus graphs.

Let $G$ be a cactus graph on $n$ vertices and let
$C=\\{r_{1},r_{2},\dots,r_{m}\\}$ be a cycle in $G$. For each $1\leq i\leq m$,
let $G_{r_{i}}$ be the subgraph of $G$ containing $r_{i}$ and obtained by
removing the edges $(r_{i-1},r_{i})$ and $(r_{i},r_{i+1})$ from $G$. In
Algorithm 5, we first compute a minimum $k$-hop dominating set $D_{i}$ for
each $G_{r_{i}}$, such $\delta_{D_{i}}(r_{i})$ is minimized, among all minimum
$k$-hop dominating sets for $G_{r_{i}}$. Then, we compute a minimum $k$-hop
dominating set $D$ of the remaining (unicyclic) graph by applying the _kHDS_
algorithm that solves the problem in unicyclic graph (Section 4), and we
return $D^{*}=\bigcup_{i}D_{i}\cup D$.

Algorithm 5 _Solve-kHDS-on-Cactus_($G$, $C$)

Input: A cactus graph $G$ and a cycle $C$ in it
Output: A minimum $k$-hop dominating set $D^{*}$ for $G$

1: for each $r_{i}\in C$ do $L_{i}\leftarrow$ _DFS-Based_($G_{r_{i}},r_{i}$)
$D_{i}\leftarrow\emptyset$

2: for each $r_{i}\in C$ do if $L_{i}=\emptyset$ then (* $G_{r_{i}}$ is a
tree*) $D_{i}\leftarrow$ _Solve-kHDS-on-Tree_ $(G_{r_{i}})$ (* Algorithm 1,
with $r_{i}$ as the root of $G_{r_{i}}$ *) else for each $\rho\in L_{i}$ do (*
Consider the vertices in sorted order *) $G_{\rho}\leftarrow$ the subgarph of
$G_{r_{i}}$ obtained by removing the edge $(\rho,\rho.\pi)$ and contains
$\rho$ $D_{i}\leftarrow\ D_{i}\ \cup$ _Solve-Special-kHDS-on-Unicycle_
$(G_{\rho},\rho)$

3: $D^{*}\leftarrow\ \bigcup_{i}D_{i}$

4: $D\leftarrow$ call solving _kHDS_ on unicyclic graphs with the updated
graph $G$ (Section 4)

5: $D^{*}\leftarrow D^{*}\cup D$

6: return $D^{*}$

Given a vertex $r_{i}\in C$, we compute a minimum $k$-hop dominating set
$D_{i}$ for $G_{r_{i}}$ as follows. If $G_{r_{i}}$ is a tree, then we compute
$D_{i}$ using Algorithm 1 (Section 2.1). Otherwise, $G_{r_{i}}$ contains a
cycle. We perform a DFS-based scan (Algorithm 7) on $G_{r_{i}}$ that starts
from $r_{i}$ and finds all the cycles of $G_{r_{i}}$. That is, every back-edge
to a vertex $u$, found in the DFS-based algorithm, corresponds to a cycle
containing $u$ as its representative. We create an ordered list $L_{i}$ of all
the vertices having back-edges in $G_{r_{i}}$, such that vertex $u$ appears
before vertex $v$ in $L_{i}$, if and only if the finishing time of $u$ in the
DFS-base algorithm is less than the finishing time of vertex $v$.

For a vertex $u\in L_{i}$, let $G_{u}$ be the subgraph of $G_{r_{i}}$
containing $u$ and obtained by removing the edge $(u,u.\pi)$ from $G_{r_{i}}$.
For each vertex $\rho\in L_{i}$ (in sorted order), we compute a (nearly)
minimum $k$-hop dominating set for $G_{\rho}$ (using Algorithm 6) as follows.
Let ${{\cal{C}}}$ be the set of cycles of $G_{\rho}$ obtained by the back-
edges to vertex $\rho$ in the DFS-Based algorithm. For each cycle
$C\in{{\cal{C}}}$, let $C^{+}$ be the unicyclic graph corresponding to $C$. We
first compute a minimum $k$-hop dominating set $D_{1}$ of $C^{+}$ that
minimizes $\delta_{D_{1}}(\rho)$, among all minimum $k$-hop dominating sets of
$C^{+}$ (using Variant-1 of solving _kHDS_ on unicyclic graphs with additional
requirements, Section 4.1). Then, we check whether there exists a $k$-hop
dominating set of $C^{+}\setminus{{\cal{N}}}_{k}(\rho)$ of size $|D_{1}|-1$.

  * •

If there exists such a set, then we compute a $k$-hop dominating $D_{2}$ set
of $C^{+}\setminus{{\cal{N}}}_{k}(\rho)$ of size $|D_{1}|-1$, such that the
distance from $\rho$ to the farthest vertex in
$C^{+}\setminus{{\cal{N}}}_{k}(D_{2})$ is minimized (using Variant-2 of
solving _kHDS_ on unicyclic graphs with additional requirements, Section 4.1).
Let $u$ be the farthest vertex from $\rho$ in
$C^{+}\setminus{{\cal{N}}}_{k}(D_{2})$. We replace $C^{+}$ in $G$ by the path
from $\rho$ to $u$, and we add $D_{2}$ to $D_{i}$.

  * •

Otherwise, let $i=\delta_{D_{1}}(\rho)$ and let $u$ be a vertex in $D_{1}$ of
distance $i$ from $\rho$. We replace $C^{+}$ in $G$ by the path from $\rho$ to
$u$ and a new path of length $k$ incident to $u$; see Figure 5. Moreover, we
add $D_{1}\setminus\\{u\\}$ to $D_{i}$.

Figure 5: Left, a unicyclic graph $C^{+}$ in which there is no $4$-dominating
set for $C^{+}\setminus{{\cal{N}}}_{4}(\rho)$ of size $m-1$ (where $m=3$). The
vertices of the $4$-dominating set are depicted in red. Right, we replace
$C^{+}$ in $G$ by the path from $\rho$ to $u$ and a new path of length $4$
attached to $u$, depicted in blue.  Procedure 6 _Solve-Special-kHDS-on-
Unicycle_($G_{\rho},\rho$)

Input: A graph $G_{\rho}$ and a point $\rho\in G_{\rho}$
Output: A (nearly) $k$-hop dominating set for $G_{\rho}$

1: ${{\cal{C}}}\leftarrow$ the set of cycles of $G_{\rho}$ obtained by the
back-edges in DFS-Based algorithm for each $C\in{{\cal{C}}}$ do
$C^{+}\leftarrow$ the unicyclic graph corresponding to $C$ $D_{1}\leftarrow$
the $k$-hop dominating set computed by Variant-1 of solving _kHDS_ on
unicyclic graphs with additional requirements (Section 4.1) with $C^{+}$ and
$\rho$ $D_{2}\leftarrow$ the $k$-hop dominating set computed by Variant-2 of
solving _kHDS_ on unicyclic graphs with additional requirements (Section 4.1)
with $C^{+}$ and $\rho$ if $|D_{2}|=|D_{1}|-1$ then $u\leftarrow$ the farthest
vertex in $C^{+}\setminus{{\cal{N}}}_{k}(D_{2})$ replace $C^{+}$ in $G$ by the
path from $\rho$ to $u$ return $D_{2}$ else ($|D_{1}|=|D_{2}|$)
$i\leftarrow\delta_{D_{1}}(\rho)$ $u\leftarrow$ a vertex in $D_{1}$ of
distance $i$ from $\rho$ replace $C^{+}$ in $G$ by the path from $\rho$ to $u$
and a new path of length $k$ incident to $u$ $D_{1}\leftarrow
D_{1}\setminus\\{u\\}$ return $D_{1}$

Algorithm 7 _DFS-Based_($G=(V,E)$, $r$)

Input: A cactus graph $G$ and a source vertex $r$
Output: A list $L$ of vertices that have a back-edge sorted by their finishing
time
(the time they are colored black)

1: $L\leftarrow\emptyset$

2: for each $u\in V$ do $u.color\leftarrow\textsc{white}$
$u.\pi\leftarrow\textsc{null}$ $u.backEdge\leftarrow\textsc{false}$

3:  _DFS-visit_($G$, $r$, $L$)

4: return $L$

zzzzzzZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
Procedure _DFS-vist_ $(G,u,L)$ zzzzzzzzZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ

1: $u.color\leftarrow\textsc{gray}$

2: for each $v\in G.Adj[u]$ do (* $G.Adj[u]$ is the list of neighbors of $u$
*) if $v.color=\textsc{white}$ then $v.\pi\leftarrow u$ _DFS-visit_($G$, $v$,
$L$) else ($v.color=\textsc{gray}$) $v.backEdge\leftarrow\textsc{true}$

3: if $u.backEdge=\textsc{true}\ $ then add $u$ to the end of $L$

4: $u.color\leftarrow\textsc{{black}}$

######  Lemma 5.1.

$D^{*}$ is a minimum $k$-hop dominating set of $G$.

######  Proof 5.2.

The proof is by induction on the number of cycles in $G$. Let $c$ be the
number of cycles in $G$. To start the induction, if $c=0$, then, by Theorem
2.4, the lemma holds, and if $c=1$, then, by Theorem 4.5, the lemma holds.

Let $OPT$ be a minimum $k$-hop dominating set of $G$. Let $\rho$ be the first
vertex in list $L_{1}$, that is returned from Algorithm _DFS-based_ (Algorithm
7). Let $C$ be the first cycle considered by _Solve-Special-kHDS-on-
Unicycle_($G_{\rho},\rho$) (Algorithm 6), and let $C^{+}$ be the unicyclic
graph corresponding to $C$ in $G_{\rho}$. Let $OPT_{C^{+}}=OPT\cap C^{+}$, and
let $m_{opt}=|OPT_{C^{+}}|$. Let $D^{*}_{C^{+}}=D^{*}\cap C^{+}$, and let
$m_{D}=|D^{*}_{C^{+}}|$. From the correctness of Variant-1 and Variant-2 of
Section 4.1, we have $m_{D}\leq m_{opt}$. Therefore, from the optimality of
$OPT$, we have either $m_{D}=m_{opt}$ or $m_{D}=m_{opt}-1$. We distinguish
between the following cases:

  * •

$C^{+}\subseteq N_{k}(D^{*}_{C^{+}})$ and $m_{D}=m_{opt}$.
By the correctness of Variant-1 of Section 4.1, we have
$\delta_{D^{*}_{C^{+}}}(\rho)\leq\delta_{OPT_{C^{+}}}(\rho)$. Thus,
${{\cal{N}}}_{k}(OPT_{C^{+}})\subseteq{{\cal{N}}}_{k}(D^{*}_{C^{+}})$. Let $u$
be the closest vertex to $\rho$ in $D^{*}_{C^{+}}$. We remove $u$ from
$D^{*}_{C^{+}}$, and replace $C^{+}$ in $G$ by the path from $\rho$ to $u$ and
a new path of length $k$ incident to $u$. This procedure guaranties that $u$
will be selected again to $D^{*}$, and $G$ has one less cycle. Therefore, by
the induction hypothesis, the set $D^{*}\setminus D^{*}_{C^{+}}$ is a minimum
$k$-hop dominating set for the remaining graph
$G\setminus{{\cal{N}}}_{k}(D^{*}_{C^{+}})$.

  * •

$C^{+}\subseteq N_{k}(D^{*}_{C^{+}})$ and $m_{D}=m_{opt}-1$.
Let $u$ be the farthest vertex from $\rho$ in
$C^{+}\setminus{{\cal{N}}}_{k}(D^{*}_{C^{+}})$. Notice that any vertex not in
$C^{+}$ that $k$-dominates $u$ also $k$-dominates all vertices of
$C^{+}\setminus{{\cal{N}}}_{k}(D^{*}_{C^{+}})$. We replace $C^{+}$ in $G$ by
the path from $\rho$ to $u$. Thus, $G$ has one less cycle. By adding $\rho$ to
$D^{*}_{C^{+}}$, we have
${{\cal{N}}}_{k}(OPT_{C^{+}})\subseteq{{\cal{N}}}_{k}(D^{*}_{C^{+}})$.
Therefore, by the induction hypothesis, the set $D^{*}\setminus D^{*}_{C^{+}}$
is a minimum $k$-hop dominating set for the remaining graph
$G\setminus{{\cal{N}}}_{k}(D^{*}_{C^{+}})$.

  * •

$C^{+}\nsubseteq N_{k}(D^{*}_{C^{+}})$ and $m_{D}=m_{opt}$.
Let $u$ be the farthest vertex from $\rho$ in
$C^{+}\setminus{{\cal{N}}}_{k}(D^{*}_{C^{+}})$. Notice that any vertex not in
$C^{+}$ that $k$-dominates $u$ $k$-dominates all vertices of
$C^{+}\setminus{{\cal{N}}}_{k}(D^{*}_{C^{+}})$. We replace $C^{+}$ in $G$ by
the path from $\rho$ to $u$. Thus, $G$ has one less cycle. By the correctness
of Variant-2 of Section 4.1, $OPT$ also needs to select a vertex from $G$ of
distance at most $k$ from $u$. Therefore, by the induction hypothesis, the set
$D^{*}\setminus D^{*}_{C^{+}}$ is a minimum $k$-hop dominating set for the
remaining graph $G\setminus{{\cal{N}}}_{k}(D^{*}_{C^{+}})$.

  * •

$C^{+}\nsubseteq N_{k}(D^{*}_{C^{+}})$ and $m_{D}=m_{opt}-1$.
By the optimality of $OPT$, this case could not occur.

######  Lemma 5.3.

Computing $D^{*}$ takes $O(n)$ time.

######  Proof 5.4.

We show that each step in the algorithm takes linear time. Performing _DFS-
Based_ on $G_{r_{i}}$ takes $O(|G_{r_{i}}|)$ time, for each $r_{i}\in C$, and
$O(n)$ time in total. Computing a minimum $k$-hop dominating set in trees
takes linear time in the size of the tree, and $O(n)$ time in total. Computing
a minimum $k$-hop dominating set in unicyclic graphs takes linear time in the
size of the graph. Computing a minimum $k$-hop dominating set in Variant-1 and
Variant-2 of the $k$-hop dominating set in unicyclic graphs takes linear time
in the size of the graph, and $O(n)$ time in total.

The following theorem follows from Lemma 5.3 and Lemma 5.1:

######  Theorem 5.5.

Let $G$ be a cactus graph on $n$ vertices. Then, for any $k\geq 1$, one can
compute a minimum $k$-hop dominating set of $G$ in $O(n)$ time.

## References

  * [1] A. D. Amis, R. Prakash, D. Huynh, and T. Vuong.  Max-min D-cluster formation in wireless ad hoc networks.  In INFOCOM, pages 32–41, 2000.
  * [2] B. S. Baker.  Approximation algorithms for NP-complete problems on planar graphs.  Journal of the ACM, 41(1):153–180, 1994.
  * [3] S. C. Barman, M. Pal, and S. Mondal.  An optimal algorithm to find minimum $k$-hop dominating set of interval graphs.  Discrete Mathematics: Algorithms and Applications, 11(2), 2019.
  * [4] P. Basuchowdhuri and S. Majumder.  Finding influential nodes in social networks using minimum $k$-hop dominating set.  In ICAA, pages 137–151, 2014.
  * [5] H. S. Chao, F. R. Hsu, and R. C. T. Lee.  An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs.  Discrete Applied Mathematics, 102(3):159–173, 2000.
  * [6] E. J. Cockayne, S. E. Goodman, and S. T. Hedetniemi.  A linear algorithm for the domination number of a tree.  Information Processing Letters, 4(2):41–44, 1975.
  * [7] R. Davila, C. Fast, M. A. Henning, and F. Kenter.  Lower bounds on the distance domination number of a graph.  Contributions to Discrete Mathematics, 12(2):11–21, 2017.
  * [8] E. D. Demaine, F. V. Fomin, M. T. Hajiaghayi, and D. M. Thilikos.  Fixed-parameter algorithms for (_k_ , _r_)-center in planar graphs and map graphs.  ACM Transaction on Algorithms, 1(1):33–47, 2005.
  * [9] M. R. Garey and D. S. Johnson.  Computers and Intractability: A Guide to the Theory of NP-Completeness.  W. H. Freeman, San Francisco, 1979.
  * [10] A. Hansberg, D. Meierling, and L. Volkmann.  Distance domination and distance irredundance in graphs.  Electronic Journal of Combinatorics, 14(1):R35, 2007.
  * [11] S. T. Hedetniemi, R. C. Laskar, and J. Pfaff.  A linear algorithm for finding a minimum dominating set in a cactus.  Discrete Applied Mathematics, 13(2-3):287–292, 1986.
  * [12] M. A. Henning and N. Lichiardopol.  Distance domination in graphs with given minimum and maximum degree.  Journal of Combinatorial Optimization, 34(2):545–553, 2017.
  * [13] H. B. Hunt III, M. V. Marathe, V. Radhakrishnan, S. S. Ravi, D. J. Rosenkrantz, and R. E. Stearns.  NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs.  Journal of Algorithms, 26(2):238–274, 1998.
  * [14] D. S. Jhonson.  Approximation algorithms for combinatorial problems.  Journal of Computer and System Sciences, 9(3):256 – 278, 1974.
  * [15] M. J. Katz, F. Nielsen, and M. Segal.  Maintenance of a piercing set for intervals with applications.  Algorithmica, 36(1):59–73, 2003.
  * [16] S. Kundu and S. Majumder.  A linear time algorithm for optimal $k$-hop dominating set of a tree.  Information Processing Letters, 116(2):197–202, 2016.
  * [17] J. K. Lan and G. J. Chang.  Algorithmic aspects of the _k_ k-domination problem in graphs.  Discret. Appl. Math., 161(10-11):1513–1520, 2013.
  * [18] D. Meierling and L. Volkmann.  A lower bound for the distance $k$-domination number of trees.  Results in Mathematics, 47:335–339, 2005.
  * [19] T. Nieberg and J. Hurink.  A PTAS for the minimum dominating set problem in unit disk graphs.  In WAOA, pages 296–306, 2005.
  * [20] R. Raz and S. Safra.  A sub-constant error-probability low-degree test, and a subconstant error-probability PCP characterization of NP.  In STOC, pages 475–484, 1997.
  * [21] F. Tian and J. M. Xu.  A note on distance domination numbers of graph.  Australasian Journal of Combinatorics, 43:181–190, 2005.


# Thermal transport across metal-insulator interface via electron-phonon
interaction

Lifa Zhang,1 Jing-Tao Lü,2 Jian-Sheng Wang,1 Baowen Li1,3,4 1 Department of
Physics and Centre for Computational Science and Engineering, National
University of Singapore, Singapore 117542, Republic of Singapore  2 DTU-
Nanotech, Department of Micro- and Nanotechnology, Technical University of
Denmark (DTU), Ørsteds Plads, Bldg. 345E, DK-2800 Lyngby, Denmark  3 NUS
Graduate School for Integrative Sciences and Engineering, Singapore 117456,
Republic of Singapore  4 NUS-Tongji Center for Phononics and Thermal Energy
Science and Department of Physics, Tongji University, 200092 Shanghai, PR
China

###### Abstract

The thermal transport across metal-insulator interface can be characterized by
electron-phonon interaction through which an electron lead is coupled to a
phonon lead if phonon-phonon coupling at the interface is very weak. We
investigate the thermal conductance and rectification flowing between the
electron part and the phonon part using nonequilibrium Green’s function
method. It is found that the thermal conductance has a nonmonotonic behavior
as a function of average temperature or the coupling strength between the
phonon leads in the metal part and the insulator one. The metal-insulator
interface shows evident thermal rectification effect, which can reverse with
changing of average temperature or the electron-phonon coupling.

###### pacs:

68.35.-p, 66.70.-f, 63.20.kd, 72.10.Di

##  1 Introduction

With the increase of integration density, accumulation of heat becomes a
bottleneck for further development of microelectronic devices. Moreover, as
most of electronic devices consist of metal and insulator/semiconductor
interfaces, to understand the thermal transport through the metal-
insulator/semiconductor interface is indispensable for heat dissipation [1, 2,
3].

Figure 1: (a) Heat generation in a metal with an applied bias. The arrow shows
the heat transport from the metal to the insulating substrate. (b) An electron
bath and a phonon bath at two different temperatures connected by EPI. Energy
exchanges between the two baths and there is a net thermal current $J$ from
the hot bath to the cold one. (c) The lattice model of the metal-insulator
interface. The one dimensional electron lead (the left upper semi-infinite
chain where the dots represent electron states ) connects to the one
dimensional atomic chain (the right semi-infinite chain) via electron-phonon
interaction $V_{\rm ep}$. The phonon part in the metal (the left lower semi-
infinite atomic chain) can also be considered to the thermal transport, which
connects to the right atomic chain by a relative coupling $\lambda$.

In metals electrons dominate thermal transport while phonons do in
semiconductors and insulators; thus for thermal transport across metal-
nonmetal interfaces, energy must transfer between electrons and phonons [4].
Thanks to many remarkable physical properties and prospects for large-area
epitaxial growth, graphene is a promising material for future electronics [5].
The biased graphene on a dielectric insulator often appears in electronic
devices especially in transistors. Due to the bias the electrons in metallic
part have a higher effective temperature than the phonons in the insulating
substrate; and the thermal transport from the electrons in metal to the
phonons in insulator is one important channel of energy transfer [7, 8]. It is
found in a very recent experiment on a carbon nanotube that more that 80
percent of the electrical power supplied to the nanotube is transferred
directly into the substrate by the electron-phonon interaction (EPI) [9].
Therefore to understand the thermal transport across the interface through the
EPI is highly desirable for the heat dissipation in electronic devices.

To study the thermal transport across interface, the acoustic mismatch model
[6] and the diffuse mismatch model [10, 4] are widely applied; however, both
models offer limited accuracy in nanoscale interfacial resistance predictions
[11] because they neglect atomic details of actual interfaces. A scattering
boundary method within the lattice dynamic approach [12, 13, 14] fully
considers the atomic structures in the interface; but it can only be applied
to ballistic thermal transport. Classical molecular dynamics is another widely
used method in phonon transport [15, 16, 17], which is not accurate below the
Debye temperature, and ignores the quantum effect. Only recently the
nonequilibrium Green’s function method, which originates from the study of
electronic transport [18], been applied to study the quantum phonon transport
[19, 20, 21, 22]. So far the study of the coupled electronic and phonon
transport [23, 24, 25] is rare, especially in the metal-nonmetal interface [4,
28, 29].

In this paper, using the nonequilibrium Green’s function method, we study the
thermal transport across metal-insulator interface via the EPI. Our model can
also be applied to metal-semiconductor interface. We study energy flow between
an electron bath and a phonon bath which are connected by electron-phonon
coupling, as shown in Fig.1 (b). The electron bath, described by a semi-
infinite electronic chain under tight-binding approximation, connects with a
phonon lead illustrated as a semi-infinite harmonic atomic chain by a weak
electron-phonon interaction, as shown in Fig.1 (c), where the phonon degrees
of freedom in metal can also be considered in the thermal transport.

##  2 Model and Method

We study the interfacial thermal transport at the metal-insulator interface as
shown in Fig. 1(a). To manifest the effect of the interface we exclude the
nonlinear electron or phonon transport in the two materials themselves, thus
the only thermal resistance comes from the interface. Such model really
uncovers the thermal transport properties of the interface itself. To study
the longitudinal thermal transport, that is, the cross-plane interfacial
transport, we can simplify the problem further to thermal transport between an
electron bath and a phonon bath which are connected by an electron-phonon
coupling, as shown in Fig. 1(b), and can be represented by one dimensional
lattice model as shown in Fig. 1(c), where a semi-infinite electronic chain
(at temperature $T_{Le}$) connects to a semi-infinite atomic chain (at
temperature $T_{R}$) by an electron-phonon interaction $V_{ep}$. The phonon
part in the metal can also be considered by another semi-infinite atomic chain
which connects to the right atomic chain by a relative coupling $\lambda$. In
our model, the scattering for both electrons and phonons only comes from the
interface, and the electron and phonon transport in the corresponding semi-
infinite periodic leads is ballistic. Therefore we can partition the system
into three parts ($L$, $C$, $R$), the atoms at the interface are regarded as
center illustrated as the dashed-line rectangle in Fig.1 (c), and the rest
parts are leads. For simplicity, we only consider one dimensional case,
ignoring electron spin. Thus the Hamiltonian of the whole system in Fig.1 (c)
is written as

$H=H^{L}_{\rm e}+H^{C}+H^{LC}_{\rm e}+\sum_{\alpha=L,R}(H^{\alpha}_{\rm
p}+H^{\alpha C}_{\rm p}),$ (1)

where $H^{L}_{\rm
e}=\sum_{i}\varepsilon_{0}c^{\dagger}_{i}c_{i}-\sum_{|i-j|=1}tc^{\dagger}_{i}c_{j}$
is the Hamiltonian of the electron lead in the left part. The electron
coupling between the left lead (the site 1) and the center is $H^{LC}_{\rm
e}=-tc^{\dagger}_{1}c-tc^{\dagger}c_{1}$. We set atomic mass $m=1$, and the
Hamiltonian of the center is

$H^{C}=\frac{1}{2}\dot{u}^{2}+\frac{1}{2}(\lambda
k^{L}+k^{R})u^{2}+\varepsilon_{0}c^{\dagger}c+V_{\rm ep}c^{\dagger}cu,$ (2)

where $k^{L}$ and $k^{R}$ are the spring constants of the left and right
atomic chains, respectively. $u$ is the atom displacement. $\lambda k^{L}$
denotes the coupling between the two atomic chains; $\lambda$ can be chosen
from 0 to 1. $V_{\rm ep}$ is the electron-phonon coupling. The phonon
Hamiltonian of two leads and its coupling to the center are $H^{\alpha}_{\rm
p}=\frac{1}{2}\sum_{i}\dot{u}^{\alpha}_{i}\dot{u}^{\alpha}_{i}+\frac{1}{2}\sum_{|i-j|=0,1}u^{\alpha}_{i}K^{\alpha}_{ij}u^{\alpha}_{j}$
and $H^{\alpha C}_{\rm p}=u^{\alpha}_{1}K^{\alpha C}u$ [20, 23].

Applying the standard procedure of nonequilibrium Green’s function method
[20], without the EPI, we obtain the electron retarded Green’s function
$G^{r}_{0}(\varepsilon)=\left[\varepsilon-\varepsilon_{0}-\Sigma^{r}_{L}(\varepsilon)\right]^{-1}$,
where $\Sigma^{r}_{L}=g^{r}_{L}t^{2}$ is the retarded self-energy with a
surface Green’s function $g^{r}_{L}$, where
$g^{r}=\left[(\varepsilon+i\eta)I-H^{L}_{\rm e}\right]^{-1}$. The less Green’s
function can also be easily obtained. The phonon retarded Green’s functions is
$D^{r}_{0}(\omega)={D^{a}_{0}}^{\dagger}(\omega)=\left[\omega^{2}-(\lambda
k^{L}+k^{R})-\Pi^{r}_{L}(\omega)-\Pi^{r}_{R}(\omega)\right]^{-1}$, where
$\Pi^{r}_{L}(\omega)=(\lambda k^{L})^{2}d^{r}_{L}(\omega)$ and
$\Pi^{r}_{R}(\omega)=(k^{R})^{2}d^{r}_{R}(\omega)$ are the retarded self
energies of left and right leads with surface Green’s function $d^{r}_{L}$ and
$d^{r}_{R}$, where
$d^{r}_{L,R}=\left[(\omega+i\eta)^{2}I-K^{L,R}\right]^{-1}$. The EPI is
included as perturbation. The full Green’s functions are obtained from the
Dyson equation, that is, $G^{r,a}=[(G_{0}^{r,a})^{-1}-\Sigma^{r,a}_{\rm
ep}]^{-1}$, and $G^{<,>}=G^{r}(\Sigma^{<,>}_{\rm ep}+\Sigma^{<,>}_{L})G^{a}$,
where $\Sigma^{r,a,<,>}_{\rm ep}$ is the self-energy from the EPI. For phonon,
we have $D^{r,a}=[(D_{0}^{r,a})^{-1}-\Pi^{r,a}_{\rm ep}]^{-1}$, and
$D^{<,>}=D^{r}(\Pi^{<,>}_{\rm ep}+\Pi^{<,>}_{L}+\Pi^{<,>}_{R})D^{a}$, where
the nonlinear self energy $\Pi^{r,a,<,>}_{\rm ep}$ comes from the electron-
phonon coupling. Keeping the lowest non-zero order (second order) of the self-
energies, we could obtain the nonlinear self-energies $\Sigma^{r,a,<,>}_{\rm
ep}$ and $\Pi^{r,a,<,>}_{\rm ep}$ up the second order, which are general for
any dimensional systems. For our one-dimensional simple model as shown in
Eq.2, the self-energies could be written as

$\Sigma_{\rm ep}^{>,<}(\varepsilon)=iV_{\rm
ep}^{2}\int{G_{0}^{>,<}}(\varepsilon-\omega){D_{0}^{>,<}}(\omega)\frac{d\omega}{2\pi},$
(3)

and

$\displaystyle\Sigma_{\rm ep}^{r}(\varepsilon)$ $\displaystyle=$
$\displaystyle iV_{\rm
ep}^{2}\bigl{\\{}-{D_{0}^{r}}(\omega^{\prime}=0)\int{G_{0}^{<}}(\varepsilon^{\prime})\frac{d\varepsilon^{\prime}}{2\pi}$
(4)
$\displaystyle+\int\frac{d\omega}{2\pi}\bigr{[}{G_{0}^{r}}(\varepsilon-\omega){D_{0}^{<}}(\omega)+{G_{0}^{<}}(\varepsilon-\omega){D_{0}^{r}}(\omega)$
$\displaystyle+{G_{0}^{r}}(\varepsilon-\omega){D_{0}^{r}}(\omega)\bigr{]}\bigr{\\}}.$

The nonlinear self-energies for the phonons are

$\Pi_{\rm ep}^{>,<}(\omega)=-iV_{\rm
ep}^{2}\int\frac{d\varepsilon}{2\pi}{G_{0}^{>,<}}(\varepsilon){G_{0}^{<,>}}(\varepsilon-\omega),$
(5)

and

$\displaystyle\Pi_{\rm ep}^{r}(\omega)$ $\displaystyle=$ $\displaystyle-
iV_{\rm
ep}^{2}\int\frac{d\varepsilon}{2\pi}\bigl{[}{G_{0}^{r}}(\varepsilon){G_{0}^{<}}(\varepsilon-\omega)$
(6)
$\displaystyle+{G_{0}^{<}}(\varepsilon){G_{0}^{a}}(\varepsilon-\omega)\bigr{]}.$

Eqs. (3-6) are the so-called Born approximation (BA). By replacing the bare
Green’s functions $G_{0}$ and $D_{0}$ with the full Green’s functions $G$ and
$D$, we do iteration under self-consistent Born approximation (SCBA). While
the BA fails to satisfy the energy current conservation, the SCBA fulfills it
[23].

Therefore, we obtain the heat current from electron part as [18, 30, 31]

$J^{\rm e}=\int\frac{d\varepsilon}{2\pi\hbar}\varepsilon~{}{\rm
Tr}\\{G^{>}(\varepsilon)\Sigma^{<}_{L}(\varepsilon)-G^{<}(\varepsilon)\Sigma^{>}_{L}(\varepsilon)\\}.$
(7)

The heat current from the phonon lead is [20, 23, 32]

$J^{\rm p}_{\alpha}=-\int\frac{d\omega}{4\pi}\hbar\omega~{}{\rm
Tr}\\{D^{>}(\omega)\Pi^{<}_{\alpha}(\omega)-D^{<}(\omega)\Pi^{>}_{\alpha}(\omega)\\}.$
(8)

Due to energy conservation, $J^{\rm e}+J^{\rm p}_{L}+J^{\rm p}_{R}=0$. If the
coupling $\lambda=0$, we obtain $J^{\rm e}=-J^{\rm p}_{R}$ when the energy
flows across the interface only through EPI, that is, the heat generation of
the metal part transfers directly to the insulator part. We set the Plank
constant $\hbar=1$ and the Boltzman constant $k_{\rm B}=1$ in the following
numerical calculation; and $\varepsilon_{0}=0$, $k^{L}=k^{R}=1,\;t=1$. We
define the conductance $\sigma=|J^{\rm e}|/\Delta T$ to illustrate the thermal
transport between the electron part and phonon part.

##  3 Thermal Conductance across the Interface

Figure 2:  (a) Thermal conductance across the metal-insulator interface vs the
average temperature of the baths. $T_{L\rm e}=T_{0}+\Delta T$, $T_{L\rm
p}=T_{R}=T_{0}-\Delta T$, $\Delta T=0.01$, $V_{\rm ep}=0.01$. (b) The thermal
current density $J(\varepsilon)$ ($J^{\rm e}=\int d\varepsilon
J(\varepsilon)$) for electrons with energy $\varepsilon$ at
$\lambda=0^{+}=10^{-4}$. (c) The thermal conductance (left scale) and current
(right scale) from the electron bath vs the temperature difference $\Delta T$
at $T_{0}=1.0$.

As shown in Fig.1(a), if the metal part is applied by a voltage, the average
energy of electrons increases, which means the electrons have a higher
effective temperature than the phonons. Thus we set the left and right phonon
leads to a lower temperature $T_{L\rm p}=T_{R}=T_{0}-\Delta T$, while the
electron lead has a higher temperature $T_{L\rm e}=T_{0}+\Delta T$. If we
don’t consider the phonon contribution in the metal part, the thermal
conductance from the electron lead to the phonon lead has a nonmonotonic
behavior with increasing the average temperature $T_{0}$, as shown in Fig.
2(a). In the low-temperature region, as temperature increases, the thermal
conductance increases due to more contribution from electrons with energy far
from Fermi surface ($\varepsilon=0$) although there is certain decrease from
the contribution near Fermi surface, which can be seen from the solid line
($T_{0}=0.2$) and dashed line ($T=0.6$) in Fig. 2 (b). With the temperature
further increasing, the dominating effect comes from the decrease of the
contribution near the Fermi level, as shown in the dashed line and dotted line
of Fig. 2 (b). This causes the thermal conductance to decrease after certain
temperature. Such dependence of thermal conductance on temperature is
consistent with the experiment observation of thermal contact conductance
between graphene and silicon dioxide [33]. While the conductance has a
nonmonotonic dependence on $T_{0}$, the heat current and conductance shows a
monotonic behavior with temperature difference $\Delta T$ increasing, as shown
in the inset of Fig. 2 (c). If we include the phonon contribution in the metal
part, the thermal conductance has a similar temperature dependence, but with a
smaller magnitude. This means that the heat generation from the electron part
is affected by the coupling strength between the two phonon parts in the
metal-insulator interface.

In order to investigate the effect of phonon-phonon channel $\lambda$ on the
thermal transport through electron-phonon channel $V_{ep}$, in Fig. 3 (a) we
plot the heat current from the electrons to the phonons when we increase the
coupling strength $\lambda$ between the two phonon parts. We find that in the
small $\lambda$ region, with $\lambda$ increasing the heat current flows into
the right phonon lead will increase due to the smaller difference between the
atom ($K^{C}=(\lambda k^{L}+k^{R})$) in interface and the atoms
($K^{R}_{ii}=2k^{R}$) in the right lead, thus the scattering for phonons at
the interface decreases. The heat is easier to transport to the right lead;
$J^{\rm e}$ increases. At the same time, the heat can flow from the electrons
to the left phonon lead; $-J^{\rm p}_{L}$ increases with $\lambda$. When the
$\lambda$ increases further, the phonon scattering between left chain and the
center atom decreases, more thermal energy transferred from electron is easier
to flow into the left lead. Such fast increasing of $-J^{\rm p}_{L}$ causes
the decreasing of the heat into the right lead $-J^{\rm p}_{R}$. With
increasing of $\lambda$, the phonon scattering at the interface between the
left and right atomic chains decreases, more phonons can transport coherently
in the two atomic leads, and are less efficient to couple to electrons; thus
the heat flowing from the electron lead begins to decrease. Due to continuous
increase of the heat flowing into the left phonon lead $-J^{\rm p}_{L}$, and
$J^{\rm e}+J^{\rm p}_{L}+J^{\rm p}_{R}=0$, thus the decrease of heat from
electrons $J^{\rm e}$ lags behind the decrease of the heat into the right lead
$-J^{\rm p}_{R}$. And if $\lambda=1$, the heat into two phonon leads has the
same value due to the symmetry. As shown in Fig. 3 (b), if the non-biased
metal part in a higher temperature while the insulator in a lower one, the
heat flow from electron part has a similar dependence on $\lambda$; but the
heat flowing from left phonon lead and the one into the right phonon lead
monotonically increase with $\lambda$ since phonon transport dominates heat
flow in such case and the phonon scattering decreases. We also find that, in
this case the thermal transport through the phonon-phonon channel $\lambda$ is
several orders of magnitude larger than that through the electron-phonon
channel. And even if $\lambda=4\times 10^{-4}$ (see the inset of Fig. 3(b)),
the thermal current of phonon is ten times larger than that of electron.
Therefore for the thermal transport in the non-biased metal-insulator
interface, such small thermal current of electron can be ignored, which is
consistent with the recent finding in Ref.[34]. However, for the interface
between a biased metal and a insulator, the thermal transport through the
electron-phonon interaction is very important, which dominated the thermal
transport even if $\lambda=1$ as shown in Fig 3 (a), which can explain the
remote Joule heating via electron-phonon interaction in Ref. [9].

Figure 3:  (a) Thermal current vs the coupling $\lambda$. The solid line
corresponds to the thermal current $J^{\rm e}$ flowing from the electron bath.
The dashed and dotted lines correspond to the thermal current ($-J^{\rm
p}_{L}$ and $-J^{\rm p}_{R}$ ) flowing into the left and right phonon baths,
respectively. (b) Thermal current vs the coupling $\lambda$ at $T_{L\rm
e}=T_{L\rm p}=1.01$, $T_{R}=0.99$. The solid, dashed and dotted lines
correspond to the thermal current flowing from the electron bath (left scale),
the left and the right phonon baths (right scale), respectively. The inset is
the zoom-in of (b) for small $\lambda$. For (a) and (b), $V_{\rm ep}=0.01$.

##  4 Thermal Rectification across the Interface via EPI

Figure 4:  Thermal rectification of the metal-insulator interface vs
temperature difference. The inset: the thermal current across the interface vs
temperature difference. $T_{h}=T_{0}(1+\Delta T)$, $T_{c}=T_{0}(1-\Delta T)$,
$V_{\rm ep}=0.01$.

Thanks to nonlinearity and asymmetry of the metal-insulator interface, we can
expect the thermal rectification, which is defined as $R=(J_{+}-J_{-})/{\rm
max}\\{J_{+},J_{-}\\}$, where $J_{+}$ is the forward direction heat flux,
defined as $T_{L}=T_{h},T_{R}=T_{c}$, and $J_{-}$ is that of the backward
direction when $T_{L}=T_{c},T_{R}=T_{h}$. Here, $T_{h}$ and $T_{c}$ correspond
to the temperatures of the hot and cold baths, respectively. In the rest of
the paper, we will not consider the phonon contribution in metal (we set
$\lambda=10^{-4}$, $T_{Lp}=T_{R}$ in the calculation to avoid divergence),
which will not change the physical properties of the rectification, and only
decrease its magnitude. Figure 4 shows the dependence of thermal rectification
on temperature difference for different average temperatures. The
rectification shows a monotonically increasing behavior of temperature
difference due to the bigger difference of heat current in larger temperature
difference as shown in the inset of Fig. 4, which is consistent with all the
traditional study on thermal rectification [35, 36]. With the temperature
$T_{0}$ increasing, we find that the rectification can change sign.

Figure 5:  (a) Thermal rectification of the metal-insulator interface vs
temperature $T_{0}$ for different temperature differences at $V_{\rm
ep}=0.01$. (b) Thermal rectification vs the electron-phonon interaction
$V_{ep}$ at different temperatures. (c) The forward thermal current (solid
line) and backward thermal one (dashed line) vs $V_{\rm ep}$ at $T_{0}=0.25$.
(d1)-(d4) The local available density of states (LADOS) at surface for the
left electron part ($\rho_{\rm e}={|\rm Img}(g^{<})|$)(solid line) and the
right phonon part ($\rho_{\rm p}={|\rm Img}(d^{<})\omega|$)(dashed line).
(d1)((d2)) and (d3)((d4)) are corresponding to the forward (backward)
transport at $T_{0}=0.25$ and $1.0$, respectively. (e1)-(e4) The forward
(solid lines) and backward (dashed lines) thermal current density
$J(\varepsilon)$ for different temperatures and different EPI. For all the
curves, $T_{h}=T_{0}(1+\Delta T)$, $T_{c}=T_{0}(1-\Delta T)$; from (b) to (e)
$\Delta T=0.4$.

The dependence of thermal rectification on temperature and the EPI is shown in
Fig. 5. We find that at a relative larger EPI ($V_{\rm ep}=0.01$), with
increasing the temperature, the thermal rectification can change sign from
positive to negative. However for a very weak EPI, the rectification always
keeps negative, as shown in Fig 5(b). Within the range of $\lambda=10^{-4}\sim
10^{-2}$, the rectification is always negative for higher temperatures, while
it can change sign from negative to positive in a lower temperature $T=0.25$.
The relation of thermal currents in the forward and backward direction changes
with increasing of $\lambda$ while both their magnitudes monotonically
increase, as shown in Fig 5(c).

From the local available density of states (LADOS) of electrons and phonons at
the surface of the corresponding leads, we find that at a higher temperature
$T_{0}=1.0$, going from the forward transport to the backward one, the main
change is that the LADOS phonons largely increases, as shown in Fig. 5 (d3)
and (d4), which causes a larger current in the backward direction than that in
the forward direction, thus the rectification is negative. At a lower
temperature, the change of LADOS for electrons and phonons are not obvious, as
shown in Fig. 5 (d1) and (d2), and the rectification could change with the
strength of EPI.

Turning on the EPI, the electron Green’s functions change much more than the
phonon ones; with increasing EPI, the Green’s functions of electrons $G^{>}$
and $G^{<}$ become more asymmetric, especially for the $G^{<}$ which have
larger value at the energy far away from the Fermi level ($\varepsilon=0$). At
a very weak EPI, the heat current comes from the contribution of electronic
energies symmetrically away from the Fermi level. The heat current of the
backward transport is larger than that of the forward one, as shown in Fig. 5
(e1) and (e3), due to the increase of the LADOS of phonons in the backward
direction, thus the rectification are negative for all the temperatures at
weak EPI as shown in Fig 5(b). With a stronger EPI, which induces larger value
of $G^{<}$ at the energy range $-2\sim-1$, where the center electron has
larger density of states. Thus we find that the forward current has larger
value at the range of $-2\sim-1$ as shown in Fig. 5(e2). At the same time, the
heat current can be affected by the temperature, in the low temperature range,
as temperature increases, more electrons with energy far away from Fermi level
contribute to the thermal current, as discussed in Fig. 2(b). Thus in Fig.
5(e2), the forward heat current is larger than the backward one; the
rectification is positive at low temperatures with larger EPI. In the higher
temperature range, the contribution from energy far away from Fermi level will
decrease with temperature increasing as shown in Fig. 2(b); further more, the
mainly change from LADOS of electron and phonon is the larger phonon LADOS in
the backward transport than that in the forward one; thus the backward heat
current is larger than the forward one as shown in Fig. 5(e4). Therefore, due
to mismatch of electron LADOS and phonon one, the rectification is negative
for high temperatures or weak EPI. Due to the nonlinearity of EPI and its
relation with temperature, we can find the positive rectification with
relative larger EPI at low temperatures.

##  5 Discussions

Figure 6:  Green’s functions for electrons and phonons, $T_{L\rm
e}=T_{0}+\Delta T$, $T_{L\rm p}=T_{R}=T_{0}-\Delta T$, $T_{0}=0.2$, $\Delta
T=0.01$. (a) The imagine part of the bare greater and less Green’s functions
for phonons and electrons: $D_{0}^{>}$ (solid line),$D_{0}^{<}$ (dotted
line),$G_{0}^{>}$ (dashed line),$G_{0}^{<}$ (dash-dotted line). (b) The
imagine part of the full Green’s functions for phonons and electrons: $D^{>}$
(solid line),$D^{<}$ (dotted line),$G^{>}$ (dashed line),$G^{<}$ (dash-dotted
line) with the EPI ($V_{\rm ep}=0.01$).

###  5.1 Full Green’s functions in the calculation

Under the SCBA, we calculate the self energies of the EPI; after the iteration
is convergent we obtain all the Green’s functions of $G^{>,<}$ and $D^{>,<}$
in Eq. (3) and (4) in the main text, then we can calculate the heat currents.
If we do not consider the phonon contribution in the metal part, we should
choose the coupling $\lambda$ be a very tiny positive value, thus the heat
current to the left part will be very small and negligible; as shown in Fig. 3
in the main text, if $\lambda=10^{-4}$ the heat current flowing into the left
phonon leads is almost zero. If $\lambda=0$, the iteration to calculate self
energies for EPI will be divergent, but if $\lambda=0^{+}=10^{-4}$, it can be
convergent. Thus here the tiny $\lambda=0^{+}$ plays a role as very small
onsite potential for the center atom, which is similar as the tiny onsite in
computing the phonon Hall effect [38]. We plot the bare Green’s functions
$G_{0}$, $D_{0}$ and the full Green’s functions $G$, $D$ in Fig. 6. Without
the EPI, the bare Green’s functions of electrons $G_{0}^{<}$ and $G_{0}^{>}$
are symmetric with respect to the origin as shown in Fig. 6 (a), but which
symmetry for $G^{<}$ and $G^{>}$ will be broken and change much if we turn on
the EPI, which can be seen in Fig 6 (b). However, the Green’s functions for
phonons do not change much.

###  5.2 The role of Fermi energy of electrons

Figure 7:  The conductance (left panel) and the rectification (right panel) vs
the onsite $\varepsilon_{0}$. $\lambda=10^{-4}$. For comparison, The dotted
lines in (a) and (b) are copied from the corresponding line in Fig.2 (a) and
Fig.5(a), respectively.

We set the onsite $\varepsilon_{0}=0$ in the main text, thus the Fermi energy
of the electron system is $\varepsilon=0$. However we can change the onsite
$\varepsilon$, as shown in Fig. 7, the onsite potential can change the
magnitude of the thermal conductance and the rectification, and the
temperature where the thermal conductance and rectification have maximum value
shifts a bit. However the curves of the thermal conductance and rectification
have the same properties with the case at $\varepsilon_{0}=0$. Therefore, the
mechanism found for the non-monotonicity of conductance and reversal of
rectification still holds for the case of nonzero Fermi energy.

###  5.3 Limitation and application

We use a simplified one-dimensional model to study thermal conductance and
rectification across the metal-insulator interface via electron-phonon
interaction. For some quasi-one dimensional metal-insulator interface systems,
the thermal transport can simply be recast to one-dimensional model, then our
results of the conductance and rectification can be applied. The thermal
resistance of a whole interface system comes from the two materials themselves
and the interface between them. Our study in this work focuses on the
interface itself, which provides understanding on the interface in the thermal
transport. Although the thermal transport via electron-phonon interaction can
be ignored in the non-biased metal-insulator interface, it dominates the
thermal transport in the remote Joule heating in a biased metal-insulator
interface.

For real materials, there would be more atoms in one unit cell, thus more
phonon branches will contribute to the thermal transport. To compare with
experiments on real materials, the simplified model need to be generalized to
two-dimensional or three dimensional with input of the real parameters. For
realistic three dimensional systems, the density of states of electrons and
phonons are quite different from those in one dimension [39], then the
analysis for the mechanism of the thermal rectification would be different and
more complicated; but the general properties on the interfacial thermal
transport, such as thermal conductance as functions of $T$, $\lambda$ and the
rectification tuned by temperature or electron-phonon interaction, would still
hold and could be verified by the future experiments.

The nonequilibrium Green’s function approach is a good candidate to solve the
interfacial thermal transport. If we study two or three dimensional systems
with large number atoms in the interface, the self-consistent process is time
consuming, and we also need to pay more attention to its convergency. If we
only are interested on the thermal conductance accurate to the second order of
$V_{ep}$, the Born approximation is applicable to avoid the convergent
problem. However, for the thermal rectification as a function of $V_{ep}$ can
only be obtained by the self consistent Born approximation. Therefore the
calculation of the simple model can provide the understanding of the basic
properties of thermal transport at metal-insulator interface and can be
generalized to real materials with the parameters obtained from first-
principle calculation. The challenges would come from the time consuming for
the self-consistent calculation of the nonlinear self energies $\Sigma_{\rm
ep}$ and $\Pi_{\rm ep}$.

##  6 Conclusion

In summary, using nonequilibrium Green’s function method we study the thermal
transport across metal-insulator interface with an EPI. The thermal
conductance and rectification across the interface is thoroughly investigated
under SCBA by a clean and efficient model where an electron lead couples to a
phonon lead through the EPI. We find that the thermal conductance is a
nonmonotonic function of average temperature, it has a maximum value at
certain temperature. Considering the phonon part in metal contributing to the
thermal transport, the heat flow from electron part will change while it has a
similar dependence on temperature. The thermal rectification effect across the
metal-insulator interface can reverse with varying of system average
temperature and the EPI. Our results are very helpful to explain and guide the
experiment on the thermal transport and dissipation in electronic devices and
interface system; and could be verified in the biased and non-biased graphene
sheet supported on insulating substrate. The reversal rectification is
significant for the study of one-way heat transport and tuning the direction
of thermal transport; thus it could have wide application in the energy
science.

## Acknowledgements

L. Z.and B. L. are supported by the grant R-144-000-300-112 from Ministry of
Education of Republic of Singapore. J.-S. W. acknowledges support from a URC
research grant R-144-000-257-112 of NUS. J.-T. L. acknowledges the Lundbeck
Foundation for financial support (R49-A5454).

## References

## References

  * [1] Vankatasubramanian R., Silvola E., Colpitts T., O’Quinn B., Nature 413, (2001) 597.
  * [2] Cahill D. G., Ford W. K., Goodson K. E., Mahan G. D., Majumdar A., Maris H. J., Merlin R., and Phillpot S. R., J. Appl. Phys. 93, (2003) 793.
  * [3] Costescu R. M., Cahill D. G., Fabreguette F. H., Sechrist Z. A., and George S. M., Science, 303, (2004) 989.
  * [4] Majumdar A. and Reddy P., Appl. Phys. Lett. 84, (2004) 4768.
  * [5] Castro Neto A. H., Guinea F., Peres N. M. R., Novoselov K. S., and Geim A. K., Rev. Mod. Phys. 81, (2011) 109.
  * [6] Little W., Can. J. Phys. 37, (1959) 334 .
  * [7] Chen J. H., Jang C., Xiao S., Ishigami M., and Fuhrer M. S., Nature Nanotech. 3, (2008) 206.
  * [8] Perebeinos V., Rotkin S. V., Petrov A. G., and Avouris P. , Nano Lett. 9, (2009) 312.
  * [9] Baloch K. H., Voskanian N., Bronsgeest M. and Cumings J. , Nature Nanotech. 7, (2012) 316.
  * [10] Swartz E. and Pohl R., Rev. Mod. Phys.61, (1989) 605.
  * [11] Stevens R., Smith A., and Norris P., J. Heat Transfer 127, (2005) 315.
  * [12] Lumpkin M. E. and Saslow W. M., Phys. Rev. B. 17, (1997) 4295.
  * [13] Wang J. and Wang J.-S., Phys. Rev. B. 74, (2006) 054303.
  * [14] Zhang L., Wang J. -S., and Li B., Phys. Rev. B 78, (2008) 144416.
  * [15] Li B., Lan J., and Wang L., Phys. Rev. Lett. 95, (2005) 104302.
  * [16] Termentzidis K., Chantrenne P., and Keblinski P., Phys. Rev. B 79, (2009) 214307.
  * [17] Landry E. S. and McGaughey A. J. H., Phys. Rev. B 80, (2009) 165304.
  * [18] Haug H. and Jauho A. P., _Quantum Kinetics in Transport and Optics of Semiconductors_ (Springer, Berlin, 1996).
  * [19] Zhang W., Fisher T. S., and Mingo N., Numerical Heat Transfer, Part B 51, (2007) 333.
  * [20] Wang J.-S., Wang J., and Lü J. T., _Eur. Phys. J. B_ 62, (2008) 381.
  * [21] Zhang L., Keblinski P., Wang J.-S., and Li B., Phys. Rev. B 83, (2011) 064303.
  * [22] Zhang L., Wang J.-S., and Li B., New J. Phys. 11, (2009) 113038.
  * [23] Lü J. T. and Wang J.-S., Phys. Rev. B 76, (2007) 165418.
  * [24] Galperin M., Ratner M. A., and Nitzan A., J. Phys.: Condens. Matter 19, 103201 (2007). M. Galperin, A. Nitzan, and M. A. Ratner, Phys. Rev. B 75, (2007) 155312.
  * [25] Musho D. and Walker D. G., ASME Conf. Proc. 2011, (2011) 413.
  * [26] Auer C., Schurrer F., and Ertler C., Phys. Rev. B 74, (2006) 165409.
  * [27] Lazzeri M. and Mauri F., Phys. Rev. B 73, (2006) 165419.
  * [28] Pop E., Mann D. A., Goodson K. E., and Dai H., J. Appl. Phys. 101, (2007) 093710.
  * [29] Ordonez-Miranda J., Alvarado-Gil J. J., and Yang R., J. Appl. Phys. 109, (2011) 094310.
  * [30] Meir Y. and Wingreen N. S., Phys. Rev. Lett. 68, (1992) 2512.
  * [31] Jauho A.-P., Wingreen N. S., and Meir Y., Phys. Rev. B 50, (1994) 5528.
  * [32] Wang J.-S., Zeng N., Wang J., and Gan C. K., Phys. Rev. E 75, (2007) 061128.
  * [33] Chen Z., Jang W., Bao W., Lau C. N., and Dames C., Appl. Phys. Lett. 95, (2009) 161910.
  * [34] Singh P., Seong M., and Sinha S., Appl. Phys. Lett. 102, 181906 (2013).
  * [35] Li B., Wang L., and Casati G., Phys. Rev. Lett. 93, (2004) 184301.
  * [36] Li N., Ren J., Wang L., Zhang G., Hänggi P., B. Li, Rev. Mod. Phys. 84, (2012) 1045.
  * [37] Zhang L., Yan Y., Wu C.-Q., Wang J.-S., and Li B., Phys. Rev. B 80, (2009) 172301.
  * [38] Wang J.-S. and Zhang L., Phys. Rev. B B 80, 012301 (2009).
  * [39] Asai Y., Phys. Rev. B, 78, 045434, [2008])