Minimum Cost Nowhere-zero Flows and Cut-balanced Orientations
Karthekeyan Chandrasekaran, Siyue Liu, R. Ravi · 2025
Read Minimum Cost Nowhere-zero Flows and Cut-balanced Orientations by Karthekeyan Chandrasekaran, Siyue Liu, R. Ravi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-18767.txt.
Introduction
Flows that never vanish and orientations that keep every cut balanced turn out to be two faces of one object. Together they tie tractable flow problems to stubborn coloring ones. Karthekeyan Chandrasekaran, Siyue Liu, and Ravi Ravi study in 2025 the priced versions. Given a bidirected graph with possibly different costs per direction, find the cheapest nowhere-zero flow, or the cheapest balanced orientation.
Both resist approximation within any finite factor, a hard verdict. The authors answer with bicriteria algorithms that bend cost and balance together. For the friendlier symmetric-cost case they give a clean three-approximation for flows, while proving the problem stays NP-hard.
Catalog record
| CREATOR | Karthekeyan Chandrasekaran, Siyue Liu, R. Ravi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 101 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-18767
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Minimum Cost Nowhere-zero Flows and Cut-balanced Orientations Karthekeyan Chandrasekaran, Siyue Liu, R. Ravi Abstract Flows and colorings are disparate concepts in graph algorithms—the former is tractable while the latter is intractable. Tutte [ 43 , 44 ] introduced the concept of nowhere-zero flows to unify these two concepts. Jaeger [ 23 ] showed that nowhere-zero flows are equivalent to cut-balanced orientations. Motivated by connections between nowhere-zero flows, cut-balanced orientations, Nash-Williams’ well-balanced orientations, and postman problems, we study optimization versions of nowhere-zero flows and cut-balanced orientations. Given a bidirected graph with asymmetric costs on two orientations of each edge, we study the min cost nowhere-zero k k -flow problem and min cost k k -cut-balanced orientation problem. We show that both problems are NP-hard to approximate within any finite factor. Given the strong inapproximability result, we design bicriteria approximations for both problems: we obtain a ( 6 , 6 ) (6,6) -approximation to the min cost nowhere-zero k k -flow and a ( k , 6 ) (k,6) -approximation to the min cost k k -cut-balanced orientation. For the case of symmetric costs (where the costs of both orientations are the same for every edge), we show that the nowhere-zero k k -flow problem remains NP-hard and admits a 3 3 -approximation. 1 Introduction Flows and colorings are disparate concepts in graph theory, especially from a computational perspective—flow problems are typically tractable while coloring problems are typically intractable. However, these two concepts are related in planar graphs via planar duality. Inspired by this connection, Tutte [ 43 , 44 ] introduced nowhere-zero flows to unify flows and colorings in arbitrary graphs. This unified viewpoint has driven several fundamental results in connectivity and orientations (e.g., see [ 46 ] and [ 5 ] ). Existence of nowhere zero flows is characterized by the existence of cut-balanced orientations [ 23 ] . Motivated by these connections, we investigate optimization problems associated with nowhere-zero flows and cut-balanced orientations. We begin by defining nowhere-zero flows, cut-balanced orientations, and the optimization problems of interest. In an undirected graph G=(V,E) , for a subset of vertices U\subseteq V , we denote the set of edges with exactly one end-vertex in U by \delta_{G}(U) . In a directed graph D=(V,A) , for U\subseteq V , we denote the arcs leaving and entering U by \delta^{+}_{D}(U) and \delta^{-}_{D}(U) respectively. For a subset of edges F\subseteq E , we denote \delta_{F}(U):=\delta_{G}(U)\cap F . Similarly, for a subset of arcs B\subseteq A , we define \delta_{B}^{\pm}(U):=\delta_{D}^{\pm}(U)\cap B . Let G=(V,E) be an undirected graph and k\geq 2 be an integer. A nowhere-zero k -flow in G is a tuple (\vec{E},f) , where \vec{E} is an orientation of E and f:\vec{E}\rightarrow\{1,2,...,k-1\} is a function that satisfies flow conservation, i.e., f(\delta_{\vec{E}}^{+}(v))=f(\delta_{\vec{E}}^{-}(v)) for every v\in V . A nowhere-zero flow is a nowhere-zero k -flow for some finite integer k\geq 2 . An orientation \vec{E} of E induces a nowhere-zero k -flow if there is a function f:\vec{E}\rightarrow\{1,2,...,k-1\} such that (\vec{E},f) is a nowhere-zero k -flow. An orientation \vec{E} of E is k -cut-balanced if |\delta_{\vec{E}}^{+}(U)|\geq\frac{1}{k}|\delta_{E}(U)|\ \forall U\subseteq V . A cut-balanced orientation is a k -cut-balanced orientation for some finite integer k\geq 2 . The bidirected graph of G=(V,E) , denoted \vec{G}=(V,E^{+}\cup E^{-}) , is obtained by making two copies e^{+}\in E^{+} and e^{-}\in E^{-} of every edge e\in E and orienting them in opposite directions. Let c:E^{+}\cup E^{-}\rightarrow\mathbb{Z}_{\geq 0} be costs on the arcs of the bidirected graph \vec{G} . The cost of an orientation \vec{E} is denoted by c(\vec{E}):=\sum_{e\in\vec{E}}c(e) and the cost of a nowhere-zero flow (\vec{E},f) is denoted by c(f):=\sum_{e\in\vec{E}}c(e)f(e) . We consider the following problems for a fixed integer k\geq 2 : Weighted nowhere-zero k -flow ( \operatorname{WNZF}(k) ) : Given: Undirected 2 -edge-connected graph G=(V,E) and costs c:E^{+}\cup E^{-} Goal: Find a nowhere-zero k -flow (\vec{E},f) with minimum cost c(f) . Weighted k -cut-balanced orientations ( \operatorname{WCBO}(k) ) : Given: Undirected 2 -edge-connected graph G=(V,E) and costs c:E^{+}\cup E^{-} Goal: Find a k -cut-balanced orientation \vec{E} with minimum cost c(\vec{E}) . The feasibility versions of \operatorname{WNZF}(k) and \operatorname{WCBO}(k) are the problems of determining whether a given undirected 2 -edge-connected graph has a nowhere-zero k -flow and a k -cut-balanced orientation, respectively. An orientation induces a nowhere-zero k -flow if and only if it is k -cut-balanced [ 23 , 16 , 17 , 41 ] . Hence, the feasibility versions of \operatorname{WNZF}(k) and \operatorname{WCBO}(k) are equivalent, and we will discuss their complexity shortly. We say that the cost function c:E^{+}\cup E^{-} is symmetric if c(e^{+})=c(e^{-}) for every e\in E and asymmetric otherwise. If the costs c are symmetric, \operatorname{WCBO}(k) is equivalent to the feasibility problem while \operatorname{WNZF}(k) is non-trivial. We denote \operatorname{WNZF}(k) for symmetric costs as \operatorname{SWNZF}(k) . We define \operatorname{WNZF}(\infty) as the problem of finding a min-cost nowhere-zero flow with no restriction on k , i.e., \operatorname{WNZF}(\infty):=\min\{c(f):\exists\ \vec{E}\text{ such that $(\vec{E},f)$ is a nowhere-zero $k$-flow for some integer $k\geq 2$}\}. We define \operatorname{WCBO}(\infty) and \operatorname{SWNZF}(\infty) analogously. In all optimization problems above, we assume that the input graph is 2 -edge-connected since this is a necessary condition for the existence of a nowhere-zero flow/cut-balanced orientation. 1.1 Background, Motivations, and Connections Nowhere-zero Flows. Nowhere-zero flow is a rich area of study in graph theory, with close connections to graph coloring and chromatic polynomials. We begin by observing that 2 -edge-connectivity is necessary and sufficient for the existence of a nowhere-zero flow. 1 1 1 The necessity of 2 -edge-connectivity for nowhere-zero flows follows from flow-conservation and nowhere-zero property. We sketch its sufficiency: we recall that every 2 -edge-connected graph G=(V,E) admits a strongly connected orientation \vec{E} , i.e., an orientation \vec{E} such that |\delta^{+}_{\vec{E}}(U)|\geq 1 for every \emptyset\neq U\subsetneq V ; such an orientation is a k -cut-balanced orientation for some sufficiently large integer k ; now, recall that an orientation is a k -cut-balanced orientation if and only if it induces a nowhere-zero k -flow [ 23 ] . Moreover, for integers k_{2}\geq k_{1}\geq 2 , a nowhere-zero k_{1} -flow is also a nowhere-zero k_{2} -flow. Given this, most works on nowhere-zero flows focused on the least integer k for which every 2 -edge-connected graph admits a nowhere-zero k -flow. Tutte [ 43 , 44 ] conjectured that every 2 -edge-connected graph has a nowhere-zero 5 -flow—we will call this Tutte’s 5 -flow conjecture. The Petersen graph does not have a nowhere-zero 4 -flow, showing that 5 is best possible. Jaeger [ 22 , 24 ] proved that every 2 -edge-connected graph has a nowhere-zero 8 -flow. Seymour [ 39 ] improved Jaeger’s result by showing that every 2 -edge-connected graph has a nowhere-zero 6 -flow. Seymour’s proof is non-constructive and a subsequent algorithmic proof was given by Younger [ 48 ] . DeVos and Nurse [ 7 ] gave a shorter proof of Seymour’s result which can also be made constructive. We now discuss the feasibility variants of \operatorname{WNZF}(k) and \operatorname{WCBO}(k) . A consequence of Seymour’s result is that for every integer k\geq 6 , all instances of both \operatorname{WNZF}(k) and \operatorname{WCBO}(k) are feasible. We now discuss the status for integers k\in\{2,3,4,5\} . An undirected graph admits a nowhere-zero 2 -flow if and only if it is