On the job rotation problem

Proof. We assume that (j, j) is a loop in D(A). As δk_max (A) = 0, there exist
PND cycles in D(A) σ1, σ2, . . . , σt in D(A) covering kmax nodes. We need to
show there exist PND cycles σ₁⁰ , σ₂⁰ , . . . , σ_t⁰0 in D(A), at least one being a loop,
that cover kmax or kmax - 1 nodes.

Clearly if (j, j) ∈ {σ₁, σ₂, . . . , σ_t} then we can use Theorem 6 and we are
done, so assume not. Then j is covered by these cycles, as otherwise, (j, j)
together with σ1 , σ2 , . . . , σt would form PND cycles in D(A) covering kmax + 1
nodes, which contradicts the definition of kmax . Hence there exists one cycle
σ_r = (j, i₂, i₃, . . . , i_p, j) ∈ {σ₁, σ₂, . . . , σ_t}.

If p is odd, then we can split σr - j , and add (j, j ) to the resulting cycles
to form PND cycles in D(A) covering kmax nodes. If instead p is even, then we
can split σr , remove the 2-cycle that contains p, and add (j, j) to the remaining
cycles to form PND cycles in D(A) covering k_max - 1 nodes. The result then
follows from Theorem 6.                                                □

For A ∈ Rn×n, we define F = {k ∈ N; δ_k(A) = -∞}. By Corollary 4, for
symmetric matrices, unless k_max = 1, the smallest even k ∈ F is 2. However,
the smallest odd value in F is more tricky. We denote this value by koddmin .

Remark. If there exist PND cycles σ1, σ2, . . . , σt in D(A) such that an odd
number of nodes is covered, then at least one of the cycles is odd. Hence
koddmin is the length of a shortest odd cycle in D(A). This cycle can be found
polynomially [19]. Note that koddmin does not exist if there is no odd cycle in
D(A), and if this is the case, then δ_k = -∞ for all odd k. For the remainder of
this section, we shall assume that koddmin exists.

Theorem 8. Let A ∈ T^n×n be a symmetric matrix, σ1 , σ2, . . . , σt be a collection
of PND cycles in D(A) covering k⁰ nodes, with at least one having odd length.
Then δk (A) = 0 for all odd k ∈ {l⁰, . . . , k⁰}, where l⁰ is the minimum length of
the odd cycles in this collection.

Proof. Without loss of generality, assume the length of σ_t is l⁰ . Then the PND
cycles σ1, σ2, . . . , σt-1 in D(A) cover k⁰-l⁰ nodes, hence δk0 -l0 = 0. By Corollary
4, δk = 0 for all even k ∈ {0, . . . , k⁰ - l⁰}. Take an arbitrary even k ∈ {0, . . . , k⁰ -
l⁰}. So k + l⁰ ∈ {l⁰, . . . , k⁰}. There exist PND cycles σ₁⁰ , σ₂⁰ , . . . , σ_t⁰0 in D(A)
covering k nodes other than those in V (σ_t). Therefore, σ₁⁰ , σ₂⁰ , . . . , σ_t⁰0 and σ_t
are PND cycles in D(A) covering k + l⁰ nodes. Hence the result.            □

<<   6   7   8   9   10   11   12   >>

More intriguing information