On the job rotation problem



Corollary 9. Let A Tn×n be a symmetric matrix, σ1 , σ2 , . . . , σt be a collec-
tion of PND cycles in
D(A) covering kmax or kmax - 1 nodes, with at least one
having length
koddmin. Then we can decide whether δk (A) is 0 or -∞ for all k
in linear time, after finding kmax and koddmin .

Proof. The result follows from Corollary 4 and Theorem 8.

Theorem 10. If A Tn×n is a symmetric matrix, then δk (A) = 0 for all odd

k {koddmin, . . . , kmax

koddmin}.


Proof. As δkmax = 0, there exist PND cycles σ1, σ2, . . . , σt in D(A) that cover
kmax nodes. There exists a cycle σ in D(A) of length koddmin.

Delete all nodes in V (σ) from σ1, σ2, . . . , σt, as well as incident arcs. As
the cycles were PND and each node was incident to precisely two arcs, up
to 2
koddmin arcs have been deleted. Therefore this leaves a total of at least
kmax - 2koddmin arcs within the remaining PND cycles and paths that have
arisen from deleting the arcs from the cycles. Split any paths into 2-cycles.
We now have PND cycles in
D(A) covering at least kmax - 2koddmin arcs, and
therefore at least
kmax - 2koddmin nodes, none of which are nodes on σ.

Therefore, by Corollary 4, for all even i ≤ kmax - 2koddmin , there exist PND
cycles
σ10 , σ20 , . . . , σt00 in D(A) covering i nodes, but none on σ. So for all even
i ≤ kmax - 2koddmin, we have PND cycles σ10 , σ20 , . . . , σt00 and σ in D(A) which
cover
i + koddmin nodes. Hence the result.                                 □

Remark. Note that {koddmin, ∙ ∙ ∙ , kmax koddmin} = ^ ^ koddmin   2 .

Corollary 11. Let A Tn×n be a symmetric matrix, with PND cycles in
D(A) covering kmax or kmax - 1 nodes, one having odd length of at most
kmax - koddmin . Then we can decide whether δk (A) is 0 or -∞ for all k in
linear time, after finding
kmax and koddmin .

Proof. The result follows from Corollary 4, Theorem 8 and Theorem 10.    □

Corollary 12. Let A Tn×n be a symmetric matrix, with PND cycles in D(A)
covering
kmax or kmax - 1 nodes, two having odd length. Then we can decide
whether
δk (A) is 0 or -∞ for all k in linear time, after finding kmax .

Proof. The result follows from Corollary 11 and the fact that the length of at
least one of the odd cycles is at most
km2ax ≤ kmax — koddmin.               □

10



More intriguing information

1. Gianluigi Zenti, President, Academia Barilla SpA - The Changing Consumer: Demanding but Predictable
2. The bank lending channel of monetary policy: identification and estimation using Portuguese micro bank data
3. The name is absent
4. The economic value of food labels: A lab experiment on safer infant milk formula
5. The name is absent
6. Reputations, Market Structure, and the Choice of Quality Assurance Systems in the Food Industry
7. The Social Context as a Determinant of Teacher Motivational Strategies in Physical Education
8. A Pure Test for the Elasticity of Yield Spreads
9. Testing for One-Factor Models versus Stochastic Volatility Models
10. The name is absent