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$
1
  • $\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 Mod
    Commented Jun 10, 2015 at 7:35

2 Answers 2

Reset to default
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$
3
  • $\begingroup$ To be clear, you are proposing network-flow <-- max-flow? $\endgroup$
    – Raphael Mod
    Commented Oct 16, 2015 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. Mod
    Commented Oct 16, 2015 at 15:51
  • $\begingroup$ Yes, it does indeed. $\endgroup$
    – Raphael Mod
    Commented Oct 16, 2015 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$
7
  • $\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. Mod
    Commented Jun 23, 2015 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
    Commented Jun 23, 2015 at 20:14
  • $\begingroup$ Or this one cs.stackexchange.com/questions/37237/… $\endgroup$
    – Wandering Logic
    Commented Jun 23, 2015 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. Mod
    Commented Oct 15, 2015 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
    Commented Oct 15, 2015 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 Mod
    Commented Oct 16, 2015 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
    Commented Oct 16, 2015 at 13:48

You must log in to answer this question.

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