Here's the output of installing without Recommends (and coreutils):

roaksoax@unleashed:~$ lxc exec xenial6 -- /bin/sh
# sudo apt-get install isc-dhcp-server --no-install-recommends
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following additional packages will be installed:
  libirs-export91 libisccfg-export90
Suggested packages:
  isc-dhcp-server-ldap apparmor
Recommended packages:
  policycoreutils
The following NEW packages will be installed:
  isc-dhcp-server libirs-export91 libisccfg-export90
0 upgraded, 3 newly installed, 0 to remove and 0 not upgraded.
Need to get 483 kB of archives.
After this operation, 1,718 kB of additional disk space will be used.
Do you want to continue? [Y/n] y
Get:1 http://archive.ubuntu.com/ubuntu xenial/main i386 libisccfg-export90
i386 1:9.9.5.dfsg-12.1ubuntu1 [21.7 kB]
Get:2 http://archive.ubuntu.com/ubuntu xenial/main i386 libirs-export91
i386 1:9.9.5.dfsg-12.1ubuntu1 [18.5 kB]
Get:3 http://archive.ubuntu.com/ubuntu xenial/main i386 isc-dhcp-server
i386 4.3.3-5ubuntu5 [443 kB]
Fetched 483 kB in 1s (405 kB/s)
Preconfiguring packages ...
Selecting previously unselected package libisccfg-export90.
(Reading database ... 12764 files and directories currently installed.)
Preparing to unpack
.../libisccfg-export90_1%3a9.9.5.dfsg-12.1ubuntu1_i386.deb ...
Unpacking libisccfg-export90 (1:9.9.5.dfsg-12.1ubuntu1) ...
Selecting previously unselected package libirs-export91.
Preparing to unpack .../libirs-export91_1%3a9.9.5.dfsg-12.1ubuntu1_i386.deb
...
Unpacking libirs-export91 (1:9.9.5.dfsg-12.1ubuntu1) ...
Selecting previously unselected package isc-dhcp-server.
Preparing to unpack .../isc-dhcp-server_4.3.3-5ubuntu5_i386.deb ...
Unpacking isc-dhcp-server (4.3.3-5ubuntu5) ...
Processing triggers for libc-bin (2.21-0ubuntu6) ...
Processing triggers for ureadahead (0.100.0-19) ...
Processing triggers for systemd (229-1ubuntu2) ...
Setting up libisccfg-export90 (1:9.9.5.dfsg-12.1ubuntu1) ...
Setting up libirs-export91 (1:9.9.5.dfsg-12.1ubuntu1) ...
Setting up isc-dhcp-server (4.3.3-5ubuntu5) ...
Generating /etc/default/isc-dhcp-server...
Processing triggers for libc-bin (2.21-0ubuntu6) ...
Processing triggers for ureadahead (0.100.0-19) ...
Processing triggers for systemd (229-1ubuntu2) ...
# dpkg -l | grep policy
ii  libsemanage-common        2.3-1build2                  all
 Common files for SELinux policy management libraries
ii  libsemanage1:i386         2.3-1build2                  i386
SELinux policy management library
# dpkg -l | grep policycoreutils

On Thu, Feb 18, 2016 at 6:28 PM, Robie Basak <email address hidden>
wrote:

> Downgrading to Medium, as I feel that Critical needs a justification.
>
> ** Changed in: isc-dhcp (Ubuntu)
>    Importance: Critical => Medium
>
> --
> You received this bug notification because you are subscribed to the bug
> report.
> https://bugs.launchpad.net/bugs/1546358
>
> Title:
>   policycoreutils (in universe) is installed by default by isc-dhcp-
>   server as it is a Recommends
>
> To manage notifications about this bug go to:
>
> https://bugs.launchpad.net/ubuntu/+source/isc-dhcp/+bug/1546358/+subscriptions
>



-- 
Andres Rodriguez (RoAkSoAx)
Ubuntu Server Developer
MSc. Telecom & Networking
Systems Engineer