Não faça isso, o diretório pertence a libselinux1
e alguns pacotes dependem dele. Você não deve remover arquivos ou diretórios fornecidos pelo gerenciador de pacotes.
Comprovado no meu sistema Debian (7.6)
Para descobrir qual pacote possui um caminho em seu sistema, use
$ dpkg -S /selinux/
libselinux1:amd64: /selinux
$ sudo apt-get remove libselinux1
.....
The following packages have unmet dependencies:
perl : Depends: perl-base (= 5.14.2-21+deb7u1) but it is not going to be installed
Depends: perl-modules (>= 5.14.2-21+deb7u1) but it is not going to be installed
E: Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages.
Dito isto, é claro que isso é uma estranheza do pacote libselinux1
.