np-complete

Given a graph $G=(V,E)$,  a  function  $f:V\to \{0,1,2,3,4\}$ is a triple Roman  dominating function (TRDF)  of $G$, for each vertex $v\in V$,  (i) if $f (v ) = 0 $, then  $v$ must have either one neighbour in $V_4$, or either two neighbours in $V_2 \cup  V_3$ (one neighbour in $V_3$) or either three neighbours in $V_2 $, (ii) if $f (v ) = 1 $, then $v$ must have either one neighbour in  $V_3 \cup  V_4$  or either two neighbours in $V_2 $, and if $f (v ) = 2 $, then $v$ must have one neighbour in $V_2 \cup  V_3\cup  V_4$. The triple Roman  domination number of $G$ is the  minimum weight of an TRDF  $f$  of $G$, where the weight of $f$ is $\sum_{v\in V}f(v)$.  The triple  Roman  domination problem is to compute the  triple Roman  domination number of a given graph.  In this paper, we study the triple  Roman  domination problem. We show that   the problem is NP-complete for  the  star convex bipartite  and the   comb convex bipartite graphs and is APX-complete for graphs of degree at~most~4. We propose a linear-time algorithm for computing  the triple Roman  domination number of proper interval graphs.  We also   give an $( 2 H(\Delta(G)+1) -1  )$-approximation algorithm  for solving the problem  for any graph $G$,  where   $  \Delta(G)$ is the maximum degree of $G$ and $H(d)$ denotes the first $d$ terms of the harmonic  series. In addition, we prove  that  for any $\varepsilon>0$  there is no  $(1/4-\varepsilon)\ln|V|$-approximation  polynomial-time   algorithm for solving  the problem on bipartite and split  graphs, unless NP $\subseteq$ DTIME $(|V|^{O(\log\log|V |)})$.

For a simple, undirected graph $G(V,E)$, a function $h : V(G) rightarrow lbrace 0, 1, 2rbrace$ such that each edge $ (u,v)$ of $G$ is either incident with a vertex with weight at least one or there exists a vertex $w$ such that either $(u,w) in E(G)$ or  $(v,w) in E(G)$ and $h(w) = 2$, is called a vertex-edge Roman dominating function (ve-RDF) of $G$. For a graph $G$, the smallest possible weight of a ve-RDF of $G$ which is denoted by $gamma_{veR}(G)$, is known as the textit{vertex-edge Roman domination number} of $G$. The problem of determining  $gamma_{veR}(G)$ of a graph $G$ is called minimum vertex-edge Roman domination problem (MVERDP). In this article, we show that the problem of deciding if $G$ has a ve-RDF of weight at most $l$ for star convex bipartite graphs, comb convex bipartite graphs, chordal graphs and planar graphs is NP-complete. On the positive side, we show that MVERDP is linear time solvable for threshold graphs, chain graphs and bounded tree-width graphs. On the approximation point of view, a 2-approximation algorithm for MVERDP is presented. It is also shown that vertex cover and vertex-edge Roman domination problems are not equivalent in computational complexity aspects. Finally, an integer linear programming  formulation for MVERDP is presented.

A dominating set $ D $ of a graph $ G=(V,E) $ is called a certified dominating set of $ G $ if $vert N(v) cap (V setminus D)vert$ is either 0 or at least 2 for all $ v in D$. The certified domination number $gamma_{cer}(G) $ is the minimum cardinality of a certified dominating set of $ G $. In this paper, we prove that the decision problem corresponding to $gamma_{cer}(G) $ is NP-complete for split graphs, star convex bipartite graphs, comb convex bipartite graphs and planar graphs. We also prove that it is linear time solvable for chain graphs, threshold graphs and bounded tree-width graphs.

Let $G$ be a simple, undirected graph. In this paper, we initiate the study of independent Roman ${3}$-domination. A function $g : V(G) rightarrow lbrace 0, 1, 2, 3 rbrace$ having the property that $sum_{v in N_G(u)}^{} g(v) geq 3$, if $g(u) = 0$, and $sum_{v in N_G(u)}^{} g(v) geq 2$, if $g(u) = 1$ for any vertex $u in V(G)$, where $N_G(u)$ is the set of vertices adjacent to $u$ in $G$, and no two vertices assigned positive values are adjacent is called an textit{ independent Roman ${3}$-dominating function} (IR3DF) of $G$. The weight of an IR3DF $g$ is the sum $g(V) = sum_{v in V}g(v)$. Given a graph $G$ and a positive integer $k$, the independent Roman ${3}$-domination problem (IR3DP) is to check whether $G$ has an IR3DF of weight at most $k$. We investigate the complexity of IR3DP in bipartite and chordal graphs. The minimum independent Roman $lbrace 3 rbrace$-domination problem (MIR3DP) is to find an IR3DF of minimum weight in the input graph. We show that MIR3DP is linear time solvable for bounded tree-width graphs, chain graphs and threshold graphs. We also show that the domination problem and IR3DP are not equivalent in computational complexity aspects. Finally, we present an integer linear programming formulation for MIR3DP.

This paper considered the cost constrained vehicle scheduling problem under the constraint that the total number of vehicles is known in advance. Each depot has a different time processing cost. The goal of this problem is to find a feasible minimum cost schedule for vehicles. A mathematical formulation of the problem is developed and the complexity of the problem when there are more than two depots is investigated. It is proved that in this case, the problem is NP-complete. Also, it is showed that there is not any constant ratio approximation algorithm for the problem, i.e., it is in the complexity class APX.