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. Eigentumsrechtliche Dezentralisierung und institutioneller Wettbewerb
2. Conservation Payments, Liquidity Constraints and Off-Farm Labor: Impact of the Grain for Green Program on Rural Households in China
3. New Evidence on the Puzzles. Results from Agnostic Identification on Monetary Policy and Exchange Rates.
4. Getting the practical teaching element right: A guide for literacy, numeracy and ESOL teacher educators
5. The name is absent
6. The WTO and the Cartagena Protocol: International Policy Coordination or Conflict?
7. The name is absent
8. Spatial Aggregation and Weather Risk Management
9. Macroeconomic Interdependence in a Two-Country DSGE Model under Diverging Interest-Rate Rules
10. Ein pragmatisierter Kalkul des naturlichen Schlieβens nebst Metatheorie