The beef here isn't whether package management questions are on-topic. There is a programming problem here all right, but it is way too broad for a single question, and you don't appear to have done enough research to frame it in a form and scope which is suitable for Stack Overflow.
Either you have a specific question about how to parse package dependencies on Debian, with almost-working code, or you have a fundamental question about how to reason about graphs. You cannot cram both into a single question.
You also seem to be arguing in comments that research for research's sake is meaningful and valid. I have no issue with that, but you cannot just pose a research question and ask somebody else to solve it for you -- that's the PhD version of a homework dump. (Not saying this is a PhD-level problem, just being rhetorical.) Either you have a programming problem and a valid question for Stack Overflow, or you have a potentially interesting question which however doesn't really belong here.
I also speculate that the answer is going to be rather boring. Most of userspace can coexist peacefully (for example, you can install every music player which is compatible with your sound hardware, so your users can choose the one they like on a multi-user system). So you will probably end up with a few system services which Conflicts:
between them, and pick the one with the biggest base of supported packages (upstart vs sysinit comes to mind as a probable divider). But in the end, the total number of packages is a good approximation, and the precise number fluctuates and depends on which package sources exactly you have enabled.
A bit of background research would have revealed that there are already tools for exploring the Debian package dependency tree. Apt itself obviously needs to be able to deduce which packages to install; but there are also stand-alone tools like dctrl-tools
Currently, there are 1416 conflicting packages:
debian$ grep-aptavail -F Conflicts . | fgrep -c Conflicts:
1416
There are 1201 unique conflicts; but the vast majority are version conflicts (a package requires at least version so-and-so or at most version so-and-so of something). Of the remaining 375, a significant chunk is still version conflicts (for example, there are two packages with
Conflicts: libmono-cecil0.3-cil, libmono-cecil0.4-cil, libmono-cecil0.5-cil
and so forth).
But anyway, I would be tempted to close this meta question as too broad, too: You attempt to generalize from "are there package management programming problems which are suitable for Stack Overflow" (there are) to "this specific question is fine" (it isn't).
npm
, which are on-topic, but a lot more questions that would probably be better asked on SU or the Linux site. The tag itself is probably too broad, and should maybe be removed in favor of more specific tags.