04.09.2020  Ausgabe 4/2020 Open Access
Some algorithmic results for finding compatible spanning circuits in edgecolored graphs
 Zeitschrift:
 Journal of Combinatorial Optimization > Ausgabe 4/2020
Wichtige Hinweise
Supported by NSFC (Nos. 11671320 and U1803263), CSC (No. 201806290049) and the Fundamental Research Funds for the Central Universities (Nos. 31020180QD124 and 3102019ghjd003)
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
In this paper we consider only finite undirected simple graphs. For terminology and notations not defined here, we refer the reader to the textbook of Bondy and Murty (
2008).
Let
G be a graph. We use
V(
G) and
E(
G) to denote the vertex set and edge set of
G, respectively. For a vertex
v of
G, we denote by
\(E_G(v)\) the set of edges of
G incident with
v, and we denote by
\(N_G(v)\) the set of neighbors of
v in
G. The
degree of a vertex
v in a graph
G, denoted by
\(d_G(v)\), is defined to be the cardinality of
\(E_G(v)\). We write
\(\Delta (G)=\max \{d_G(v)\mid v\in V(G)\}\). If no ambiguity can arise, we will denote
\(E_G(v)\),
\(N_G(v)\) and
\(d_G(v)\) by
E(
v),
N(
v) and
d(
v), respectively.
Anzeige
A
spanning circuit in a graph
G is defined as a closed trail that visits (contains) each vertex of
G. A
Hamilton cycle of
G refers to a spanning circuit visiting each vertex of
G exactly once; an
Euler tour of
G refers to a spanning circuit traversing each edge of
G. Hence, a spanning circuit is a common relaxation of a Hamilton cycle and an Euler tour. A graph is said to be
hamiltonian if it contains a Hamilton cycle, and a graph is said to be
eulerian if it admits an Euler tour.
An
edgecoloring of a graph
G is defined as a mapping
\(c: E(G)\rightarrow \mathbb {N}\), where
\(\mathbb {N}\) is the set of natural numbers. An
edgecolored graph refers to a graph with a fixed edgecoloring. Two edges of a graph are said to be
consecutive with respect to a trail (with a fixed orientation) if they are traversed consecutively along the trail. A
compatible spanning circuit in an edgecolored graph refers to a spanning circuit in which any two consecutive edges have distinct colors. An edgecolored graph is said to be
properly colored if any two adjacent edges (i.e., edges sharing exactly one end vertex) of the graph have distinct colors, and an edgecolored graph is
rainbow if each pair of edges of the graph has distinct colors. Thus, a compatible Hamilton cycle is properly colored, and a properly colored spanning circuit is compatible. Conversely, a compatible spanning circuit is obviously not necessarily properly colored. Thus, a compatible spanning circuit can be viewed as a generalization of a properly colored spanning circuit. Compatible spanning circuits are of interest in graph theory applications, for example, in genetic and molecular biology (Pevzner
2000; Szachniuk et al.
2014,
2009), in the design of printed circuits and wiring boards (Tseng et al.
2010), and in channel assignment of wireless networks (Ahuja
2010; Sankararaman et al.
2014).
Let
G be an edgecolored graph. We use
c(
e) to denote the color appearing on the edge
e of
G, and we use
C(
G) to denote the set of colors appearing on the edges of
G. Let
\(d_G^i(v)\) denote the cardinality of the set
\(\{e\in E_G(v)\mid c(e)=i\}\) for a vertex
\(v\in V(G)\) and a color
\(i\in C(G)\). We let
\(\Delta _G^{mon}(v)=\max \{d_G^i(v)\mid i\in C(G)\}\) for a vertex
\(v\in V(G)\), and we let
\(\Delta ^{mon}(G)=\max \{\Delta _G^{mon}(v)\mid v\in V(G)\}\); these two parameters are called the
maximum monochromatic degree of a vertex
v of
G and the
maximum monochromatic degree of an edgecolored graph
G, respectively. The
color degree of a vertex
v of an edgecolored graph
G, denoted by
\(cd_G(v)\), is defined to be the number of colors appearing on the edges of
G incident with
v. When no confusion can arise, we will use
\(d^i(v)\),
\(\Delta ^{mon}(v)\) and
cd(
v) instead of
\(d_G^i(v)\),
\(\Delta _G^{mon}(v)\) and
\(cd_G(v)\), respectively.
From a sufficient condition perspective, the existence of two kinds of extremal compatible spanning circuits, i.e., compatible Hamilton cycles and compatible Euler tours in specific edgecolored graphs has been studied extensively. For more details on the topic, we refer the reader to Alon and Gutin (
1997), Bollobás and Erdős (
1976), Chen and Daykin (
1976), Daykin (
1976), Fleischner and Fulmek (
1990), Kotzig (
1968), Lo (
2016) and Shearer (
1979). On the other hand, Benkouar et al. (
1996), from an algorithmic perspective, considered the existence of compatible Euler tours in edgecolored eulerian graphs. Benkouar et al. (
1996) provided a polynomialtime algorithm for finding a compatible Euler tour in an edgecolored eulerian graph
G in which
\(\Delta ^{mon}(v)\le d(v)/2\) for each vertex
v of
G. Independently, Pevzner (
1995) described a similar algorithm for solving the same problem.
Anzeige
In recent work (Guo et al.
2020a,
b), sufficient conditions for the existence of more general compatible spanning circuits (i.e., not necessarily a compatible Hamilton cycle or Euler tour) in specific edgecolored graphs have been established.
In this paper, we consider the existence of compatible spanning circuits in edgecolored graphs from an algorithmic perspective. We first prove the following complexity result by a simple reduction from a result due to Garey et al. (
1974).
Theorem 1.1
The decision problem of determining whether an edgecolored connected graph contains a compatible spanning circuit is NPcomplete.
We postpone the proofs of all our results in order not to interrupt the flow of the narrative. Motivated by the above NPcompleteness result, we consider the existence of compatible spanning circuits in specific classes of edgecolored graphs from an algorithmic perspective, and we analyze the complexity of the associated algorithms.
A number of sufficient conditions for the existence of compatible Hamilton cycles in edgecolored complete graphs have been obtained (see Alon and Gutin
1997; Bollobás and Erdős
1976; Chen and Daykin
1976; Daykin
1976; Lo
2016; Shearer
1979). In particular, Bollobás and Erdős (
1976) considered the problem and proposed the following conjecture on the existence of compatible Hamilton cycles in edgecolored complete graphs back in the 1970s (see Conjecture
1.1). Recently, Lo (
2016) proved that this conjecture is true asymptotically. Throughout the rest of this paper, we use
\(K^c_{n}\) to denote an edgecolored complete graph on
n vertices, where
\(n\ge 3\).
Conjecture 1.1
(Bollobás and Erdős
1976) If
\(\Delta ^{mon}(K^c_{n})<\lfloor n/2\rfloor \), then
\(K^c_{n}\) contains a compatible Hamilton cycle.
In the rest of this paper, we first deal with the existence of compatible spanning circuits (with no restrictions) in graphs
\(K^c_{n}\) with
\(\Delta ^{mon}(K^c_{n})\le \lfloor (n1)/2\rfloor \), as follows.
Theorem 1.2
If
\(\Delta ^{mon}(K^c_{n})\le \lfloor (n1)/2\rfloor \), then
\(K^c_{n}\) contains a compatible spanning circuit. Moreover, such a compatible spanning circuit can be found by an
\(O(n^4)\) algorithm.
Remark 1.1
Example 1.1
Let
G be a complete graph on
n (
\(n\ge 3\)) vertices, and let
u be one of the vertices of
G. We label the remaining vertices with
\(v_1, \ldots , v_{n1}\), respectively, and we color the edge
\(uv_i\) with color
i for each
\(v_i\), where
\(1\le i\le n1\). Let
\(H=Gu\), and consider a decomposition of the edges of
H into
\(\lfloor (n2)/2\rfloor \) Hamilton cycles (together with one perfect matching
M, if
n is odd). We arbitrarily orient these Hamilton cycles (and
M, if
n is odd) such that they become directed cycles (a directed perfect matching). We color the edge
\(v_iv_j\) with color
j if the arc
\(\overrightarrow{v_iv_j}\) is an arc of one of these Hamilton cycles (perfect matching). This defines an edgecoloring of
G, thus a
\(K^c_{n}\).
One can check that the edgecolored complete graph
\(K^c_{n}\) of Example
1.1 satisfies
\(\Delta ^{mon}(K^c_{n})=\lfloor (n1)/2\rfloor +1\), but it contains no compatible spanning circuit, because such a circuit cannot visit the vertex
u compatibly.
We next deal with the existence of compatible spanning circuits visiting every vertex, except for one specific vertex, exactly
\((n2)/2\) times in graphs
\(K^c_{n}\), and we obtain the following result.
Theorem 1.3
Let
n be an even integer such that
\(n\ge 4\). If
\(\Delta ^{mon}(K^c_{n})\le (n2)/2\) and
\(cd(v_0)\ge n\lfloor (\sqrt{4n3}+1)/2\rfloor \) for some vertex
\(v_0\) of
\(K^c_{n}\), then
\(K^c_{n}\) contains a compatible spanning circuit visiting every vertex of
\(K^c_{n}\), except for
\(v_0\), exactly
\((n2)/2\) times. Moreover, such a compatible spanning circuit can be found by an
\(O(n^4)\) algorithm.
Remark 1.2
The rest of the paper deals with the proofs of our three results.
2 Proof of Theorem 1.1
Our proof is based on the NPcompleteness of the following special case of the Hamilton problem, an early complexity result due to Garey et al. (
1974).
Problem 2.1
(Garey et al.
1974)

Instance: A connected graph G with \(\Delta (G)=3\).

Question: Does G contain a Hamilton cycle?
The problem above can easily be reduced to the following special case of the decision problem we stated in Theorem
1.1.
Problem 2.2

Instance: An edgecolored connected graph \(G^c\) with \(\Delta (G^c)=3\).

Question: Does \(G^c\) contain a compatible spanning circuit?
First of all, Problem
2.2 clearly belongs to the class NP: for any candidate subgraph
H corresponding to a compatible spanning circuit in
\(G^c\), it can be verified in polynomial time whether the subgraph
H contains all vertices of
\(G^c\),
\(d_H(v)=2\) and
\(\Delta ^{mon}_H(v)=1\) for each vertex
v of
H.
For any instance
G of Problem
2.1, we construct a rainbow edgecolored graph by coloring all edges of
G with pairwise distinct colors, to obtain an instance
\(G^c\) of Problem
2.2. It is obvious that the graph
G contains a Hamilton cycle if and only if the edgecolored graph
\(G^c\) contains a compatible spanning circuit.
3 Proofs of Theorems 1.2 and 1.3
Before proceeding with our proofs, we first introduce some additional terminology.
For a given trail
\(T_i=x_1x_2\cdots x_i\)
\((i\ge 2)\) of a graph
H, we use
\(H_i\) to denote the (spanning) subgraph of
H obtained from
H by deleting all the edges of
\(T_i\). For a given (compatible) trail
\(T_i=x_1x_2\cdots x_i\)
\((i\ge 2)\) of an edgecolored graph
H, an edge
\(x_ix_{i+1}\) of
H is said to be
suitable for
\(T_i\) in
H if
\(x_ix_{i+1}\in E_{H_i}(x_i)\) and
\(c(x_ix_{i+1})\) satisfies that
\(c(x_ix_{i+1})\ne c(x_{i1}x_i)\) and
\(d^{c_0}_{H_i}(x_i)=\max \limits _{c\ne c(x_{i1}x_i)}\{d^{c}_{H_i}(x_i)\}\), where
\(c_0=c(x_ix_{i+1})\).
We prove Theorem
1.2 by considering the following polynomial algorithm, and proving its correctness. We use CSC as shorthand for compatible spanning circuit.
×
The ideas behind Algorithm 1 were inspired by similar ideas due to Pevzner (
1995) for an efficient algorithm to construct a compatible Euler tour in an edgecolored eulerian graph
G in which
\(\Delta ^{mon}(v)\le d(v)/2\) for each vertex
v of
G.
Next, we show the correctness of Algorithm 1 by proving the following lemmas, with the notations
\(H_i\),
\(T_i\),
H and
T defined as above.
Lemma 3.1
We have
\(\Delta ^{mon}_{H_i}(v)\le d_{H_i}(v)/2\) for each integer
i with
\(i\ge 2\) such that
\(T_i\ne T\), and each vertex
v of
\(H_i\), excluding possibly
\(x_1\) and
\(x_i\).
Proof
Suppose, to the contrary, that the statement of Lemma
3.1 does not hold. Let
\(i_0\) be the minimum integer such that Lemma
3.1 fails. Clearly, we have
\(i_0>2\). Thus, for some color
c and some vertex
v distinct from
\(x_1\) and
\(x_{i_0}\), we have
\(d^c_{H_{i_0}}(v)> d_{H_{i_0}}(v)/2\). It is not difficult to see that
\(v=x_{i_01}\); otherwise Lemma
3.1 would already fail for the integer
\(i_01\). It follows from
\(d^c_{H_{i_0}}(x_{i_01})> d_{H_{i_0}}(x_{i_01})/2\) and
\(d_{H_{i_0}}(x_{i_01})\) is even that
\(d^c_{H_{i_0}}(x_{i_01})\ge d_{H_{i_0}}(x_{i_01})/2+1\).
Obviously, we have
\(d^c_{H_{i_01}}(x_{i_01})\ge d^c_{H_{i_0}}(x_{i_01})\ge d_{H_{i_0}}(x_{i_01})/2+1=(d_{H_{i_01}}(x_{i_01})1)/2+1= (d_{H_{i_01}}(x_{i_01})+1)/2\).
We first prove the following claim in order to complete the proof of Lemma
3.1.
Claim 1
\(c(x_{i_01}x_{i_0})=c\).
Proof
Suppose, to the contrary, that
\(c(x_{i_01}x_{i_0})\ne c\). Recall that
\(d^c_{H_{i_01}}(x_{i_01})\ge (d_{H_{i_01}}(x_{i_01})+1)/2\) and
\(T_{i_0}\ne T\). It follows that
\(c(x_{i_02}x_{i_01})=c\) by the rules of Step 3 of Algorithm 1. Thus, we have
\(d^c_{H_{i_02}}(x_{i_01})=d^c_{H_{i_01}}(x_{i_01})+1\ge (d_{H_{i_01}}(x_{i_01})+1)/2+1=d_{H_{i_02}}(x_{i_01})/2+1\), contradicting the minimality of
\(i_0\). This confirms our claim.
\(\square \)
By Claim
1, we have
\(c(x_{i_02}x_{i_01})\ne c\) and
\(c(x_{i_01}x_{i_0})=c\). Hence, we have
\(d^c_{H_{i_02}}(x_{i_01})\)
\(=d^c_{H_{i_0}}(x_{i_01})+1\ge d_{H_{i_0}}(x_{i_01})/2+1+1=(d _{H_{i_02}}(x_{i_01})2)/2+1+1=d_{H_{i_02}}(x_{i_01})/2+1\), contradicting the minimality of
\(i_0\). This completes the proof of Lemma
3.1.
\(\square \)
Lemma 3.2
We have
\(\Delta ^{mon}_{H_i}(x_1)\le \lceil d_{H_i}(x_1)/2\rceil \) for each integer
i with
\(i\ge 2\) such that
\(x_i\ne x_1\).
Proof
By Step 2 of Algorithm 1, we have
\(\Delta ^{mon}_{H_2}(x_1)=\Delta ^{mon}_{H_1}(x_1)=\Delta ^{mon}_{H}(x_1)\). For the case that
n is odd, we have
\(\Delta ^{mon}_{H}(x_1)=\Delta ^{mon}_{K^c_{n}}(x_1)\le (n1)/2=\lceil (n2)/2\rceil =\lceil d_{H_2}(x_1)/2\rceil \). For the case that
n is even, we have
\(\Delta ^{mon}_{H}(x_1)\le \Delta ^{mon}_{K^c_{n}}(x_1)\le (n2)/2=\lceil (n3)/2\rceil =\lceil d_{H_2}(x_1)/2\rceil \). Thus, Lemma
3.2 holds for
\(i=2\).
Next, we assume that
\(i\ge 3\). Suppose, to the contrary, that the statement of Lemma
3.2 does not hold. Let
\(i_0\) be the minimum integer such that Lemma
3.2 fails. Since
\(x_{i_0}\ne x_1\), we conclude that
\(x_{i_01}= x_1\); otherwise Lemma
3.2 would already fail for some integer less than
\(i_0\). Thus, for some color
c, we have
\(d^c_{H_{i_0}}(x_1)\ge \lceil d_{H_{i_0}}(x_1)/2\rceil +1\). Note that
\(d_{H_{i_0}}(x_1)\) is odd. Let
\(d_{H_{i_0}}(x_1)=2k1\)
\((k\ge 1)\). Obviously, we have
\(d^c_{H_{i_01}}(x_1)\ge d^c_{H_{i_0}}(x_1)\ge \lceil d_{H_{i_0}}(x_1)/2\rceil +1=\lceil (2k1)/2\rceil +1=k+1=d_{H_{i_01}}(x_1)/2+1\).
We first prove the following claim in order to complete the proof of Lemma
3.2.
\(\square \)
Claim 2
\(c(x_1x_{i_0})=c\).
Proof
Suppose, to the contrary, that
\(c(x_1x_{i_0})\ne c\). Recall that
\(x_{i_01}= x_1\) and
\(d^c_{H_{i_01}}(x_1)\ge d_{H_{i_01}}(x_1)/2+1\). It follows that
\(c(x_{i_02}x_1)=c\) by the rules of Step 3 of Algorithm 1. Thus, we have
\(d^c_{H_{i_02}}(x_1)=d^c_{H_{i_01}}(x_1)+1\ge d_{H_{i_01}}(x_1)/2+1+1=k+1+1=\lceil d_{G_{i_02}}(x_1)/2\rceil +1\), contradicting the minimality of
\(i_0\). This confirms our claim.
\(\square \)
By Claim
2, we have
\(c(x_{i_02}x_1)\ne c\) and
\(c(x_1x_{i_0})=c\). Hence, we have
\(d^c_{H_{i_02}}(x_1)=d^c_{H_{i_0}}(x_1)+1\ge \lceil d_{H_{i_0}}(x_1)/2\rceil +1+1=k+1+1=\lceil d_{H_{i_02}}(x_1)/2\rceil +1\), contradicting the minimality of
\(i_0\). This completes the proof of Lemma
3.2.
\(\square \)
Lemma 3.3
For each integer
i with
\(i\ge 2\) such that
\(T_i\ne T\), we have
$$\begin{aligned} \Delta ^{mon}_{H_{i1}}(x_i)\le \left\{ \begin{array}{ll} \displaystyle d_{H_{i1}}(x_i)/2, &{} \text{ if } x_i\ne x_1;\\ \displaystyle (d_{H_{i1}}(x_i)+1)/2, &{} \text{ if } x_i= x_1. \end{array} \right. \end{aligned}$$
Lemma
3.3 implies that for each trail
\(T_i\ne T\), there always exists an edge
\(x_ix_{i+1}\) that is suitable for
\(T_i\) in
H.
Next, we show that Algorithm 1 will terminate, by proving the following lemma.
Lemma 3.4
For an integer
i with
\(i\ge 3\) such that
\(x_i\ne x_1\) and
\(E_{H_i}(x_i)=E_{H_i}(x_1)=\{x_ix_1\}\), we have
\(V(T_i)=V(H)\), as well as
\(c(x_{i1}x_i)\ne c(x_ix_1)\) and
\(c(x_ix_1)\ne c(x_1x_2)\).
Proof
Let
i be an integer with
\(i\ge 3\) such that
\(x_i\ne x_1\) and
\(E_{H_i}(x_i)=E_{H_i}(x_1)=\{x_ix_1\}\).
We first claim that
\(V(T_i)=V(H)\). Suppose, to the contrary, that there exists a vertex
\(v\in V(H)\setminus V(T_i)\). Obviously, we have
\(v\notin \{x_1, x_i\}\). Recall that
\(K^c_{n}\) is a complete graph on
n vertices, where
\(n\ge 3\). It follows from the construction of
H that at least one of
\(vx_i\) and
\(vx_1\) is an edge of
\(H_i\), contradicting the fact that
\(E_{H_i}(x_i)=E_{H_i}(x_1)=\{x_ix_1\}\). Thus as we claimed, we have
\(V(T_i)=V(H)\).
Recall that
\(E_{H_i}(x_i)=\{x_ix_1\}\). It follows that
\(\Delta ^{mon}_{H_{i1}}(x_i)=1\) by Lemma
3.3. Therefore, we conclude that
\(c(x_{i1}x_i)\ne c(x_ix_1)\).
Next, we prove the assertion that
\(c(x_ix_1)\ne c(x_1x_2)\). Suppose, to the contrary, that
\(c(x_ix_1)=c(x_1x_2)=c_0\). Let us consider
\(T_i\) as the oriented trail in the direction from
\(x_1\) to
\(x_2\) (see Fig.
1). Note that
\(d_H(x_1)=n1\), if
n is odd, and
\(d_H(x_1)=n2\), otherwise. We use
\(y_1, y_2,\ldots ,y_{n3}, y_{n2}\) (and
\(y_{n1}\), if
n is odd) to denote the vertices of
H adjacent to the vertex
\(x_1\) according to the order in which they are visited by the oriented trail
\(T_i\) (see Fig.
1a, b).
×
We prove the following claim in order to complete the proof of Lemma
3.4.
Claim 3
There exists an integer
j with
\(2\le j\le n4\) (
\(2\le j\le n3\), if
n is odd) such that
\(c(\overrightarrow{y_jx_1})\ne c_0\) and
\( c(\overrightarrow{x_1y_{j+1}})\ne c_0\).
Proof
Suppose, to the contrary, that at least one of
\(c(\overrightarrow{y_jx_1})\) and
\( c(\overrightarrow{x_1y_{j+1}})\) is
\(c_0\) for every integer
j with
\(2\le j\le n4\) (
\(2\le j\le n3\), if
n is odd). It follows that
\(d^{c_0}_H(x_1)\ge (n4)/2+2>(n2)/2\) (
\(d^{c_0}_H(x_1)\ge (n3)/2+2>(n1)/2\), if
n is odd), contradicting the fact that
\(\Delta ^{mon}(K^c_{n})\le \lfloor (n1)/2\rfloor \). This confirms our claim.
\(\square \)
Let
\(j_0=\max \{j\mid c(\overrightarrow{y_jx_1})\ne c_0~\)and
\(~ c(\overrightarrow{x_1y_{j+1}})\ne c_0\}\). We suppose that
\(y_{j_0}=x_k\). Thus, we have
\(x_{k+1}=x_1\). We conclude that
\(d^{c_0}_{H_{k+1}}(x_1)\ge (n3j_01)/2+1\) and
\(d_{H_{k+1}}(x_1)=n2j_0\) (
\(d^{c_0}_{H_{k+1}}(x_1)\ge (n2j_01)/2+1\) and
\(d_{H_{k+1}}(x_1)=n1j_0\), if
n is odd), implying that
\(d^{c_0}_{H_{k+1}}(x_1)\ge d_{H_{k+1}}(x_1)/2\). Recall that
\(c(\overrightarrow{y_{j_0}x_1})\ne c_0\). By definition, the edge of
\(E_{H_{k+1}}(x_1)\) with color
\(c_0\) is suitable for
\(T_{k+1}\) in
H. It follows that
\(c(\overrightarrow{x_1y_{j_0+1}})=c_0\) by the rules of Step 3 of Algorithm 1. However, as supposed, we have
\(c(\overrightarrow{x_1y_{j_0+1}})\ne c_0\), a contradiction. This completes the proof of Lemma
3.4.
\(\square \)
Lemma
3.4 implies that Algorithm 1 will terminate in the case that
\(E_{H_i}(x_i)=E_{H_i}(x_1)=\{x_ix_1\}\) for some integer
i with
\(i\ge 3\) such that
\(x_i\ne x_1\). However, it is possible that Algorithm 1 terminates earlier. It is not difficult to check that in all cases the output
T of Algorithm 1 is a compatible spanning circuit of
\(K^c_{n}\).
Now, we analyze the time complexity of Algorithm 1. It is obvious from the structure of the algorithm that the combination of Step 4 and Step 3 dominates and determines its time complexity. Since each edge of
H is traversed at most once, Step 3 is performed at most
\(E(H)=O(n^2)\) times according to Step 4 of Algorithm 1. In Step 3 of Algorithm 1, it requires at most
\(O(n^2)\) time to choose a vertex
\(x_{i+1}\) such that
\(x_ix_{i+1}\) is suitable for
\(T_i\) in
H: this requires checking and comparing these colors that appear on
\(x_{i1}x_i\) and the at most
\(O(n^2)\) edges of
\(E_H(x_i)\). Thus, Step 3 takes at most
\(O(n^2)\) time, yielding an overall time complexity
\(O(n^4)\). This completes the proof of Theorem
1.2.
\(\square \)
3.1 Proof of Theorem 1.3
We prove Theorem
1.3 by using a known algorithm due to Pevzner (
1995) as a subroutine to construct an
\(O(n^4)\) algorithm, and proving its correctness.
Pevzner (
1995) provided a polynomial algorithm for constructing a compatible Euler tour (CET for short) in an edgecolored eulerian graph
G in which
\(\Delta ^{mon}(v)\le d(v)/2\) for each vertex
v of
G (see Algorithm 2 below). Benkouar et al. (
1996) independently described a different algorithm for solving the same problem, requiring solving a perfect matching problem for a specific class of complete
kpartite graphs.
We use Algorithm 2 as a subroutine to construct an
\(O(n^4)\) algorithm for finding a compatible spanning circuit visiting every vertex of
\(K^c_n\), except for one specific vertex, exactly
\((n2)/2\) times (SCSC for short), subject to the conditions that
n is an even integer and
\(n\ge 4\), as well as the graph
\(K^c_n\) satisfies
\(\Delta ^{mon}(K^c_n)\le (n2)/2\) and
\(cd(v_0)\ge n\lfloor (\sqrt{4n3}+1)/2\rfloor \) for some vertex
\(v_0\) of
\(K^c_n\) (see Algorithm 3 below).
In Algorithm 3, we denote
\(G'=K^c_nv_0\), where
\(v_0\) is a specific vertex of
\(K^c_n\) with
\(cd(v_0)\ge n\lfloor (\sqrt{4n3}+1)/2\rfloor \). It is not difficult to see that
\(\Delta ^{mon}_{G'}(v)\le \Delta ^{mon}(K^c_n)\le (n2)/2=d_{G'}(v)/2\) for each vertex
v of
\(G'\). Thus, the graph
\(G'\) satisfies the conditions of Algorithm 2. This implies that we can use Algorithm 2 as a subroutine in Step 2 of Algorithm 3 to construct a compatible Euler tour
\(T'\) of
\(G'\).
After presenting the pseudocode of the two algorithms, we show the correctness of Algorithm 3 by stating and proving Lemma
3.5. This is followed by a short analysis of the time complexity and some concluding remarks.
×
×
The correctness of Algorithm 3 follows directly from the following lemma (and the correctness of Algorithm 2 due to Pevzner (
1995)).
Lemma 3.5
There exists an edge
\(x_ix_{i+1}\) of
\(T'\) such that
\(c(x_{i1}x_i)\ne c(x_iv_0)\) and
\(c(x_iv_0)\ne c(v_0x_{i+1})\), as well as
\(c(v_0x_{i+1})\ne c(x_{i+1}x_{i+2})\), where the subscripts are taken modulo
\({n1 \atopwithdelims ()2}\).
Proof
Suppose, to the contrary, that for each integer
i such that
\(c(x_iv_0)\ne c(v_0x_{i+1})\), either
\(c(x_{i1}x_i)= c(x_iv_0)\), or
\(c(v_0x_{i+1})= c(x_{i+1}x_{i+2})\).
Let
\(cd(v_0)=n\ell \ge n\lfloor (\sqrt{4n3}+1)/2\rfloor \). Thus, we have
\(\ell \le (\sqrt{4n3}+1)/2\). Let
\(P=\{\{v_0x_i,~v_0x_{i+1}\}\subset E_{K^c_n}(v_0)\mid c(v_0x_i)\ne c(v_0x_{i+1})\}\). We can conclude that
\(P\ge {n1 \atopwithdelims ()2}{\ell \atopwithdelims ()2}=((n1)(n2))/2(\ell (\ell 1))/2=(n^23n+2{\ell }^2+\ell )/2\).
As supposed, we have either
\(c(x_{i1}x_i)= c(x_iv_0)\), or
\(c(v_0x_{i+1})= c(x_{i+1}x_{i+2})\) for each pair
\(\{v_0x_i,~v_0x_{i+1}\}\) of
P. Note that the graph
\(G'\) is a complete graph on
\(n1\) vertices. It follows from
\(\ell \le (\sqrt{4n3}+1)/2\) that
\(\frac{P}{n1}\ge \frac{n^23n+2{\ell }^2+\ell }{2(n1)}\ge \frac{n3}{2} >\frac{n4}{2}\). Therefore, there exists a vertex
v of
\(G'\) such that
\(d^{c_0}_{K^c_n}(v)\ge (n4)/2+1+1>(n2)/2\), where
\(c_0=c(v_0v)\), contradicting that
\(\Delta ^{mon}(K^c_n)\le (n2)/2\). This completes the proof of Lemma
3.5.
\(\square \)
Lemma
3.5 clearly shows that we can always find an edge satisfying the requested conditions at Step 3 of Algorithm 3.
It is not difficult to check that the closed trail returned by Algorithm 3 is a desired compatible spanning circuit of
\(K^c_n\).
In order to analyze the time complexity of Algorithm 3, we first need to analyze the time complexity of Algorithm 2 due to Pevzner, since we use it as a subroutine. In fact, it is clear that Algorithm 2 is the dominating factor regarding the time complexity of Algorithm 3. Due to the similarity with Algorithm 1, it is not difficult to see that Algorithm 2 has time complexity
\(O(n^4)\) (in case the graph
G is a complete graph on
n vertices). Therefore, the whole time complexity of Algorithm 3 is
\(O(n^4)\). This completes the proof of Theorem
1.3.
\(\square \)
4 Conclusions and final remarks
In this work, we considered the existence of more general compatible spanning circuits in edgecolored graphs from an algorithmic perspective. We first proved that the decision problem of determining whether an edgecolored connected graph contains a compatible spanning circuit is NPcomplete, even within graphs with maximum degree 3. We then developed two polynomialtime algorithms for finding compatible spanning circuits (with certain properties) in specific edgecolored complete graphs. In particular, our Algorithm 1 returns a compatible spanning circuit (with no restrictions) directly. In previous work from literature, this was done in two steps. We also presented Algorithm 3 for finding compatible spanning circuits visiting every vertex, except for one specific vertex, exactly
\((n2)/2\) times in edgecolored complete graphs
G on even
n (
\(n\ge 4\)) vertices with
\(\Delta ^{mon}(G)\le (n2)/2\) and
\(cd(v_0)\ge n\lfloor (\sqrt{4n3}+1)/2\rfloor \) for some vertex
\(v_0\) of
G.
In future work, we look forward to establishing polynomialtime algorithms for finding compatible spanning circuits in other classes of edgecolored graphs. As another future direction, a more challenging problem is to develop polynomialtime algorithms for finding compatible spanning circuits visiting every vertex exactly (or at least) a specified number of times in some specific classes of edgecolored graphs.
Acknowledgements
We thank the anonymous referees for their careful reading, and for their useful comments on an earlier version that improved the presentation.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.