Today I ran exactly into this problem. I ran some updates and auto-removes on my Ubuntu 16.04 machine and suddenly VLC was gone.
So the next thing I did was just a simple
sudo apt install vlc
and in return I got this error message:
The following packages have unmet dependencies: vlc : Depends: libgles1-mesa (>= 7.8.1) but it is not going to be installed or libgles1 E: Unable to correct problems, you have held broken packages.
So before using my brain, I rather used google and I was not successful to get VLC for what ever reason, back on my machine.
Moments later my brain kicked in and my solution for this problem was easy. Very easy.
sudo snap install vlc vlc daily from 'videolan' installed
Started VLC and there you go. Running like expected.
In case you have never snapped anything on your 16.04 machine, simply install Snap on it.
sudo apt install snapd
For more details to use and handle snap check out this post on How to Install and Manage Snap Packages on Ubuntu 16.04 LTS