Holding Period Algorithms and the Blockchain
My question is, do these holding period algorithms have to correspond to the actual UTXOs being spent on the blockchain? 


This is likely a question best answered by a qualified accountant, or tax lawyer. 

I say this because there are many nuances to it: if you spend half of your oldest UTXO, to sell it for cash, then what do we say about the change output? It is a brand new UTXO, but clearly you bought those coins long ago. Similarly, how would the age or origin of a coin-consolidation UTXO be calculated? What about outputs from coinjoin-style transactions? What happens if I just want to update my cold storage system, and want to move coins to new addresses? etc.

I hope these examples help highlight the difficulty of applying existing regulations to a new system like Bitcoin. If you are looking for tax/legal advice, the best course of action is to ask a professional, not a stranger on the internet. 


  Does using FIFO entail that you have to program your wallet to spend older UTXOs before newer ones, and vice-versa for LIFO?


A wallet using such a system would be bad for your privacy, UTXO-management, and fee-management, plus it still wouldn't answer the questions I mentioned above. So I doubt that any reasonable regulation would require such a thing.