3
$\begingroup$

I noticed we have tags for both and . Does that make sense? Is there any distinction?

There seem to be only 2 questions tagged with . Should we make a synonym of ?

$\endgroup$
  • $\begingroup$ I guess max-flow is slightly more specific; I'd tag modelling questions with network-flow but not necessarily max-flow, which I'd reserve for max-flow algorithms and such. $\endgroup$ – Raphael Jun 10 '15 at 7:35
3
$\begingroup$

Yes, in my opinion should be a synonym of .

There's really no difference between them, as they are currently being used:

  • We currently have only 4 questions tagged . 3 out of 4 of those are also tagged .

  • Meanwhile, almost all questions tagged are actually about finding a maximum flow.

While in principle it would be possible to create a meaningful distinction between them, (a) it'd be a very fine line, (b) no such distinction currently exists, (c) people aren't actually using the tag that way, (d) we don't have any tag wikis or anything to guide posters to use the tags that way and most posters probably don't read tag wikis anyway, so posters will continue to use tags in a way that does not respect those fine distinctions, (e) the two are so close that I don't see much value in drawing that particular distinction anyway.

$\endgroup$
  • $\begingroup$ To be clear, you are proposing network-flow <-- max-flow? $\endgroup$ – Raphael Oct 16 '15 at 10:27
  • 1
    $\begingroup$ @Raphael, yes (so network-flow would be the remaining tag that shows up; if a user types max-flow, it gets converted to network-flow). That's based on the fact that we currently have 72 questions tagged network-flow, and only 4 tagged max-flow. Does that seem reasonable to you? $\endgroup$ – D.W. Oct 16 '15 at 15:51
  • $\begingroup$ Yes, it does indeed. $\endgroup$ – Raphael Oct 16 '15 at 21:35
2
$\begingroup$

I would vote to keep . Max-flow should apply to a strict subset of questions. We also have , which is another class of network-flow algorithms. It has 151 uses, which is more than double what we have on .

Shortest path problems can be viewed as specializations of the minimum cost flow problem with costs but no capacity constraints on the links. Similarly Max-flow problems can be viewed as specializations of the minimum cost flow problem with capacity constraints but zero costs on all the links.

Similarly the min-cost flow problem is itself a specialization of the linear programming problem, and multi-commodity flow problems can be formulated as integer programming problems, but I don't think we want to get rid of the tag just because we already have an tag.

$\endgroup$
  • $\begingroup$ Not that I have any particular objection to this proposal, but... are there any (existing) network-flow questions that max-flow wouldn't apply to? $\endgroup$ – D.W. Jun 23 '15 at 19:15
  • $\begingroup$ Whoa! Not many. Here's a few: cs.stackexchange.com/questions/6773/…, cs.stackexchange.com/questions/7610/…, cs.stackexchange.com/questions/2283/… $\endgroup$ – Wandering Logic Jun 23 '15 at 20:14
  • $\begingroup$ Or this one cs.stackexchange.com/questions/37237/… $\endgroup$ – Wandering Logic Jun 23 '15 at 20:20
  • $\begingroup$ I think we could merge max-flow and network-flow without merging any of those other tags. I don't see that shortest paths or linear programming or integer programming really enter into it; there wouldn't be any inconsistency or problem created if we merged only max-flow and network-flow without merging it into any of those other tags. I don't view those other tags as analogous; the situation with them is different, as they are much more recognizably distinct from network flow. $\endgroup$ – D.W. Oct 15 '15 at 18:31
  • 2
    $\begingroup$ I now agree. In practice shortest-path is used without network-flow, while network-flow is almost always used for max-flow/min-cut problems instead of max-flow. It doesn't matter whether my taxonomy is technically correct or not, that's not how users are actually using the tags. $\endgroup$ – Wandering Logic Oct 15 '15 at 20:28
  • $\begingroup$ I agree as well. The fact that any P problem can be expressed as network flow problem or LP or ... does not mean we should all tag them network-flow or linear-programming. $\endgroup$ – Raphael Oct 16 '15 at 10:27
  • $\begingroup$ @Raphael, that was not my original argument. My argument was that shortest-path is the subclass of network flow problems with edge costs but infinite capacities, while max-flow is the subclass of network flow problems with edge capacities, but 0 edge costs. Further, these are the only two obvious subclasses of network flow. The argument is not "x can be expressed as y". Nonetheless, since users aren't using the terms the way I use them, we should go with the wisdom of the crowd. $\endgroup$ – Wandering Logic Oct 16 '15 at 13:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .