I have added Provides: xlibs to debian/control of source package libx11 and rebuilt it, which solved the problem. There also is an utility which generated empty .debs with required Provides:, but I could not remember the name, thus the rebuild. -- gothfox