A network flow approach to a common generalization of Clar and Fries numbers

Bérczi-Kovács, Erika and Frank, András (2024) A network flow approach to a common generalization of Clar and Fries numbers. Discrete Mathematics, 347 (11). p. 114145. ISSN 0012365X

Preview

Text Fries.pdf Download (523kB) | Preview

Abstract

Clar number and Fries number are two thoroughly investigated parameters of plane graphs emerging from mathematical chemistry to measure stability of organic molecules. First, we introduce a common generalization of these two concepts for bipartite plane graphs, and then we extend it further to the notion of source-sink pairs of subsets of nodes in a general (not necessarily planar) directed graph. The main result is a min-max formula for the maximum weight of a source-sink pair. The proof is based on the recognition that the convex hull of source-sink pairs can be obtained as the projection of a network tension polyhedron. The construction makes it possible to apply any standard cheapest network flow algorithm to compute both a maximum weight source-sink pair and a minimizer of the dual optimization problem formulated in the min-max theorem. As a consequence, our approach gives rise to the first purely combinatorial, strongly polynomial algorithm to compute a largest (or even a maximum weight) Fries-set of a perfectly matchable plane bipartite graph and an optimal solution to the dual minimization problem.

Actions (login required)

Edit Item