Masaki Tomisawa, Hiroaki Tohyama

Department of Life Engineering, Faculty of Engineering, Maebashi Institute of Technology, Maebashi city, Gunma, 371-0816, Japan

tomisawa@maebashi-it.ac.jp, tohyama@maebashi-it.ac.jp

A vertex cover of a graph is a set of vertices that includes at least one endpoint of every edge of the graph and can be regarded as the placement of police officers or fixed surveillance cameras so that each street of a neighborhood represented by the graph can be confirmed visually without moving from their position. Given a graph G and a natural number k, the vertex cover problem is the problem of deciding whether there exists a vertex cover in G of size at most k. The vertex cover problem is one of Karp's 21 NP-complete problems.

Recently, we introduced an edge routing problem that a single police officer must confirm all the streets. The officer is allowed to move, but can confirm any street visually from an incident intersection without traversing it. We showed that the problem of deciding whether there exists a patrol route for a given mixed graph in which each edge is either traversed exactly once or confirmed visually is NP-complete. In this paper, we show that the police officer patrol problem remains NP-complete even if given graphs are weighted digraphs.

Keywords: edge traversing, police officer patrol problem, Chinese postman problem, vertex cover problem, NP-complete Mathematics Subject Classification : 68Q25, 68R10, 05C85

DOI: 10.5614/ejgta.2024.12.2.10

Received: 9 August 2022, Revised: 25 August 2024, Accepted: 16 September 2024.

1. Introduction

The Chinese postman problem (CPP) is a famous problem in graph theory to decide whether there exists a tour for a post officer in a given area within a given amount of time which starts and ends at the post office. The post officer must traverse every street in the area at least once since their Job is in order to deliver all of the town's mail.

CPP is introduced by Mei-Ko [8] as a generalization of the Eulerian circuit problem. The Eulerian circuit problem can be solved in polynomial time because it only requires checking whether the degree of every vertex in a given undirected graph is even. Edmonds and Johnson [3] showed that CPP on undirected graphs or directed graphs can also be solved in polynomial time. On the other hand, in the case that a given graph is a mixed graph, the Eulerian circuit problem remains solvable in polynomial time (cf. [12]), but CPP is shown to be NP-complete by Papadimitriou [9]. He also showed that CPP remains NP-complete even if restricted to those whose edges all have equal length or those on mixed planner graphs or on mixed graphs with vertices of degree three. Tohyama and Adachi [11] investigated how the complexity of CPP on a mixed graph changes with the addition of a limit on the number of times each edge can be traversed. Specifically, they showed that even if the number of traversals of each edge is restricted to two, CPP on mixed graphs remains NP-complete. The computational complexity of other problems related to CPP such as windy CPP, k-CPP, and capacitated CPP is summarized in [1, 10].

The rural postman problem (RPP) is one of the generalizations of CPP with a given set of edges that must be traversed by the postman. Lenstra and Rinnoy-Kan [6, 7] showed that the optimization version of RPP on undirected graphs or directed graphs is NP-hard.

A vertex cover of a graph is a set of vertices that includes at least one endpoint of every edge of the graph. The Vertex Cover problem (VC) is the problem of deciding whether there exists a vertex cover of size at most k in a given graph G where k is a given positive integer. VC is one of Karp's 21 NP-complete problems [5]. The Connected Vertex Cover problem (CVC) is to decide whether there exists a vertex cover V ′ of size at most k such that the subgraph induced by V ′ is connected for a given graph and positive integer k. CVC is NP-complete problem introduced by Garey and Johnson [4] and they also showed that CVC on planar graphs of maximum degree 4 remains NP-complete.

When a given graph is regarded as a city, that is, each vertex is intersection and each edge is street, its vertex cover is the placement of police officers or fixed surveillance cameras so that each street of a neighborhood represented by the graph can be confirmed visually without moving from their position. Not only two-way streets but also one-way streets can also be confirmed visually from either of its incident intersections.

In [12], we introduced an edge routing decision problem which is to find a patrol route for a single police officer to confirm all streets. The police officer is allowed to confirm any street visually from an incident intersection without traversing it. Therefore, he does not have to traverse all the streets. That is, the set of vertices on the patrol route becomes a connected vertex cover for the given graph. Let G = (V, E, A) be a connected simple mixed graph, where V is the set of vertices, E is the set of undirected edges and A is the set of arcs. When we simply call an edge, it is undirected edge or arc. A sequence S : v0, v1, v2, . . ., vⁿ of vertices is said to be a patrol route on G, if the following conditions hold:

• (1) For each i (0 ≤ i < n), either {vⁱ , vi+1} ∈ E or (vⁱ , vi+1) ∈ A. This means that there exists an edge between two successive vertices in S. Arcs must be traversed according to their direction. It is said that each edge {vⁱ , vi+1} ∈ E (or (vⁱ , vi+1) ∈ A) between members of S is traversed from vⁱ to vi+1.
• (2) For any i and j (0 ≤ i < j < n),

\[\{v_i, v_{i+1}\} \neq \{v_j, v_{j+1}\} \text{ if } \{v_i, v_{i+1}\}, \{v_j, v_{j+1}\} \in E \text{ and}\]
\((v_i, v_{i+1}) \neq (v_j, v_{j+1}) \text{ if } (v_i, v_{i+1}), (v_j, v_{j+1}) \in A.\)

This means that the same edge cannot be traversed more than once.

• (3) The set R^S = {vⁱ : 0 ≤ i ≤ n} of vertices in S is a vertex cover of G. That is, RS∩{v, v′} ̸= ϕ holds for any (v, v′ ) ∈ A and {v, v′} ∈ E. This means that for any edge e, at least one vertex to which e is incident is in S. If exactly one vertex to which e is incident is in S, it is said that e is confirmed visually.
• (4) v⁰ = vn. That is, S is a circuit.

For instance, we illustrate a mixed graph and a patrol route S : v1, v8, v7, v13, v6, v5, v4, v11, v3, v4, v12, v10, v¹ of the graph in Figure 1. The set of vertices R^S = {v1, v3, v4, v5, v6, v7, v8, v10, v11, v12, v13} in S is one of connected vertex cover of this graph.

Figure 1. Mixed graph and a patrol route S (red part). The set of vertices in S is one of vertex cover of this graph.

In [12], we introduced the problem of deciding whether there exists a patrol route for a given mixed graph. We named this problem the Police Officer Patrol Problem (POPP) and showed that POPP is NP-complete.

Let d^G : E ∪ A → N be a cost function for a mixed graph G = (V, E, A). Here, N is the set of natural numbers includes 0. For each edge a ∈ E ∪ A, dG(a) is regarded as its length or the time spent traversing it. Then the cost DG(S) for a patrol route S : v0, v1, v2, . . ., vⁿ on G is defined as follows:

\[\mathfrak{D}_G(\mathfrak{S}) = \sum_{i=0}^{n-1} d_G(v_i, v_{i+1}).\]

In this paper, we treat the Police Officer Patrol Problem on weighted graphs which is to decide whether there exists a patrol route on G with the cost w or less for given a graph G, a cost function d^G and a natural number w. In the case that G is a mixed graph, since this problem becomes POPP introduced in [12] if the cost of every edge is 0, its computational complexity is also NP-complete. In general, when the computational complexity of the restricted problem is compared to the one of the original problem, complexity of the restricted problem is equal or less than one of the original problem. So it would be interesting to investigate how the computational complexity of restricted problems behaves. We show that the problem as which given graphs are restricted to weighted digraphs (called DPOPP below) remain NP-complete.

2. Gadgets

In this section, firstly, we introduce two weighted digraphs used as "deemed" edges below. Secondly, we introduce two kinds of weighted digraphs represented using deemed edges and show the properties of them.

2.1. Deemed Edges

The first graph we consider is a digraph G¹ = (V1, A1), where

\[V_1 = \{v, v', u_1, u_2, u_3, u_4\} \text{ and}\]
\[A_1 = \{(v, u_1), (u_1, u_2), (u_2, v'), (v', u_3), (u_3, u_4), (u_4, v)\}.\]

For any arc a ∈ A1, d^G1 (a) = 0, that is, all arcs of G¹ are assigned cost 0. Throughout this paper, when we illustrate a weighted digraph G, only the costs of arcs such that dG(a) > 0 are indicated, and the costs zero are omitted. We illustrate G¹ in Figure 2 (i). G¹ will appear as the subgraph of

Figure 2. (i) Digraph G¹ which is called ϵ-edge ⟨v, v′ ⟩ with cost 0 and (ii) its representation.

a digraph constructed in the proof that DPOPP is NP-complete. Then only v and v ′ are adjacent to outer vertices of G1, and vertices u1, u2, u³ and u⁴ are not adjacent to them. Therefore, v and v ′ are called external vertices and u1, u2, u³ and u⁴ are called internal vertices of G1. Suppose that G¹ appears as the subgraph of a graph. Then, on any patrol route of the graph, only by dropping in at the external vertex v without dropping in at the internal vertices, arcs (v, u1) and (u4, v) can be confirmed visually. Similarly, arcs (v ′ , u3) and (u2, v′ ) can be confirmed visually only by dropping in at the external vertex v ′ . However, only by dropping in at these two external vertices, the arcs

\((u_1,u_2)\) and \((u_3,u_4)\) can not be confirmed visually. Consequently, all arcs must be traversed on any patrol route. In this case, vertices in \(G_1\) must be traversed in order from v to \(u_1\) to \(u_2\) and to v' and must be traversed in order from v' to \(u_3\) to \(u_4\) and to v. We regard \(G_1\) as a deemed edge with end points v and v' which is traversed as a round trip between v and v' with cost 0 exactly once. We call \(G_1\) an \(\epsilon\)-edge and denote it by \(\langle v, v' \rangle\). We illustrate the \(\epsilon\)-edge as in Figure 2 (ii). We remark that the \(\epsilon\)-edge \(\langle v, v' \rangle\) can be represented by \(\langle v', v \rangle\).

In order to introduce the second graph, we define a digraph \(\hat{G}_2 = (\hat{V}_2, \hat{A}_2)\), where

\[\hat{V}_2 = \{v, v', u_5, u_6, u_7, u_8, u_9, u_{10}, u_{11}\} \text{ and}\] \[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\] \[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Let v and v' be external vertices and let \(u_5, u_6, \ldots, u_{11}\) be internal vertices. Let e, f, \(g_1\) and \(g_2\) be natural numbers. The cost function \(d_{\hat{G}_2}\) is defined as follows: \(d_{\hat{G}_2}(u_5, u_7) = e\), \(d_{\hat{G}_2}(u_{10}, u_7) = f\), \(d_{\hat{G}_2}(u_{10}, u_{11}) = g_1\), \(d_{\hat{G}_2}(u_5, u_6) = g_2\) and cost zero is assigned to all other remaining arcs. We illustrate the weighted digraph \(\tilde{G}_2\) in Figure 3.

Figure 3. Weighted directed graph \(\hat{G}_2\).

Suppose that \(\mathfrak{S}\) is any patrol route on a weighted digraph including \(\hat{G}_2\). Then we consider tours on \(\hat{G}_2\) for \(\mathfrak{S}\). We remark that arcs \((u_7,u_8)\) and \((u_8,u_9)\) must be traversed. Because if these arcs are not traversed, then \((u_5,u_7)\), \((u_9,u_6)\), \((u_{10},u_7)\) and \((u_9,u_{11})\) can not be traversed, and therefore, it is not even possible to confirm \((u_7,u_8)\) and \((u_8,u_9)\) visually. Thus, there are the following four tours on \(\hat{G}_2\):

• (1) Vertices are traversed in the order from v to \(u_5\) to \(u_7\) to \(u_8\) to \(u_9\) to \(u_{11}\) and to v' (Figure 4 (i)). In this case, arcs \((u_5, u_6)\), \((u_6, v)\), \((u_9, u_6)\), \((u_{10}, u_{17})\), \((u_{10}, u_{11})\) and \((v', u_{10})\) are confirmed visually. This tour is exactly one traversal from v to v' that requires cost e.
• (2) Vertices are traversed in the order from v' to \(u_{10}\) to \(u_{7}\) to \(u_{8}\) to \(u_{9}\) to \(u_{6}\) and to v (Figure 4 (ii)). In this case, arcs \((v, u_{5})\), \((u_{5}, u_{6})\), \((u_{5}, u_{7})\), \((u_{9}, u_{11})\), \((u_{10}, u_{11})\) and \((u_{11}, v')\) are confirmed visually. This tour is exactly one traversal from v' to v that requires cost f.
• (3) Vertices are traversed in the order from v to \(u_5\) to \(u_7\) to \(u_8\) to \(u_9\) to \(u_6\) and to v, and are traversed in the order from v' to \(u_{10}\) to \(u_{11}\) and to v' (Figure 4 (iii)). In this case, arcs \((u_5, u_6)\), \((u_{10}, u_7)\) and \((u_9, u_{11})\) are confirmed visually. This tour is the composite subtours of the round trip where the origin-destination is v and the round trip where the origin-destination is v'. This tour requires the total cost \(e + g_1\).

(4) Vertices are traversed in the order from v to \(u_5\) to \(u_6\) and to v, and are traversed in the order from v' to \(u_{10}\) to \(u_7\) to \(u_8\) to \(u_9\) to \(u_{11}\) and to v' (Figure 4 (iv)). In this case, arcs \((u_5, u_7)\), \((u_9, u_6)\) and \((u_{10}, u_{11})\) are confirmed visually. As well as the tour (3), this tour is the composite subtours of the round trip where the origin-destination is v and the round trip where the origin-destination is v'. This tour requires the total cost \(f + g_2\).

Figure 4. Four tours in which every arc of \(\hat{G}_2\) is either traversed or confirmed visually.

The second graph we consider is generated by combining \(G_1=(V_1,A_1)\) and \(\hat{G}_2=(\hat{V}_2,\hat{A}_2)\). That is, we define a digraph \(G_2=(V_2,A_2)\), where \(V_2=V_1\cup\hat{V}_2\) and \(A_2=A_1\cup\hat{A}_2\). The cost function \(d_{G_2}\) is defined by \(d_{G_1}\) and \(d_{\hat{G}_2}\) directly. That is, \(d_{G_2}(a)=0\) if \(a\in A_1\) and \(d_{G_2}(a)=d_{\hat{G}_2}(a)\) if \(a\in\hat{A}_2\). We illustrate \(G_2\) in Figure 5 (i).

Figure 5. (i) Weighted digraph \(G_2\) which is called \(\zeta\)-edge \(\langle v, v' \rangle_{e,f,g}\) and (ii) its representation.

Suppose that \(\mathfrak{S}\) is any patrol route on a digraph including \(G_2\). Since all arcs in \(G_1\) must be traversed, based on four tours (1), (2), (3) and (4) on \(\hat{G}_2\) described above, tours on \(G_2\) for \(\mathfrak{S}\) can be classified:

• (1)′ The tour corresponding to (1) can be regarded as the composite of the following three subtours: (i) a tour traversed from v to u⁵ to u⁷ to u⁸ to u⁹ to u¹¹ and to v ′ , (ii) a tour traversed from v ′ to u³ to u⁴ and to v and (iii) a tour traversed from v to u¹ to u² and to v ′ . Then at the external vertex v, the number of out-going traversals is exactly one more than the number of in-going traversal. Conversely, at the another external vertex v ′ , the number of in-going traversals is exactly one more than the number of out-going traversal. From this fact, such tour on G² is said to be traversed from v to v ′ with cost e.
• (2)′ The tour corresponding to (2) can be regarded as the composite of the following three subtours: (i) a tour traversed from v ′ to u¹⁰ to u⁷ to u⁸ to u⁹ to u⁶ and to v, a tour traversed from v to u¹ to u² and to v ′ and (iii) a tour traversed from v ′ to u³ to u⁴ and v. Then at the external vertex v, the number of in-going traversals is exactly one more than the number of out-going traversal. Conversely, at the another external vertex v ′ , the number of out-going traversals is exactly one more than the number of in-going traversal. From this fact, such tour on G² is said to be traversed from v ′ to v with cost f.
• (3)′ The tour corresponding to (3) can be regarded as the composite of the following four subtours: (i) a tour traversed from v to u⁵ to u⁷ to u⁸ to u⁹ to u⁶ and to v, (ii) a tour traversed from v ′ to u10, u¹¹ and to v ′ , (iii) a tour traversed from v to u¹ to u² and to v ′ and (iv) a tour traversed from v ′ to u³ to u⁴ and v. Then at both external vertices v and v ′ , the number of in-going and out-going traversals are the same. Therefore, in this fact, such tour on G² is said to be traversed as a round trip between v and v ′ with cost e + g1.
• (4)′ The tour corresponding to (4) can be regarded as the composite of the following four subtours: (i) a tour traversed from v to u⁵ to u⁶ and to v, (ii) a tour traversed from v ′ to u10, to u7, to u8, to u9, to u¹¹ and to v ′ , (iii) a tour traversed from v to u¹ to u² and to v ′ and (iv) a tour traversed from v ′ to u³ to u⁴ and to v. Similarly to (3)′ , at both external vertices v and v ′ , the number of in-going and out-going traversals are the same. Therefore, such tour on G² is said to be traversed as a round trip between v and v ′ with cost f + g2.

Although both tours (3) and (4) on the digraph Gˆ ² consist of two separated subtours, we remark that on the digraph G2, these subtours are combined by the tours on the digraph G1. In the relation of the number of in-going and out-going traversals at the external vertices v and v ′ of G2, the tours (3)′ and (4)′ are equal. Therefore, when on G² choosing either tour traversed as a round trip between v and v ′ is selected, then one with smaller costs will be chosen. Hence, it is considered that there exists the following three tours on G2:

• (I) The tour traversed from v to v ′ with cost e.
• (II) The tour traversed from v ′ to v with cost f.
• (III) The tour traversed as a round trip between v and v ′ with cost g = min{e + g1, f + g2}.

We call the weighted digraph G² a ζ-edge and denote it by ⟨v, v′ ⟩e,f,g. The ζ-edge ⟨v, v′ ⟩e,f,g is illustrated in Figure 5 (ii). By putting (e, f, g1, g2) = (1, 1, 1, 1), we can construct ζ-edge ⟨v, v′ ⟩1,1,2.

Similarly, by putting (e, f, g1, g2) = (1, 2, 0, 0), ζ-edge ⟨v, v′ ⟩1,2,¹ can be constructed. We remark that ζ-edge ⟨v, v′ ⟩e,f,g can also be expressed as ⟨v ′ , v⟩f,e,g.

All digraphs that appear thereafter are represented using deemed edges. That is, in every weighted digraph G = (V, A), only external vertices are indicated in V and each element in A is indicated by ϵ-edges and ζ-edges. The cost function is given by subscripts of ζ-edges indirectly although it is not denoted by the form of the function dG. In the digraph represented in this way, multiple deemed edges may be included. In this case, for instance, if two ζ-edges ⟨v, v′ ⟩e,f,g are included, they are represented by ⟨v, v′ ⟩ [1] e,f,g and ⟨v, v′ ⟩ [2] e,f,g by adding superscript.

We show a property of the tours traversed three ζ-edges which are incident to the same vertex.

Lemma 2.1. Let G be any weighted digraph including three ζ-edges ⟨v, v1⟩1,1,2, ⟨v, v2⟩1,2,¹ and ⟨v, v3⟩2,1,¹ which are incident to a vertex v (see Figure 6). Suppose that only these three ζ-edges are incident to v. Then for any patrol route S on G, either of the following holds if all of these three ζ-edges must be traversed with cost 1:

• 1. ⟨v, v1⟩1,1,² is traversed from v¹ to v, ⟨v, v2⟩1,2,¹ is traversed as a round trip and ⟨v, v3⟩2,1,¹ is traversed from v to v3.
• 2. ⟨v, v1⟩1,1,² is traversed as a round trip, ⟨v, v2⟩1,2,¹ is traverse from v to v² and ⟨v, v3⟩2,1,¹ is traverse from v³ to v.

Figure 6. Three ζ-edges ⟨v, v1⟩1,1,2, ⟨v, v2⟩1,2,¹ and ⟨v, v3⟩2,1,¹ which are incident to a vertex v.

Proof. We obtain this assertion by considering the number of in-going and out-going traversals at v in S.

2.2. Two digraphs represented using deemed edges

Our proof of NP-completeness for DPOPP is to give that 3SAT is polynomial time reducible to DPOPP. In this section, we introduce two subgraphs represented using deemed edges corresponding to variables and clauses which appear in Boolean formula.

Let χ be a label and z be a natural number. A set of vertices V z χ and a set of ζ-edges A^z χ are defined as follows:

\[V_{\chi}^{z} = \begin{cases} \{\chi_{0}, \chi_{0}'\}, & \text{if } z = 0, \\ \{\chi_{i}, \chi_{i}' : 1 \le i \le z\}, & \text{otherwise,} \end{cases}\]

\[A_{\chi}^{z} = \begin{cases} \{\langle \chi_{0}, \chi_{0}' \rangle_{1,2,1}, \langle \chi_{0}, \chi_{0}' \rangle_{2,1,1}\}, & \text{if } z = 0, \\ \{\langle \chi_{i}, \chi_{i}' \rangle_{1,2,1} : 1 \leq i \leq z\} \cup \{\langle \chi_{i}', \chi_{i+1} \rangle_{1,1,2} : 1 \leq i < z\}, & \text{otherwise.} \end{cases}\]

Let x and \(\overline{x}\) be labels and let s and t be natural numbers with \(s+t\geq 1\). Then we define a weighted digraph \(G_x^{s,t}=(V_x^{s,t},A_x^{s,t})\), where \(V_x^{s,t}=V_x^s\cup V_{\overline{x}}^t\), \(A_x^{s,t}=A_x^s\cup A_{\overline{x}}^t\cup \hat{A}_x^{s,t}\). Here,

\[\hat{A}_x^{s,t} = \begin{cases} \{\langle x_0, \overline{x}_1 \rangle_{1,1,2}, \langle x_0', \overline{x}_t' \rangle_{1,1,2} \}, & \text{if } s = 0, \\ \{\langle x_1, \overline{x}_0 \rangle_{1,1,2}, \langle x_s', \overline{x}_0' \rangle_{1,1,2} \}, & \text{if } t = 0, \\ \{\langle x_1, \overline{x}_1 \rangle_{1,1,2}, \langle x_s', \overline{x}_t' \rangle_{1,1,2} \}, & \text{otherwise.} \end{cases}\]

Moreover, in order to show a property of \(G_x^{s,t}\), we introduce a weighted digraph \(\tilde{G}_x^{s,t}=(\tilde{V}_x^{s,t},\tilde{A}_x^{s,t})\) including the subgraph \(G_x^{s,t}\). Here,

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

and

\[\tilde{A}_{x}^{s,t} = A_{x}^{s,t} \cup \{\langle x_{i}, y_{i} \rangle_{2,1,1}, \langle x_{i}', y_{i}' \rangle_{1,2,1} : 1 \le i \le s\} \cup \{\langle \overline{x}_{i}, \overline{y}_{i} \rangle_{2,1,1}, \langle \overline{x}_{i}', \overline{y}_{i}' \rangle_{1,2,1} : 1 \le i \le t\},\]

where y is an arbitrary fixed label. For instance, we illustrate the weighted digraphs \(\tilde{G}_x^{s,t}\) with s, \(t \geq 1\) and \(\tilde{G}_x^{0,t}\) in Figure 7.

Figure 7. Weighted digraph \(\tilde{G}_x^{s,t}\) \((s,t\geq 1)\) and (ii) \(\tilde{G}_x^{0,t}\). Red part are \(G_x^{s,t}\) and \(G_x^{0,t}\).

For tours on this graph \(\tilde{G}_{x}^{s,t}\), we obtain the following lemma.

Lemma 2.2. Let G be a weighted digraph including a subgraph isomorphic to \(\tilde{G}_x^{s,t}\). Assume that only the vertices \(y_i\), \(y_i'\), \(\overline{y}_i\) and \(\overline{y}_i'\) have neighbors outside \(\tilde{V}_x^{s,t}\). If every deemed edge in G is only allowed tours with the cost one or less, then for any patrol route \(\mathfrak{S}\) on G, either of the following conditions is satisfied:

• (1) Every \(\zeta\)-edge \(\langle x_i, x_i' \rangle_{1,2,1}\) is traversed from \(x_i\) to \(x_i'\) and every \(\zeta\)-edge \(\langle \overline{x}_i, \overline{x}_i' \rangle_{1,2,1}\) is traversed as a round trip.
• (2) Every \(\zeta\)-edge \(\langle x_i, x_i' \rangle_{1,2,1}\) is traversed as a round trip and every \(\zeta\)-edge \(\langle \overline{x}_i, \overline{x}_i' \rangle_{1,2,1}\) is traversed from \(\overline{x}_i\) to \(\overline{x}_i'\).

Proof. Every vertex \(\hat{x}\) in \(V_x^{s,t}\) is incident to exactly three \(\zeta\)-edges. For instance, in the case of s, \(t \geq 1\), the vertex \(x_1\) is incident to three \(\zeta\)-edges \(\langle x_1, y_1 \rangle_{2,1,1}\), \(\langle x_1, x_1' \rangle_{1,2,1}\) and \(\langle x_1, \overline{x}_1 \rangle_{1,1,2}\). We remark that the edge-induced subgraph generated by the set of these three \(\zeta\)-edges to which \(\hat{x}\) is incident is isomorphic to the graph constructed in Lemma 2.1. Weighted digraphs \(\tilde{G}_x^{0,t}\) and \(\tilde{G}_x^{s,0}\) include edge-induced subgraphs which are isomorphic to the graph such that \(v_2 = v_3\) in Lemma 2.1.

We focus on the \(\zeta\)-edge \(\langle x_s', \overline{x}_t' \rangle_{1,1,2}\). Suppose that it is traversed from \(x_s'\) to \(\overline{x}_t'\) on \(\mathfrak{S}\). Since the way to traverse this edge is decided, by Lemma 2.1, the way to traverse the remaining two \(\zeta\)-edges incident to \(x_s'\) is also decided. That is, \(\langle x_s, x_s' \rangle_{1,2,1}\) must be traversed from \(x_s\) to \(x_s'\) and \(\langle x_s', y_s' \rangle_{1,2,1}\) must be traversed as a round trip (\(\langle x_0', x_0 \rangle_{1,2,1}\) is traversed as a round trip if s=0). Similarly, how to traverse the remaining two deemed edges which are incident to \(\overline{x}_t'\) can also be decided. That is, \(\langle \overline{x}_t, \overline{x}_t' \rangle_{1,2,1}\) must be traversed as a round trip and \(\langle \overline{x}_t', \overline{y}_t' \rangle_{1,2,1}\) must be traversed from \(\overline{x}_t'\) to \(\overline{y}_t'\) (\(\langle \overline{x}_0', \overline{x}_0 \rangle_{1,2,1}\) is traversed from \(\overline{x}_0'\) to \(\overline{x}_0\) if t=0). Moreover, the decision on how to traverse \(\langle x_s, x_s' \rangle_{1,2,1}\) and \(\langle \overline{x}_t, \overline{x}_t' \rangle_{1,2,1}\) determines how to traverse the remaining \(\zeta\) edges which are incident to \(x_s\) and \(\overline{x}_t\) is decided. By applying Lemma 2.1 repeatedly in this way, if \(\langle x_s', \overline{x}_t' \rangle_{1,1,2}\) is traversed from \(x_s'\) to \(\overline{x}_t'\), then we obtain the fact that every \(\zeta\)-edge \(\langle x_t, x_t' \rangle_{1,2,1}\) is traversed as a round trip. By a similar argument, we can verify that every \(\zeta\)-edge \(\langle x_t, x_t' \rangle_{1,2,1}\) is traversed as a round trip and every \(\zeta\)-edge \(\langle \overline{x}_t, \overline{x}_t' \rangle_{1,2,1}\) is traversed from \(\overline{x}_t'\) to \(\overline{x}_t'\) if \(\langle x_s', \overline{x}_t' \rangle_{1,2,1}\) is traversed from \(\overline{x}_t'\) to \(\overline{x}_t'\) if it raversed from \(\overline{x}_t'\) is traversed from \(\overline{x}_t'\) to \(\overline{x}_t'\) if it raversed from \(\overline{x}_t'\) is traversed from \(\overline{x}_t'\) to \(\overline{x}_t'\).

We remark that the weighted digraph \(G_x^{s,t}\) consists of 2(s+t) \(\zeta\)-edges if \(s,t\geq 1\), and \(G_x^{s,0}\) and \(G_x^{0,t}\) consist of 2s+3 and 2t+3 \(\zeta\)-edges, respectively.

Let C be a label and p, q and r be fixed labels determined by C. Then we define a weighted digraph \(G_C = (V_C, A_C)\), where

\[V_C = \{p_j, q_j : 1 \le j \le 3\} \cup \{r_1, r_2\},\] \[A_C = \{\langle r_1, p_j \rangle_{1,2,1}, \langle q_j, r_2 \rangle_{1,2,1} : 1 \le j \le 3\} \cup \{\langle r_1, r_2 \rangle_{2,1,1}^{[1]}, \langle r_1, r_2 \rangle_{2,1,1}^{[2]}\}.\]

Moreover, in order to describe a property of \(G_C\), we define a weighted digraph \(\tilde{G}_C = (\tilde{V}_C, \tilde{A}_C)\) which contains \(G_C\) as a subgraph. Here,

\[\tilde{V}_C = V_C \cup \{p'_j, q'_j : 1 \le j \le 3\},\] \[\tilde{A}_C = A_C \cup \{\langle p_j, q_j \rangle_{1,2,1}, \langle p_j, p'_j \rangle_{1,1,2}, \langle q_j, q'_j \rangle_{1,1,2} : 1 \le j \le 3\}.\]

We illustrate \(\tilde{G}_C\) and its subgraph \(G_C\) in Figure 8. We obtain the following property for \(\tilde{G}_C\).

Figure 8. Weighted digraph \(\tilde{G}_C\) and its subgraph \(G_C\) (red part).

Lemma 2.3. Let G be a weighted digraph with \(\tilde{G}_C\) as a subgraph. Suppose that only the vertices \(p'_j\) and \(q'_j\) have neighbors outside \(\tilde{V}_C\). If every deemed edge in G is only allowed tours with the cost one or less, then for any patrol route \(\mathfrak{S}\) on G, at least one of the three \(\zeta\)-edges \(\langle p_j, q_j \rangle_{1,2,1}\) must be traversed from \(p_j\) to \(q_j\).

Proof. Since for any vertex v in \(\{p_j, q_j : 1 \le j \le 3\}\) there exist three vertices \(v_1, v_2\) and \(v_3\) in \(\tilde{V}_C\) such that three \(\zeta\)-edges \(\langle v, v_1 \rangle_{2,1,1}, \langle v, v_2 \rangle_{1,2,1}\) and \(\langle v, v_3 \rangle_{1,1,2}\) are in \(\tilde{A}_C\), by Lemma 2.1, if the way to traverse one of these three \(\zeta\)-edges is decided, the way to traverse the others is also decided, accordingly. Specifically, if \(\langle p_j, q_j \rangle_{1,2,1}\) is traversed from \(p_j\) to \(q_j\), then:

• \(\langle r_1, p_j \rangle_{1,2,1}\) must be traversed as a round trip and \(\langle p_j, p_j' \rangle_{1,1,2}\) must be traversed from \(p_j'\) to \(p_j\);
• \(\langle q_j, r_2 \rangle_{1,2,1}\) must be traversed as a round trip and \(\langle q_j, q'_j \rangle_{1,1,2}\) must be traversed from \(q_j\) to \(q'_j\). Similarly, if \(\langle p_j, q_j \rangle_{1,2,1}\) is traversed as a round trip, then:
• \(\langle r_1, p_j \rangle_{1,2,1}\) must be traversed from \(r_1\) to \(p_j\) and \(\langle p_j, p_j' \rangle_{1,1,2}\) must be traversed from \(p_j\) to \(p_j'\);
• \(\langle q_j, r_2 \rangle_{1,2,1}\) must be traversed from \(q_j\) to \(r_2\) and \(\langle q_j, q'_j \rangle_{1,1,2}\) must be traversed from \(q'_j\) to \(q_j\).

Suppose that \(k \zeta\)-edges \(\langle p_j, q_j \rangle_{1,2,1}\) are traversed from \(p_j\) to \(q_j\) on \(\mathfrak{S}\) (the remaining \(3-k \zeta\)-edges \(\langle p_j, q_j \rangle_{1,2,1}\) are traversed as round trips). Then, by the relation between the number of in-going and out-going traversals at \(r_1\) and \(r_2\), the following statements hold:

• (i) if k=3, for each j (\(1 \le j \le 3\)), both \(\langle r_1, p_j \rangle_{1,2,1}\) and \(\langle q_j, r_2 \rangle_{1,2,1}\) must be traversed as a round trip. In this case, it is necessary that both \(\langle r_1, r_2 \rangle_{2,1,1}^{[1]}\) and \(\langle r_1, r_2 \rangle_{2,1,1}^{[2]}\) are traversed as a round trip.
• (ii) if k=2 then, for exactly one value of j (\(1 \le j \le 3\)), \(\langle r_1, p_j \rangle_{1,2,1}\) and \(\langle q_j, r_2 \rangle_{1,2,1}\) must be traversed from \(r_1\) to \(p_j\) and from \(q_j\) to \(r_2\), respectively. For the two remaining values of j, both \(\langle r_1, p_j \rangle_{1,2,1}\) and \(\langle q_j, r_2 \rangle_{1,2,1}\) must be traversed as round trips. In this case, it is necessary that one of \(\langle r_1, r_2 \rangle_{2,1,1}^{[1]}\) and \(\langle r_1, r_2 \rangle_{2,1,1}^{[2]}\), for example \(\langle r_1, r_2 \rangle_{2,1,1}^{[1]}\) is traversed from \(r_2\) to \(r_1\) and another \(\zeta\)-edge \(\langle r_1, r_2 \rangle_{2,1,1}^{[2]}\) is traversed as a round trip.
• (iii) if k=1, for exactly two values of j (\(1 \le j \le 3\)), \(\langle r_1, p_j \rangle_{1,2,1}\) and \(\langle q_j, r_2 \rangle_{1,2,1}\) must be traversed from \(r_1\) to \(p_j\) and from \(q_j\) to \(r_2\), respectively. For the remaining value of j, both \(\langle r_1, p_j \rangle_{1,2,1}\) and \(\langle q_j, r_2 \rangle_{1,2,1}\) must be traversed as round trips. In this case, both \(\langle r_1, r_2 \rangle_{2,1,1}^{[1]}\) and \(\langle r_1, r_2 \rangle_{2,1,1}^{[2]}\) are traversed from \(r_2\) to \(r_1\).
• (iv) If k=0, that is, all three \(\zeta\)-edges \(\langle p_j,q_j\rangle_{1,2,1}\) are traversed as round trips, then for each j \((1\leq j\leq 3),\ \langle r_1,p_j\rangle_{1,2,1}\) and \(\langle q_j,r_2\rangle_{1,2,1}\) must be traversed from \(r_1\) to \(p_j\) and from \(q_j\) to \(r_2\), respectively. In this case, no matter how \(\langle r_1,r_2\rangle_{2,1,1}^{[1]}\) and \(\langle r_1,r_2\rangle_{2,1,1}^{[2]}\) are traversed, the number of in-going and out-going traversals at \(r_1\) (at \(r_2\) similarly) cannot be equal. Hence, there exists no patrol route on G such that all three \(\zeta\)-edges \(\langle p_j,q_j\rangle_{1,2,1}\) are traversed as round trips.

We remark that the weighted digraph \(G_C\) consists of 8 \(\zeta\)-edges.

3. NP-completeness of the Police Officer Patrol Problem on weighted digraphs

Theorem 3.1. DPOPP is NP-complete.

Proof. Let G = (V, A) be a connected simple digraph, \(d_G : A \to \mathbb{N}\) be a cost function and w be a natural number. DPOPP is in NP, since it can be verified in polynomial time whether or not \(\mathfrak{S}\) is a patrol route with cost w or less for a given sequence \(\mathfrak{S}\) of vertices in G. Therefore, in order to show that DPOPP is NP-complete, we need only show that 3SAT (cf. [2]) is reducible to DPOPP in polynomial time. For any Boolean formula F in 3-conjunctive normal form, we show that a weighted digraph \(G_F\) and a natural number w which satisfies the following condition can be constructed in polynomial time:

F is satisfiable \(\iff\) \(G_F\) has a patrol route with cost w or less.

Let \(F=C_1\cdot C_2\cdot \cdots \cdot C_m\) be a Boolean formula in 3-conjunctive normal form with n variables \(x_1,x_2,\cdots,x_n\), where \(C_i=c_{i1}+c_{i2}+c_{i3}\) \((1\leq i\leq m)\) and each \(c_{ij}\) \((1\leq j\leq 3)\) is either a variable or its negation. Let \(s_k\) and \(t_k\) be the numbers of appearances of \(x_k\) and \(\overline{x}_k\) in F, respectively. For any k \((1\leq k\leq n)\), \(s_k+t_k\geq 1\) holds, since F contains at least one \(x_k\) or \(\overline{x}_k\). Moreover, we assume that \(s_k\) literals \(c_{i_{k,1}j_{k,1}}, c_{i_{k,2}j_{k,2}}, \ldots, c_{i_{k,s_k}j_{k,s_k}}\) are equal to \(x_k\), and \(t_k\) literals \(c_{i'_{k,1}j'_{k,1}}, c_{i'_{k,2}j'_{k,2}}, \ldots, c_{i'_{k,t_k}j'_{k,t_k}}\) are equal to \(\overline{x}_k\) Suppose that their indices satisfy the following conditions:

• \(i_{k,1} \le i_{k,2} \le \cdots \le i_{k,s_k}\) and \(j_{k,l} < j_{k,l+1}\) if \(i_{k,l} = i_{k,l+1}\),
• \(i'_{k,1} \le i'_{k,2} \le \cdots \le i'_{k,t_k}\) and \(j'_{k,l} < j'_{k,l+1}\) if \(i'_{k,l} = i'_{k,l+1}\).

We construct a weighted digraph \(G_F = (V_F, A_F)\) from the formula F. Here, \(G_F\) contains the following two kinds of subgraphs:

• \(G^{s_k,t_k}_{x_k}=(V^{s_k,t_k}_{x_k},A^{s_k,t_k}_{x_k})\) corresponding to each variable \(x_k\) \((1 \le k \le n)\). \(G^{s_k,t_k}_{x_k}\) is the subgraph of the weighted digraph \(\tilde{G}^{s_k,t_k}_{x_k}\) treated in Lemma 2.2.
• \(G_{C_i} = (V_{C_i}, A_{C_i})\) corresponding to each clause \(C_i\) \((1 \le i \le m)\). Here,

\[V_{C_i} = \{ p_{i,j}, q_{i,j} : 1 \le j \le 3 \} \cup \{ r_{i,1}, r_{i,2} \},\]

\[A_{C_i} = \{ \langle r_{i,1}, p_{i,j} \rangle_{1,2,1}, \langle q_{i,j}, r_{i,2} \rangle_{1,2,1} : 1 \le j \le 3 \} \cup \{ \langle r_{i,1}, r_{i,2} \rangle_{2,1,1}^{[1]}, \langle r_{i,1}, r_{i,2} \rangle_{2,1,1}^{[2]} \}.\]

We remark that \(G_{C_i}\) is isomorphic to the weighted digraph \(G_C\) treated in Lemma 2.3.

We combine n weighted digraphs \(G_{x_k}^{s_k,t_k}\) and m weighted digraphs \(G_{C_i}\) by equating external vertices in \(G_{x_k}^{s_k,t_k}\) with external vertices in \(G_{C_i}\) as follows: For each k \((1 \le k \le n)\),

• if \(s_k > 0\) then for each l \((1 \le l \le s_k)\), the vertices \(x_{k,l}\) and \(x'_{k,l}\) in the subgraph \(G^{s_k,t_k}_{x_k}\) are equated with the vertices \(p_{i_{k,l},j_{k,l}}\) and \(q_{i_{k,l},j_{k,l}}\) in the subgraph \(G_{C_{i_{k,l}}}\), respectively.
• if \(t_k > 0\) then for each l \((1 \le l \le t_k)\), the vertices \(\overline{x}_{k,l}\) and \(\overline{x}'_{k,l}\) in the subgraph \(G^{s_k,t_k}_{x_k}\) are equated with the vertices \(p_{i'_{k,l},j'_{k,l}}\) and \(q_{i'_{k,l},j'_{k,l}}\) in the subgraph \(G_{C_{i'_{k,l}}}\), respectively.

These equated vertices have two labels (for example, \(x_{k,l}\) and \(p_{i_{k,l},j_{k,l}}\)), and we use these labels interchangeably according to convenience. Therefore, for instance, if vertices \(x_{k,l}\) and \(x'_{k,l}\) (or \(\overline{x}_{k,l}\) and \(\overline{x}'_{k,l}\)) in \(G^{s_k,t_k}_{x_k}\) are equated with vertices \(p_{i_{k,l},j_{k,l}}\) and \(q_{i_{k,l},j_{k,l}}\) in \(G_{C_{i_{k,l}}}\), respectively, then \(\zeta\)-edge \(\langle x_{k,l}, x'_{k,l} \rangle_{1,2,1}\) (or \(\langle \overline{x}_{k,l}, \overline{x}'_{k,l} \rangle_{1,2,1}\)) is sometimes represented by \(\langle p_{i_{k,l},j_{k,l}}, q_{i_{k,l},j_{k,l}} \rangle_{1,2,1}\).

The set of external vertices \(V_F\) and the set of deemed edges \(A_F\) of \(G_F\) are defined as follows:

\[\begin{split} V_F &= \left(\bigcup_{k=1}^n V_{x_k}^{s_k,t_k}\right) \bigcup \left(\bigcup_{i=1}^m V_{C_i}\right), \\ A_F &= \left(\bigcup_{k=1}^n A_{x_k}^{s_k,t_k}\right) \bigcup \left(\bigcup_{i=1}^m A_{C_i}\right) \cup \left\{\langle r_i, r_{i+1}\rangle : 1 \leq i < m\right\}. \end{split}\]

The vertices \(r_{i,1}\) in \(G_{C_i}\) and \(r_{i+1,1}\) in \(G_{C_{i+1}}\) are connected by the \(\epsilon\)-edge \(\langle r_{i,1}, r_{i+1,1} \rangle\). Since all \(\epsilon\)-edges must be traversed as round trips, these have no effect on the relationship between the numbers of in-going and out-going traversals at their external vertices. Therefore, we can apply Lemma 2.3 for every subgraph in \(G_F\) which is isomorphic to the graph \(\tilde{G}_C\) constructed in Lemma 2.3. The role of \(\epsilon\)-edges is to guarantee that \(G_F\) is connected.

For instance, we consider the Boolean formula \(F = (\overline{x}_1 + x_2 + x_3)(x_1 + \overline{x}_2 + x_4)(\overline{x}_1 + x_3 + \overline{x}_4)\). We illustrate the weighted digraph \(G_F\) constructed from to F in Figure 9. Since the two literals \(c_{11}\)

Figure 9. The graph \(G_F\) constructed from a three conjunctive normal Boolean formula \(F = (\overline{x}_1 + x_2 + x_3)(x_1 + \overline{x}_2 + x_4)(\overline{x}_1 + x_3 + \overline{x}_4)\).

and \(c_{31}\) in F are equal to \(\overline{x}_1\) (that is, \(i_{1,1}=1\), \(j_{1,1}=1\), \(i_{1,2}=3\) and \(j_{1,2}=1\)), the vertices \(\overline{x}_{1,1}\) and \(\overline{x}'_{1,1}\) in \(G^{2,1}_{\overline{x}_1}\) are equated with the vertices \(p_{i_{1,1},j_{1,1}}(=p_{1,1})\) and \(q_{i_{1,1},j_{1,1}}(=q_{1,1})\) in \(G_{C_{i_{1,1}}}(=G_{C_1})\), respectively, and \(\overline{x}_{1,2}\) and \(\overline{x}'_{1,2}\) in \(G^{2,1}_{\overline{x}_1}\) are equated with \(p_{i_{1,2},j_{1,2}}(=p_{3,1})\) and \(q_{i_{1,2},j_{1,2}}(=q_{3,1})\) in \(G_{C_{i_{1,2}}}(=G_{C_3})\), respectively. Thus, vertices of \(G_{x_k}\) are equated with vertices of \(G_{C_i}\) as follows:

\[\overline{x}_{1,1} = p_{1,1}, \ \overline{x}'_{1,1} = q_{1,1}, \quad x_{2,1} = p_{1,2}, \ x'_{2,1} = q_{1,2}, \quad x_{3,1} = p_{1,3}, \ x'_{3,1} = q_{1,3},\] \(x_{1,1} = p_{2,1}, \ x'_{1,1} = q_{2,1}, \quad \overline{x}_{2,1} = p_{2,2}, \ \overline{x}'_{2,1} = q_{2,2}, \quad x_{4,1} = p_{2,3}, \ x'_{4,1} = q_{2,3},\) \(\overline{x}_{1,2} = p_{3,1}, \ \overline{x}'_{1,2} = q_{3,1}, \quad x_{3,2} = p_{3,2}, \ x'_{3,2} = q_{3,2}, \quad \overline{x}_{4,1} = p_{3,3}, \ \overline{x}'_{4,1} = q_{3,3}.\)

We remark that \(G_F\) includes subgraphs which are isomorphic to \(\tilde{G}_{x_k}^{s_k,t_k}\) and \(\tilde{G}_{C_i}\) for each variable \(x_k\) and clause \(C_i\), respectively. For instance, in the graph \(G_F\) constructed from the formula \(F=(\overline{x}_1+x_2+x_3)(x_1+\overline{x}_2+x_4)(\overline{x}_1+x_3+\overline{x}_4)\), the graph which adds the following six \(\zeta\)-edges to \(G_{x_1}^{1,2}\) is isomorphic to \(\tilde{G}_{x_1}^{1,2}\):

\[\langle r_{1,1}, \overline{x}_{1,1} \rangle_{1,2,1}, \langle \overline{x}'_{1,1}, r_{1,2} \rangle_{1,2,1}, \langle r_{2,1}, x_{1,1} \rangle_{1,2,1}, \langle x'_{1,1}, r_{2,2} \rangle_{1,2,1}, \langle r_{3,1}, \overline{x}_{1,2} \rangle_{1,2,1}, \langle \overline{x}'_{1,2}, r_{3,2} \rangle_{1,2,1}.\]

On the other hand, the graph which adds the following six \(\zeta\)-edges to \(G_{C_1}\) is isomorphic to \(\tilde{G}_{C_1}\):

\[\langle \overline{x}_{1,1}, x_{1,1} \rangle_{1,1,2}, \langle \overline{x}'_{1,1}, \overline{x}_{1,2} \rangle_{1,1,2}, \langle x_{2,1}, \overline{x}_{2,1} \rangle_{1,1,2}, \langle x'_{2,1}, \overline{x}'_{2,1} \rangle_{1,1,2}, \langle x_{3,1}, \overline{x}_{3,0} \rangle_{1,1,2}, \langle x'_{3,1}, x_{3,2} \rangle_{1,1,2}.\]

Finally we define the natural number w as the numbers of \(\zeta\)-edges in \(G_F\). The weighted digraph \(G^{s_k,t_k}_{x_k}\) \((1 \leq k \leq n)\) consists of \(2(s_k+t_k)+3(s_k'+t_k')\) \(\zeta\)-edges, where

\[s'_k = \begin{cases} 1, & \text{if } s_k = 0, \\ 0, & \text{otherwise} \end{cases} \quad \text{and} \quad t'_k = \begin{cases} 1, & \text{if } t_k = 0, \\ 0, & \text{otherwise}. \end{cases}\]

On the other hand, each weighted digraph \(G_{C_i}\) \((1 \le i \le m)\) has \(8 \zeta\)-edges. In addition, since F is the Boolean formula in 3-conjunctive normal form with m clauses, the number of literals \(\sum_{k=1}^{n} (s_k + t_k)\) is equal to 3m. Hence, we define w as follows:

\[w = 2\sum_{k=1}^{n} (s_k + t_k) + 3\sum_{k=1}^{n} (s'_k + t'_k) + 8m = 14m + 3\sum_{k=1}^{n} (s'_k + t'_k).\]

It is obvious that the weighted digraph \(G_F\) and the natural number w can be constructed from F in polynomial time. Therefore, it only remains for us to show that F is satisfiable if and only if \(G_F\) has a patrol route with cost w or less.

Let \(I:\{x_1,x_2,\ldots,x_n\}\to\{0,1\}\) be a truth assignment of F. Then the \(\zeta\)-edge \(\langle x'_{k,s},\overline{x}'_{k,t}\rangle_{1,1,2}\) in the subgraph \(G^{s_k,t_k}_{x_k}\) is traversed from \(x'_{k,s}\) to \(\overline{x}'_{k,t}\) if \(I(x_k)=1\), and is traversed from \(\overline{x}'_{k,t}\) to \(x'_{k,s}\) if \(I(x_k)=0\). By Lemma 2.2, if \(I(x_k)=1\) then every \(\zeta\)-edge \(\langle x_{k,l},x'_{k,l}\rangle_{1,2,1}\) is traversed from \(x_{k,l}\) to \(x'_{k,l}\) and every \(\zeta\)-edge \(\langle \overline{x}_{k,l},\overline{x}'_{k,l}\rangle_{1,2,1}\) is traversed as a round trip. Similarly, if \(I(x_k)=0\) then every \(\zeta\)-edge \(\langle x_{k,l},x'_{k,l}\rangle_{1,2,1}\) is traversed as a round trip and every \(\zeta\)-edge \(\langle \overline{x}_{k,l},\overline{x}'_{k,l}\rangle_{1,2,1}\) is traversed from \(\overline{x}_{k,l}\) to \(\overline{x}'_{k,l}\). Additionally, by Lemma 2.2, each \(G^{s_k,t_k}_{x_k}\) has no other valid edge tour.

We assume that F is satisfiable. Then, there exists a truth assignment I by which F is satisfied. In this case, at least one among \(c_{h1}\), \(c_{h2}\) and \(c_{h3}\) is satisfied for every h (\(1 \le h \le m\)). Now, suppose that \(c_{hh'}\) is satisfied under this assignment. If \(c_{hh'} = x_k\) (or \(\overline{x}_k\)), then the corresponding \(\zeta\)-edge \(\langle x_{k,l}, x'_{k,l} \rangle_{1,2,1}\) (or \(\langle \overline{x}_{k,l}, \overline{x}'_{k,l} \rangle_{1,2,1}\)), that is, \(\langle p_{h,h'}, q_{h,h'} \rangle_{1,2,1}\) is traversed from \(p_{h,h'}\) to \(q_{h,h'}\) (We remark that \(h = i_{k,l}, h' = j_{k,l}\)). Edges in \(G_{C_h}\) can be traversed in the way described in the proof of Lemma 2.3. In addition, all \(\epsilon\)-edges can be traversed as round trips. Such an edge tour constitutes a patrol route of \(G_F\) on which every \(\zeta\)-edge is traversed with cost 1.

Conversely, suppose that \(G_F\) has a patrol route \(\mathfrak{S}\) with cost w. Since \(G_F\) has w \(\zeta\)-edges, every \(\zeta\)-edge must be traversed with cost 1. Then by the way of constructing the weighted digraph \(G_F\) and Lemma 2.2, we can define a truth assignment \(I_{\mathfrak{S}}: \{x_1, x_2, ..., x_n\} \to \{0, 1\}\) uniquely for the patrol route \(\mathfrak{S}\) on which every \(\zeta\)-edge is traversed with cost 1 as follows:

(1) \(I_{\mathfrak{S}}(x_k) = 1\) if every \(\zeta\)-edge \(\langle p_{i_{k,l},j_{k,l}}, q_{i_{k,l},j_{k,l}} \rangle_{1,2,1}\) corresponding to \(s_k\) literals \(c_{i_{k,1},j_{k,1}}, c_{i_{k,2},j_{k,2}}, \ldots, c_{i_{k,s_k},j_{k,s_k}}\) which are equal to \(x_k\) is traversed from \(p_{i_{k,l},j_{k,l}}\) to \(q_{i_{k,l},j_{k,l}}\) (\(\langle x_{k,0}, x'_{k,0} \rangle_{1,2,1}\) is traversed from \(x_{k,0}\) to \(x'_{k,0}\) if \(s_k = 0\)).

(2) \(I_{\mathfrak{S}}(x_k) = 0\) if every \(\zeta\)-edge \(\langle p_{i'_{k,l},j'_{k,l}}, q_{i'_{k,l},j'_{k,l}} \rangle_{1,2,1}\) corresponding to \(t_k\) literals \(c_{i'_{k,1},j'_{k,1}}, c_{i'_{k,2},j'_{k,2}}, \ldots, c_{i'_{k,t_k},j'_{k,t_k}}\) which are equal to \(\overline{x}_k\) is traversed from \(p_{i',j'}\) to \(q_{i',j'}\) (\(\langle \overline{x}_{k,0}, \overline{x}'_{k,0} \rangle_{1,2,1}\) is traversed from \(\overline{x}_{k,0}\) to \(\overline{x}'_{k,0}\) if \(t_k = 0\)).

Assume that for each i \((1 \le i \le m)\), a \(\zeta\)-edge \(\langle p_{i,j_i}, q_{i,j_i} \rangle_{1,2,1}\) \((1 \le j_i \le 3)\) is traversed from \(p_{i,j_i}\) to \(q_{i,j_i}\) on the patrol route \(\mathfrak{S}\). The existence of such \(\zeta\)-edge is guaranteed by Lemma 2.3. Let \(c_{ij_i}\) be the literal corresponding to the \(\zeta\)-edge \(\langle p_{i,j_i}, q_{i,j_i} \rangle_{1,2,1}\). If the literal \(c_{ij_i}\) is equal to \(x_k\) then \(I_{\mathfrak{S}}(c_{ij_i}) = I_{\mathfrak{S}}(x_k) = 1\). On the other hand, if the literal \(c_{ij_i}\) is equal to \(\overline{x}_k\) then \(I_{\mathfrak{S}}(c_{ij_i}) = I_{\mathfrak{S}}(\overline{x}_k) = 1\) since \(I_{\mathfrak{S}}(x_k) = 0\). Hence, F is satisfiable since every clause \(C_i = c_{i1} + c_{i2} + c_{i3}\) is satisfied by \(I_{\mathfrak{S}}\).

References

• [1] K. Akoudad and F. Jawab, Recent survey on bases routing problems: CPP, RPP and CARP, International Journal of Engineering Research & Technology 2 (2013), 3652–3668.
• [2] S.A. Cook, The complexity of theorem-proving procedures, STOC '71, Proceedings of the third annual ACM symposium on Theory of computing (1971), 151–158. DOI: 10.1145/800157.805047.
• [3] J. Edmonds and E.L. Johnson, Matching, Euler tours and the chinese postman, Math. Programming 5(1) (1973), 88–124. DOI: 10.1007/BF01580113.
• [4] M.R. Garey and D.S. Johnson, The rectilinear Steiner tree problem is NP-complete, SIAM Journal on Applied Mathematics, 32(4) (1977), 826–834. DOI: 10.1137/0132071.
• [5] R.M. Karp, Reducibility among combinatorial problems, R.E. Miller and J.W. Thatcher, Complexity of Computer Computations (1972), 85–103, Plenum Press. DOI: 10.1007/978-1-4684-2001-2_9.
• [6] J.K. Lenstra and A.H.G Rinnooy-Kan, On general routing problems, Networks, 6 (1976), 273–280. DOI: 10.1002/net.3230060305.
• [7] J.K. Lenstra and A.H.G. Rinnooy-Kan, Complexity of vehicle routing and scheduling problems, Networks 11 (1981), 221–227. DOI: 10.1002/net.3230110211.
• [8] K. Mei-Ko, Graphic programming using odd or even points, Chinese Math. 1 (1962), 237–277.
• [9] C.H. Papadimitriou, On the complexity of edge traversing, J. Assoc. Comput. Mach. 23(3) (1976), 544–554. DOI: 10.1145/321958.321974.
• [10] Ö. Ç. Sökmen, Ş. Emeç, M. Yilmaz, and G. Akkaya, An overview of Chinese postman problem, 3rd International Conference on Advanced Engineering Technologies 10 (2019).
• [11] H. Tohyama and A. Adachi, Complexity of a restricted chinese postman problem, Trans. IPS. Japan 37(11) (1996), 1886–1896.

[12] H. Tohyama and M. Tomisawa, Complexity of the police officer patrol problem, Journal of Information Processing 30 (2022), 307–314. DOI: 10.2197/ipsjjip.30.307.