The maximum beer flow problem*

doi:10.1016/j.tcs.2026.115768

The maximum beer flow problem*

2026-01-01

0

PRE

AI

DOI：10.1016/j.tcs.2026.115768

Original

Original request for help

Save

Abstract

En 中文

Let G = (V, E, B) be a graph with a vertex set V, an edge set E, and a distinguished subset of vertices B c V, called beer stores. A beer path from u to v is a path that starts at u, ends at v, and visits at least one beer store. The notion of a beer path was recently introduced and studied, with a focus on finding the shortest beer path in a graph. In this work, we explore the natural extension of this notion into what we call a beer flow. We show that the maximum beer flow problem can be formulated by linear programming so that it can be solved in polynomial time. However, when the flow on each edge is restricted to be integral, the problem suddenly becomes NP-hard, even in the very simple settings. This result is in stark contrast with the traditional maximum flow problem, where integrality of flow will not complicate the problem.

Keywords:

Beer path

Beer flow

NP-Hardness

Approximation

The maximum beer flow problem*

Abstract

Journal

Organization