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

Erika Bérczi-Kovács Alfréd Rényi Institute of Mathematics, Department of
Operations Research, ELTE Eötvös Loránd University, Budapest, Hungary, and
ELKH-ELTE Egerváry Research Group on Combinatorial Optimization. Contact:
<EMAIL_ADDRESS>András Frank Department of Operations
Research, ELTE Eötvös Loránd University, Budapest, Hungary, and ELKH-ELTE
Egerváry Research Group on Combinatorial Optimization. Contact:
<EMAIL_ADDRESS>
###### 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.

##  1 Introduction

This paper considers some optimization problems arising in mathematical
chemistry. A natural graph model to capture the basic structure of an organic
molecule uses a planar graph $G$ where the atoms are represented by nodes of
$G$ while the bonds between atoms correspond to the edges of $G$. Several
important parameters can be described with this approach, which gives rise to
challenging problems in combinatorial optimization. One of the most well-known
of these problems concerns the Clar number [6]. Clar’s empirical observation
states a connection between the stability of a so-called aromatic hydrocarbon
molecule and the maximum number of disjoint benzenoid rings, called the Clar
number. In the graph model, the Clar number of a molecule is the cardinality
of the largest Clar-set, where a Clar-set of a perfectly matchable planar
graph $G$ embedded in the plane consists of some disjoint inner faces of $G$
that can simultaneously alternate with respect to an appropriate perfect
matching of $G$.

Another important parameter of a molecule is its Fries number [11, 16]. In the
graph model, the Fries number of a perfectly matchable planar graph $G$
embedded in the plane is the maximum cardinality of a Fries-set, where a
Fries-set consists of some distinct but not necessarily disjoint inner faces
that can simultaneously alternate with respect to an appropriate perfect
matching of $G$.

A major issue of the investigations is the algorithmic and structural aspects
of Clar and Fries numbers and sets, in which the polyhedral approach (that is,
linear programming) plays a central role. We concentrate on 2-connected
perfectly matchable bipartite plane graphs $G=(S,T;E)$, where a plane graph
means a planar graph with a given embedding in the plane. (Recall that a
polyhedron is the solution set of a linear inequality system, while a polytope
is the convex hull of a finite number of points. A fundamental theorem of
linear programming states that every polytope is a bounded polyhedron. In
discrete optimization, it is often a basic, non-trivial approach to provide
explicitly such a linear description of the polytope of combinatorial objects
to be investigated.)

Consider first the situation with Clar numbers and sets. Hansen and Zheng [15]
(using different notation) introduced a polyhedron
$P=\\{(x^{\prime},x^{\prime\prime}):Fx^{\prime}+Qx^{\prime\prime}=1,\
(x^{\prime},x^{\prime\prime})\geq 0\\}$, where $F$ is the node vs inner-face
incidence matrix of $G$ while $Q$ is the standard node-edge incidence matrix
of $G$ (and hence $[F,Q]$ is a small size $(0,1)$-matrix). They considered the
projection $P_{\rm Cl}:=\\{x^{\prime}:\ \exists\ x^{\prime\prime}$ with
$(x^{\prime},x^{\prime\prime})\in P\\}$ of $P$ to the variables $x^{\prime}$
and observed that the integral (that is, $(0,1)$-valued) elements of $P_{\rm
Cl}$ correspond to the Clar-sets of $G$. Hansen and Zheng conjectured that $P$
(and hence $P_{\rm Cl}$) is an integral polyhedron, which property, if true,
implies that the vertices of $P_{\rm Cl}$ correspond to the Clar-sets of $G$.

Abeledo and Atkinson [2] (Theorem 3.5) proved that $[F,Q]$ is a unimodular
matrix (though not always totally unimodular). This implied the truth of the
conjecture of Hansen and Zheng since a theorem of Hoffman and Kruskal [18]
(see Theorem 21.5 in the book [24] of Schrijver) implies that, for a
unimodular matrix $[A,A^{\prime}]$ and integral vector $b$, the polyhedron
$\\{(x,x^{\prime}):Ax+A^{\prime}x^{\prime}=b,x\geq 0\\}$ is integral (and so
is the dual polyhedron $\\{y:yA\geq c,yA^{\prime}=c^{\prime}\\}$ whenever
$(c,c^{\prime})$ is an integral vector.)

A tiny remark is in order. It follows from the previous approach that $P_{\rm
Cl}$ is the polytope of Clar-sets, and $P_{\rm Cl}$ was obtained as a
projection of the polyhedron $P$. At first sight, it may seem more natural to
figure out an explicit polyhedral description of $P_{\rm Cl}$ itself. However,
the linear inequality system describing $P_{\rm Cl}$ may consist of an
exponential number of inequalities. This is why it is more efficient to
produce $P_{\rm Cl}$ as the projection of the (integral) polyhedron $P$ that
is described by only $O(|E|)$ constraints. Of course, a maximum weight vertex
of $P_{\rm Cl}$ (that is, a maximum weight Clar-set) can be computed once a
maximum weight vertex of $P$ can be.

Abeledo and Atkinson [2] noted that an analogous approach works for Fries-
sets, as well. Namely, in Theorem 3.6 of [2] they claimed (without a proof)
that a certain matrix $A$ is unimodular, and indicated that the Fries-sets
correspond to the vertices of the a projection $P_{\rm Fr}$ of the polyhedron
defined by $A$. It should be noted that $A$ is a small size $(0,\pm
1)$-matrix.

Since the sizes of the describing unimodular matrices are small (a linear
function of the size of the graph $G$), a general purpose linear programming
algorithm can be used to compute an optimal (maximum weight) basic solution
which corresponds to an optimal Clar-set (Fries-set). Moreover, as the
matrices are $(0,\pm 1)$-valued, the strongly polynomial time algorithm of
Tardos [25] for solving such linear programs can be applied. Therefore, there
exists a strongly polynomial algorithm for computing both a maximum weight
Clar-set and a maximum weight Fries-set.

In addition, Abeledo and Atkinson [3] provided a network flow formulation for
the dual of the Clar problem, and hence, as they write: ”the Clar number and
the cut cover can be found in polynomial time by solving a minimum cost
network flow problem”. Yet another fundamental result of Abeledo and Atkinson
[3] is an elegant min-max formula for the Clar number of a plane bipartite
graph, which was conjectured by Hansen and Zheng [14, 15].

As for a min-max formula concerning the Fries number, the above-mentioned
linear programming approach of Fries-sets [2] does provide one through the
l.p. duality theorem, though this was not explicitly formulated (in a form
similar to the one mentioned before concerning Clar numbers). Moreover, to our
best knowledge, no purely combinatorial or network flow based algorithm
appears in the literature for computing the Fries number of $G$.

The major goal of the present work is to develop a common generalization of
the Clar number and Fries number problems, and based on this, to develop a
strongly polynomial algorithm relying exclusively on standard network flow
subroutines. Our approach is self-contained, in particular, it does not rely
on any earlier polyhedral results on Clar-sets and Fries-sets.

We note that the presented common framework for Clar-sets and Fries-sets has
nothing to do with a popular conjecture stating that a plane graph has a
largest Clar-set that can be extended to a largest Fries-set. This conjecture
was disproved by Hartung [17] for general plane graphs (for fullerenes),
proved for a special class of benzenoids by Graver et al. [13], but it is
still open for general perfectly matchable bipartite plane graphs.

A basic tool of our approach is that we reformulate the original problem on
$G$ for the planar dual graph of $G$, and then we can drop the planarity
assumption. This idea appeared in the work of Erdős, Frank, and Kun [7], where
the major problem was to find a largest (weight) sink-stable set of a (not
necessarily planar) digraph $D=(V,A)$. Here the term sink-stable refers to a
stable set of $D$ whose elements are sink nodes in an appropriate dicut-
equivalent reorientation of $D$, where a digraph $D^{\prime}=(V,A^{\prime})$
is a dicut-equivalent reorientation of $D$ if it can be obtained from $D$ by
reorienting some disjoint one-way cuts ($=$ dicuts). (Incidentally we remark
that this digraph model not only covered the (weighted) Clar number problem
but implied an elegant theorem of Bessy and Thomassé [5] as well as its
extension by Sebő [21].)

The Fries number problem can also be embedded into this general digraph
framework, where it transforms into finding a dicut-equivalent reorientation
of a digraph in which the set of sink and source nodes is as large as
possible. However, this requires a technique more involved than the one needed
for Clar numbers (see Remark 5.10).

Our goal, in fact, is to develop a common framework for these extensions of
the Clar and Fries problems. Namely, in Section 1.1, we introduce the notion
of source-sink (so-si) pairs $\\{Y_{\text{o}},Y_{\text{i}}\\}$ of disjoint
subsets of nodes of $D$, and, for a given pair of weight-functions
$\\{w_{\text{o}},w_{\text{i}}\\}$, develop a min-max formula (Theorem 4.1) for
the maximum total weight
$\widetilde{w}_{\text{o}}(Y_{\text{o}})+\widetilde{w}_{\text{i}}(Y_{\text{i}})$
of a so-si pair. The proof is based on the revelation that the convex hull of
(the characteristic vectors of) so-si pairs can be obtained as the projection
of a network tension polyhedron (of $3|V|$-dimension), and hence the maximum
weight so-si pair problem can be transformed into a maximum weight feasible
tension problem. As such a tension problem is the linear programming dual of a
minimum cost network flow (or circulation) problem, the approach not only
results in a (combinatorial) min-max formula but it also gives rise to a
strongly polynomial algorithm that relies exclusively on standard network flow
subroutines.

###  1.1 Notation, terminology

Given a ground-set $S$, we do not distinguish between a vector $c\in{\bf
R}^{S}$ and a function $c:S\rightarrow{\bf R}$. For a vector or function $c$
on $S$, let $\widetilde{c}(X):=\sum\ [c(s):s\in X]$.

We call a digraph weakly connected or just connected if its underlying
undirected graph is connected. Often we refer to the edges of a digraph as
arcs. Let $D=(V,A)$ be a loopless connected digraph with $n\geq 2$ nodes. For
a subset $U$ of nodes, the in-degree
$\varrho(U)=\varrho_{D}(U)=\varrho_{A}(U)$ is the number of arcs entering $U$,
while the out-degree $\delta(U)=\delta_{D}(U)=\delta_{A}(U)$ is the number of
arcs leaving $U$. Typically, we do not distinguish between a one-element set
$U=\\{u\\}$ and its only element $u$, for example,
$\varrho(u)=\varrho(\\{u\\})$. For a vector (or function) $z$ on the arc-set
$A$ of $D$, let $\varrho_{z}(U):=\sum\ [z(e):e$ enters $U]$ and
$\delta_{z}(U):=\sum\ [z(e):e$ leaves $U]$.

A function $z$ defined on the arc-set of $D$ is called a circulation in $D$ if
$\varrho_{z}(v)=\delta_{z}(v)$ holds for every node $v$. This is equivalent to
requiring that $\varrho_{z}(v)\leq\delta_{z}(v)$ holds for every node $v$.
Furthermore, for a circulation $z$, $\varrho_{z}(U)=\delta_{z}(U)$ holds for
any subset $U\subseteq V$. For lower and upper bound functions $f,g$, we say
that a circulation $z$ is feasible if $f\leq z\leq g$. (Here $-\infty$ is
allowed for the components of $f$ and $+\infty$ for the components of $g$.)

A function $\pi$ defined on the node-set of $D$ is often referred to a
potential, which induces the tension $\Delta_{\pi}$ (sometimes called
potential-drop) on the arc-set of $D$, where $\Delta_{\pi}(uv):=\pi(v)-\pi(u)$
for $uv\in A$. An integer-valued tension can be obtained as the potential-drop
of an integer-valued potential. It is a well-known property that the set of
circulations and the set of tensions are complementary orthogonal subspaces
(over the rationals or the reals), that is, $z\Delta_{\pi}=0$ holds for any
circulation $z$ and potential $\pi$. We call an integer-valued potential $\pi$
small-dropping if its potential-drop $\Delta_{\pi}$ is $(0,1)$-valued. When
$\Delta_{\pi}$ is $(0,1)$-valued only on a subset $A_{0}\subseteq A$ of arcs,
we say that $\pi$ is small-dropping on $A_{0}$.

For given lower bound $c_{\ell}:A\rightarrow{\bf R}\cup\\{-\infty\\}$ and
upper bound $c_{u}:A\rightarrow{\bf R}\cup\\{+\infty\\}$, we say that a
potential $\pi$ or the potential drop $\Delta_{\pi}$ is
$(c_{\ell},c_{u})$-feasible if $c_{\ell}\leq\Delta_{\pi}\leq c_{u}$. When
$c_{\ell}\equiv-\infty$ (that is, when no lower bound is given), we speak of
$c_{u}$-feasibility.

A circuit is a connected undirected graph in which the degree of every node is
2. For a circuit $C$, we use the convention that $C$ also denotes the edge-set
of the circuit while $V(C)$ denotes its node-set. A directed graph is also
called a circuit if it arises from an undirected circuit by arbitrarily
orienting its edges. A directed graph obtained from an undirected circuit by
orienting each edge in the same direction is called a one-way circuit or just
a di-circuit.

We call two orientations of an undirected graph di-circuit equivalent if one
of them can be obtained from the other one by reorienting a set of arc-
disjoint di-circuits. This is clearly equivalent to requiring that the in-
degree of a node on one orientation is equal to the in-degree in the other
orientation.

By reorienting (or reversing) an arc $uv$, we mean the operation of replacing
$uv$ by $vu$. The reorientation of a subset $B$ of arcs (that is, reversing
$B$) means that we reorient all the elements of $B$.

By a cut of a connected graph $G=(V,E)$, we mean the set of edges connecting
$Z$ and $V-Z$ for some subset $Z$ of nodes. By a minimal cut we mean an
inclusionwise minimal cut. A useful observation is that a cut is minimal if
and only if both $Z$ and $V-Z$ induce a connected subgraph of $G$.
Furthermore, every cut can be partitioned into minimal cuts. An minimal cut is
sometimes called a bond, but this term should not be confused with a bond used
in chemistry (which corresponds to an edge of the modelling graph).

By a cut of a digraph $D=(V,A)$ defined by a subset $Z$ of nodes, we mean the
set of arcs connecting $Z$ and $V-Z$ (in either direction). In the special
case when no arc enters $Z$, the cut is called a directed cut or a dicut of
$D$. Sometimes the term one-way cut is used for a dicut. We say that digraph
$D^{\prime}=(V,A^{\prime})$ is called a dicut-equivalent reorientation of $D$
if $D^{\prime}$ is obtained from $D$ by reorienting some disjoint one-way cuts
of $D$ (see [7]). A node of $D$ will be called a sink node (or just a sink) if
it admits no leaving arcs. A node is a source node if it admits no entering
arcs. A subset of nodes is a sink set (respectively, a source set) if each of
its elements is a sink (resp., a source). Clearly, a sink set is always
stable.

We call a subset $Y$ of nodes of $D$ sink-stable (source-stable) if there is a
dicut-equivalent reorientation of $D$ in which every node in $Y$ is a sink
node (source node). Obviously, a set is sink-stable if and only if it is
source-stable. These are special stable sets of $D$, and a node of a one-way
circuit of $D$ never belongs to a sink-stable set of $D$.

For two disjoint sets $Y_{\rm o},Y_{\rm i}\subseteq V$, we call the ordered
pair $(Y_{\rm o},Y_{\rm i})$ a source-sink (= so-si) pair if there is a dicut-
equivalent reorientation of $D$ in which $Y_{\rm o}$ is a source set while
$Y_{\rm i}$ is a sink set. It may be the case that $(Y_{\rm o},Y_{\rm i})$ is
a so-si pair, but $(Y_{\rm i},Y_{\rm o})$ is not (as exemplified by an acyclic
orientation of a triangle). For a subset $Y$ of nodes the following four
properties are obviously equivalent: $Y$ is a sink-stable set, $Y$ is a
source-stable set, $(Y,\emptyset)$ is a so-si pair, $(\emptyset,Y)$ is a so-si
pair.

We call a subset $Y$ of nodes of $D$ resonant if it can be partitioned into
subsets $Y_{\rm o}$ and $Y_{\rm i}$ where $(Y_{\rm o},Y_{\rm i})$ is a so-si
pair. (The name is motivated by the term resonant set of faces of a plane
graph, see, for example, [29]). A sink-stable (or source-stable) set is
clearly resonant111The term ’resonant’ has different definitions in the
literature, sometimes it is a synonym of a Clar-set. In this paper we use it
as a generalization of a Fries-set..

##  2 Undirected plane graphs and directed general graphs

Recall a basic result of Fáry [8] stating that every simple planar graph
admits an embedding in the plane where each edge is represented by a straight-
line segment. A deeper result of Tutte [26] states that a 3-connected simple
planar graph admits an embedding into the plane in which every edge is
represented by a straight-line segment and the faces are convex sets.

Let $G=(V,E)$ be a loopless 2-connected planar graph. Throughout we consider a
specified embedding of $G$ into the plane, and say that $G$ is a plane graph.
Such an embedded graph divides the plane into disjoint (connected) regions,
exactly one of them is infinite. We refer to these regions as the faces of the
plane graph. Since $G$ is 2-connected, its faces are surrounded by a circuit
of $G$, and we refer to these as face-bounding circuits or just face-circuits.
(In the literature, often the longer term boundary circuit is used.) With a
slight abuse of terminology, sometimes we do not distinguish between a face
and its face-circuit. The single infinite face is called the outer face of $G$
while all the other faces are the inner faces of $G$. For their surrounding
circuits, we use the term outer (inner) face-circuit.

Note that the set of face-circuits may be different for another embedding of a
planar graph into the plane, but for 3-connected planar graphs, by a theorem
of Tutte, the set of face-circuits is independent from the embedding.

Let $F$ be a face of $G$ and $C_{F}$ its face-circuit. Let
$\stackrel{{\scriptstyle\rightarrow}}{{G}}$ be an orientation of $G$ in which
the orientation $\stackrel{{\scriptstyle\rightarrow}}{{C}}_{F}$ of $C_{F}$ is
a one-way circuit. When we say that the face $F$ and the di-circuit
$\stackrel{{\scriptstyle\rightarrow}}{{C}}_{F}$ is clockwise (anti-clockwise)
oriented, we mean that it is clockwise (anti-clockwise) when looked at from
the inside of $F$. (Or putting it in another way, we may imagine that
$\stackrel{{\scriptstyle\rightarrow}}{{G}}$ is embedded on the surface of a
sphere, with no distinction between the outer face and the inner faces, and a
one-way face-circuit is clockwise in the usual sense.)

As a simple example, let the graph be a single circuit $C$ embedded in the
plane and let $\stackrel{{\scriptstyle\rightarrow}}{{C}}$ be an orientation of
$C$ which is a one-way circuit. Now the graph has one inner face and one outer
face, $C$ is a one-way face-circuit belonging to both faces, and
$\stackrel{{\scriptstyle\rightarrow}}{{C}}$ is clockwise with respect to the
inner face if and only if it is anti-clockwise with respect to the outer face.

It follows from this definition that if $F_{1}$ and $F_{2}$ are neighbouring
(incident) faces of $G$ (that is, they have an edge in common) and their face-
circuits are one-way circuits in $\stackrel{{\scriptstyle\rightarrow}}{{G}}$,
then one of $F_{1}$ and $F_{2}$ is clockwise in
$\stackrel{{\scriptstyle\rightarrow}}{{G}}$ while the other is anti-clockwise.

Throughout the paper, we assume that $G=(S,T;E)$ is a perfectly matchable,
2-connected, loopless, bipartite plane graph. Let $M$ be a perfect matching of
$G$. A circuit $C$ of $G$ is called $M$-alternating if edges in $C\cap M$ and
$C-M$ are alternating on $C$. If $M^{\prime}$ is another perfect matching of
$G$, then the symmetric difference $M\ominus
M^{\prime}:=(M-M^{\prime})\cup(M^{\prime}-M)$ of $M$ and $M^{\prime}$ consists
of disjoint circuits which are both $M$-alternating and
$M^{\prime}$-alternating.

A set ${\cal C}^{\prime}$ of node-disjoint face-circuits of $G$ forms a Clar-
set if $G$ has a perfect matching $M$ such that each member of ${\cal
C}^{\prime}$ is $M$-alternating.

A set ${\cal C}^{\prime}$ of (distinct) face-circuits of $G$ forms a Fries-set
if $G$ has perfect matching $M$ such that each member of ${\cal C}^{\prime}$
is $M$-alternating. Sometimes a Fries-set is called a resonant set of faces or
face-circuits [29].

Let ${\cal C}_{G}$ denote the set of face-circuits of $G$ (including the outer
face). For a non-empty subset ${\cal C}^{\prime}$ of ${\cal C}_{G}$, the Clar
number Cl$({\cal C}^{\prime})=$ Cl${}_{G}({\cal C}^{\prime})$ of $G$ within
${\cal C}^{\prime}$ is the maximum cardinality of a Clar-set consisting of
some members of ${\cal C}^{\prime}$. When ${\cal C}^{\prime}$ is the set of
inner faces, we simply speak of the Clar number of $G$. It should be noted
that the Clar number of two different embeddings of a planar graph into the
plane with the same outer face may be different (unless the graph is
3-connected).

For a non-empty subset ${\cal C}^{\prime}$ of face-circuits, the Fries number
Fr$({\cal C}^{\prime})=$ Fr${}_{G}({\cal C}^{\prime})$ of $G$ within ${\cal
C}^{\prime}$ is the maximum cardinality of a Fries-set consisting of some
members of ${\cal C}^{\prime}$. When ${\cal C}$ is the set of all inner faces,
we simply speak of the Fries number of $G$.

The basic optimization problem for Clar (respectively, Fries) numbers is (A)
to compute the Clar (Fries) number of $G$ as well as a maximizing Clar-set
(Fries-set) consisting of inner face-circuits. In a slightly more general
version, we are interested in (B) finding a maximum cardinality Clar-set
(Fries-set) within a specified subset of face-circuits. An even more general
form is (C) the weighted Clar-set (Fries-set) problem where we are given a
non-negative weight-function $w$ on the set of faces (face-circuits), and want
to construct a Clar-set (Fries-set) of largest weight. (When $w$ is
$(0,1)$-valued we are back at Problem (B), while Problem (A) is obtained for
the special weight-function $w$ defined to be $1$ on all inner faces and $0$
on the outer face.) In what follows, we consider a weighted version of a
common generalization of Clar-sets and Fries-sets.

###  2.1 Common framework for Clar and Fries

For any perfect matching $M$ of $G$, we define an orientation
$\stackrel{{\scriptstyle\rightarrow}}{{G}}_{M}$ of $G$, as follows. Orient
each element of $M$ toward $S$ while all the other edges of $G$ toward $T$.
Then a face (and its face-circuit) of $G$ is $M$-alternating if and only if it
is a one-way circuit in the orientation
$\stackrel{{\scriptstyle\rightarrow}}{{G}}_{M}$. Note that every one-way
circuit of $\stackrel{{\scriptstyle\rightarrow}}{{G}}_{M}$ is clockwise or
anti-clockwise.

We will say that an $M$-alternating face-circuit of $G$ is clockwise (anti-
clockwise) if the corresponding one-way circuit in
$\stackrel{{\scriptstyle\rightarrow}}{{G}}_{M}$ is clockwise (anti-clockwise).
It follows for two adjacent $M$-alternating faces that one of them is
clockwise, while the other one is anti-clockwise. Furthermore, both the set of
clockwise $M$-alternating face-circuits and the set of anti-clockwise
$M$-alternating face-circuits are Clar-sets, and their union is a Fries-set.
And conversely, every Fries-set ${\cal F}^{\prime}$ can be obtained in this
way. Indeed, if $M$ is a perfect matching for which the members of ${\cal
F}^{\prime}$ are $M$-alternating, then both the set of clockwise
$M$-alternating members and the set of anti-clockwise $M$-alternating members
of ${\cal F}^{\prime}$ are Clar-sets.

Observe that for any Clar-set ${\cal C}^{\prime}$ there is a perfect matching
$M^{\prime}$ such that each member of ${\cal C}^{\prime}$ is
$M^{\prime}$-alternating and clockwise. Indeed, by definition, there is a
perfect matching $M$ for which each member of ${\cal C}^{\prime}$ is
$M$-alternating. Then the perfect matching $M^{\prime}$ obtained by taking the
symmetric difference of $M$ and the union of anti-clockwise members of ${\cal
C}^{\prime}$ will do.

Let $w_{1}$ and $w_{2}$ be two non-negative weight-functions on the set of
faces of $G$. In the common generalization of the weighted Fries and Clar
problems, we look for a perfect matching $M$ of $G$ for which the sum of the
total $w_{1}$-weight of the clockwise $M$-alternating face-circuits plus the
total $w_{2}$-weight of the anti-clockwise $M$-alternating face-circuits is as
large as possible. We refer to this common framework as the double-weighted
Clar-Fries problem, see Problem 1 below.

In the special case when $w_{1}:=w$ and $w_{2}:=0$, we are back at the maximum
$w$-weighted Clar-set problem. In the special case when $w_{1}:=w$ and
$w_{2}:=w$, we are back at the maximum $w$-weighted Fries-set problem.

Input: A perfectly matchable 2-connected plane bipartite graph $G=(S,T,E)$
with non-negative weightings $w_{1}$ and $w_{2}$ on the set of faces of $G$.

Output: A perfect matching $M$ of $G$ for which the sum of the total
$w_{1}$-weight of the clockwise $M$-alternating face-circuits plus the total
$w_{2}$-weight of the anti-clockwise $M$-alternating face-circuits is maximum.

Problem 1 Double-weighted Clar-Fries problem

We shall show that Problem 1 can be embedded in the following, significantly
more general framework concerning directed graphs.

Input: A loopless, weakly connected (non-necessarily planar) digraph $D=(V,A)$
with non-negative weightings $w_{\rm o}$ and $w_{\rm i}$ on $V.$

Output: A dicut-equivalent reorientation of $D$ for which the sum of the total
$w_{\rm o}$-weight of source nodes plus the total $w_{\rm i}$-weight of sink
nodes is maximum.

Problem 2 Double-weighted source-sink pair problem

######  Claim 2.1.

The double-weighted Clar-Fries problem formulated in Problem 1 is a special
case of the double-weighted source-sink pair problem formulated in Problem 2.

Proof. Let $M$ be an arbitrary perfect matching of $G$, and consider the
planar dual digraph $D_{M}$ of $\stackrel{{\scriptstyle\rightarrow}}{{G}}_{M}$
(where each dual arc is oriented from the left to the right with respect to
the primal arc). The weight-functions $w_{1}$ and $w_{2}$ on the set of faces
of $G$ can be associated with weight-functions $w_{\rm o}$ and $w_{\rm i}$ on
the set of nodes of $D_{M}$. Observe that for another perfect matchings
$M^{\prime}$ of $G$, the orientations
$\stackrel{{\scriptstyle\rightarrow}}{{G}}_{M}$ and
$\stackrel{{\scriptstyle\rightarrow}}{{G}}_{M^{\prime}}$ are di-circuit
equivalent and hence $D_{M}$ and $D_{M^{\prime}}$ are dicut-equivalent.
Conversely, any dicut-equivalent reorientation of $D_{M}$ arises in this way
(that is, there is a perfect matching $M^{\prime}$ of $G$ for which the
orientations $\stackrel{{\scriptstyle\rightarrow}}{{G}}_{M}$ and
$\stackrel{{\scriptstyle\rightarrow}}{{G}}_{M^{\prime}}$ are di-circuit
equivalent). Therefore there is a one-to-one correspondence between the so-si
pairs of $D_{M}$ and the set of clockwise and anticlockwise faces of $G$
belonging to a perfect matching $M^{\prime}$ of $G$. It follows that Problem
2, when applied to $D_{M}$ in place of $D$, outputs a so-si pair $(Y_{\rm
o},Y_{\rm i})$ for which its double-weight
$\widetilde{w}_{\text{o}}(Y_{\text{o}})+\widetilde{w}_{\text{i}}(Y_{\text{i}})$
is maximum, and this pair $(Y_{\rm o},Y_{\rm i})$ corresponds to a pair of
clock-wise and anti-clock-wise $M^{\prime}$-alternating faces with a maximum
$(w_{1},w_{2})$ double weight.

Note that the problem of finding a dicut-equivalent reorientation of a digraph
$D$ for which the total weight of the set of sink nodes is as large as
possible is a special case of this problem and was solved by Erdős, Frank, and
Kun [7]. Theorem 4.1 of [7] states that a stable set of $D$ is sink-stable if
and only if $|S\cap V(C)|\leq\eta(C)$ holds for every circuit $C$ of $D$,
where $\eta(C)$ denotes the minimum of the number of forward arcs of $C$ and
the number of backward arcs of $C$. By extending this result, we shall derive
an analogous characterization of source-sink pairs in Section 3. Resonant sets
will be characterized in Corollary 5.9 in terms of integer-valued circulations
(and not only circuits). Perhaps a bit surprisingly, no characterization of
resonant sets may exist that requires an inequality only for circuits, see
Remark 5.10.

In another approach, clockwise and anti-clockwise M-alternating edge sets
appear in the formulation of Abeledo and Ni [1], who gave an LP description
for the Fries number of plane bipartite graphs using a TU matrix.

Shi and Zhang [23] considered $(4,6)$-fullerenes, and gave a formula for a
variation of the Fries number problem when only the number of alternating
hexagonal faces is to be maximized. Note that this problem is a special case
of the Fries number within a subset ${\cal C}^{\prime}$ of face-circuits
defined above, by choosing ${\cal C}^{\prime}$ to be the set of hexagonal
faces.

We conclude this section by remarking that the problems above concerning Clar
and Fries numbers can be considered for non-bipartite plane graphs, as well.
It was shown by Bérczi-Kovács and Bernáth [4] that computing the Clar number
is NP-hard for general plane graphs, but the problem is open if the number of
odd faces is constant. This is the case, for example, for fullerene graphs (a
3-connected 3-regular planar graph with hexagonal faces and exactly six
pentagonal faces). The status of the Fries number problem for general plane
graphs is open. Salami and Ahmadi in [20] gave both integer and quadratic
programming formulations for the Fries number of fullerenes.

##  3 Characterizing source-sink pairs

In this section we describe a characterization of source-sink pairs of a
digraph $D=(V,A)$. Recall the notion of dicut-equivalence of two orientations
of an undirected graph. It was observed in [7] (Lemma 3.1) that a subset
$F\subseteq A$ of arcs is the union of disjoint one-way cuts if and only if
there is an integer-valued potential $\pi$ for which $\chi_{F}=\Delta_{\pi}$,
where $\chi_{F}\in\\{0,1\\}^{A}$ is the incidence vector of $F$. This
immediately implies the following observation.

######  Claim 3.1.

Digraph $D$ admits a dicut-equivalent reorientation $D^{\prime}$ if and only
if there is a potential $\pi:V\rightarrow{\bf Z}_{+}$ which is small-dropping
on $A$ and $D^{\prime}$ arises from $D$ by reversing those arcs $e$ of $D$ for
which $\Delta_{\pi}(e)=1$.

Let $f:A\rightarrow{\bf R}\cup\\{-\infty\\}$ and $g:A\rightarrow{\bf
R}\cup\\{+\infty\\}$ be lower and upper bound functions on the arc-set of
$D=(V,A)$, respectively, for which $f\leq g$. By the extended (but equivalent)
form of Gallai-lemma [12], there is an $(f,g)$-feasible tension if and only
if, for every circuit $C$ of $D$, the total $f$-value on the arcs of $C$ in
one direction is at most the total $g$-value on the arcs in the other
direction. (In the original Gallai-lemma $f\equiv-\infty$ in which case the
condition reduces to requiring that $g$ is conservative, that is, $D$ admits
no one-way circuit with negative $g$-weight. This immediately implies the
extended form by adding the reverse $\stackrel{{\scriptstyle\leftarrow}}{{e}}$
of each arc $\in A$ to $D$ and define
$g(\stackrel{{\scriptstyle\leftarrow}}{{e}}):=-f(e)$.)

Let $F$ and $R$ be two disjoint subsets of arcs of digraph $D=(V,A)$. We
consider the members of $F$ as fixed arcs while the elements of $R$ must be
reversed. Let $N:=A-(F\cup R)$ denote the complement of $F\cup R$.

######  Claim 3.2.

For a partition $\\{F,R,N\\}$ of the arc-set of digraph $D=(V,A)$, the
following are equivalent.

(A) $D$ admits a dicut-equivalent reorientation for which every element of $R$
is reversed while the orientation of every element of $F$ is unchanged.

(B) There is a small-dropping potential $\pi$ for which

$\Delta_{\pi}(e)=\begin{cases}1&\ \ \hbox{if}\ \ \ e\in R\cr 0&\ \ \hbox{if}\
\ \ e\in F.\end{cases}$ (1)

(C) For every circuit of $D$, the number of $R$-arcs in one direction is at
most the number of $(R\cup N)$-arcs in the other direction.

Proof. The equivalence of conditions (A) and (B) follows from Claim 3.1. Let

$(f(e),g(e)):=\begin{cases}(0,0)&\ \ \hbox{if}\ \ \ e\in F\cr(1,1)&\ \
\hbox{if}\ \ \ e\in R\cr(0,1)&\ \ \hbox{if}\ \ \ e\in N.\end{cases}$

It follows from this definition that a small-dropping potential $\pi$ meets
(1) if and only if $\Delta_{\pi}$ is $(f,g)$-feasible. For a circuit of $D$,
the sum of the $f$-values of the arcs in one direction is the number of
$R$-arcs in this direction, and the sum of the $g$-values of the arcs of $C$
in the other direction is the number of $(R\cup N)$-arcs in that direction.
Therefore the extended Gallai-lemma implies the equivalence of Conditions (B)
and (C).

In digraph $D=(V,A)$, let $Y_{\rm o}\subseteq V$ and $Y_{\rm i}\subseteq V$ be
disjoint stable sets for which we want to decide whether $(Y_{\rm o},Y_{\rm
i})$ is a so-si pair. Of course, if no arc enters $Y_{\rm o}$ and no arc
leaves $Y_{\rm i}$, then $(Y_{\rm o},Y_{\rm i})$ is a so-si pair. We refer to
an arc $e\in A$ as incorrect if it enters $Y_{\rm o}$ or leaves $Y_{\rm i}$,
while $e$ is considered correct if it leaves $Y_{\rm o}$ or enters $Y_{\rm
i}$. We refer to those members of $A$ which are neither correct nor incorrect
as neutral arcs.

######  Theorem 3.3.

For disjoint node-sets $Y_{\rm o}\subseteq V$, $Y_{\rm i}\subseteq V$ of
digraph $D=(V,A)$, the following properties are equivalent.

(A) $(Y_{\rm o},Y_{\rm i})$ is a so-si pair.

(B) There is a small-dropping potential $\pi$ on $V$ for which

$\Delta_{\pi}(e)=\begin{cases}1&\ \ \hbox{if}\ \ \ e\in A\ \
\hbox{incorrect}\cr 0&\ \ \hbox{if}\ \ \ e\in A\ \ \hbox{correct.}\end{cases}$
(2)

(C) For every circuit of $D$, the number of incorrect arcs in one direction is
at most the total number of correct arcs and neutral arcs in the other
direction.

Proof. By definition, $(Y_{\rm o},Y_{\rm i})$ is a so-si pair if and only if
$D$ admits a dicut-equivalent reorientation $D^{\prime}$ in which $Y_{\rm o}$
is a source set and $Y_{\rm i}$ is a sink set, that is, the incorrect arcs in
$D^{\prime}$ are reversed while the correct arcs are unchanged. Let $R$ denote
the set of incorrect arcs and $F$ the set of correct arcs. Then the properties
(A), (B), and (C) occurring in Claim 3.2 are just equivalent to those in the
theorem.

In the rest of the paper, we are going to prove a min-max theorem for the
maximum $w$-weight of a resonant set. Actually, we do this in a more general
form when $w_{\rm o}:V\rightarrow{\bf R}_{+}$ and $w_{\rm i}:V\rightarrow{\bf
R}_{+}$, are two given weight-functions and we are interested in finding a so-
si pair $(Y_{\rm o},Y_{\rm i})$ whose $(w_{\rm o},w_{\rm i})$-weight defined
by $\widetilde{w}_{\rm o}(Y_{\rm o})+\widetilde{w}_{\rm i}(Y_{\rm i})$ is
maximum. As the problem will be formulated as a network circulation problem in
a larger digraph $D^{*}$, a standard algorithm for the latter one will compute
the optimal solutions occurring in the min-max theorem (Theorem 4.1).

##  4 Min-max formula and algorithm for double-weighted source-sink pair

In this section, we exhibit first a min-max formula for the maximum $(w_{\rm
o},w_{\rm i})$-weight of a so-si pair of digraph $D=(V,A)$. As a preparation
for its proof (to be worked out in Section 5), we describe here a feasible
circulation problem on a larger digraph $D^{*}$ along with its linear
programming dual, a feasible tension problem. The algorithmic aspects of the
approach will be discussed in Section 5.3.

###  4.1 The main theorem

Let $\stackrel{{\scriptstyle\leftarrow}}{{A}}$ denote the set of arcs obtained
from $A$ by reversing all the arcs in $A$. Let
$\stackrel{{\scriptstyle\leftrightarrow}}{{A}}:=A\cup\stackrel{{\scriptstyle\leftarrow}}{{A}}$
and
$\stackrel{{\scriptstyle\leftrightarrow}}{{D}}:=(V,\stackrel{{\scriptstyle\leftrightarrow}}{{A}})$.
That is, $\stackrel{{\scriptstyle\leftrightarrow}}{{D}}$ is the digraph
arising from $D$ by adding the reverse of its arcs.

For a non-negative vector $z_{\rm i}$ defined on the arc-set
$\stackrel{{\scriptstyle\leftrightarrow}}{{A}}$, we say that $z_{\rm i}$ is an
in-cover of $w_{\rm i}$ if $\varrho_{z_{\rm i}}(v)\geq w_{\rm i}(v)$ holds for
every node $v\in V$ (where $\varrho_{z_{\rm i}}(v)$ denotes the sum of
$z_{i}$-values on the arcs in $\stackrel{{\scriptstyle\leftrightarrow}}{{A}}$
entering $v$). Analogously, a non-negative vector $z_{\rm o}$ is said to be an
out-cover of $w_{\rm o}$ if $\delta_{z_{\rm o}}(v)\geq w_{\rm o}(v)$ holds for
every node $v\in V$. We say that a pair $(z_{\rm o},z_{\rm i})$ of non-
negative vectors defined on $\stackrel{{\scriptstyle\leftrightarrow}}{{A}}$ is
a cover of $(w_{\rm o},w_{\rm i})$ if $z_{\rm o}$ is an out-cover of $w_{\rm
o}$ and $z_{\rm i}$ is an in-cover of $w_{\rm i}$. A cover $(z_{\rm o},z_{\rm
i})$ of $(w_{\rm o},w_{\rm i})$ is a circular cover of $(w_{\rm o},w_{\rm i})$
if $z=z_{\rm o}+z_{\rm i}$ is a circulation in
$\stackrel{{\scriptstyle\leftrightarrow}}{{D}}$. Let $c:=\chi_{A}$ denote the
characteristic function of $A$ defined on the arc-set
$\stackrel{{\scriptstyle\leftrightarrow}}{{A}}$, that is,

$c(e):=\begin{cases}1&\ \ \hbox{if}\ \ \ e\in A\cr 0&\ \ \hbox{if}\ \ \
e\in\stackrel{{\scriptstyle\leftarrow}}{{A}}.\end{cases}$ (3)

In what follows, the cost-function $c$ always refers to the function defined
in (3). The $c$-cost of a circular cover $(z_{\rm o},z_{\rm i})$ of $(w_{\rm
o},w_{\rm i})$ is $cz_{\rm o}+cz_{\rm i}$.

The main result of the paper (beside the algorithmic aspects) is the following
min-max formula. Recall that for a vector $w$ on set $V$,
$\widetilde{w}(X):=\sum\ [w(s):s\in X]$.

######  Theorem 4.1.

Let $w_{\rm o}:V\rightarrow{\bf R}_{+}$ and $w_{\rm i}:V\rightarrow{\bf
R}_{+}$ be weight-functions on the node-set of digraph $D=(V,A)$. Then

$\begin{cases}\hbox{ $\max\\{\widetilde{w}_{\rm o}(Y_{\rm
o})+\widetilde{w}_{\rm i}(Y_{\rm i}):(Y_{\rm o},Y_{\rm i})$ \ a source-sink
pair$\\}$}\ \ &\cr\hbox{ $=$ }\ &\cr\hbox{ $\min\\{c(z_{\rm o}+z_{\rm i}):\
(z_{\rm o},z_{\rm i})$ \ a circular cover of $(w_{\rm o},w_{\rm i})$$\\}$.}\
\cr\end{cases}$ (4)

If $(w_{\rm o},w_{\rm i})$ is integer-valued, then the circular cover of
minimum $c$-cost may be chosen integer-valued.

###  4.2 A primal circulation problem and its dual tension problem

We associate a digraph $D^{*}=(V^{*},A^{*})$ with $D$ and investigate a
minimum cost feasible circulation problem on $D^{*}$ along with its linear
programming dual which is a maximum weight feasible tension problem. On one
hand, an optimal integer-valued tension in $D^{*}$ shall define a maximum
$(w_{\rm o},w_{\rm i})$-weight so-si pair. On the other hand, an optimal
feasible circulation in $D^{*}$ shall define a minimum $c$-cost circular cover
$(z_{\rm o},z_{\rm i})$ of $(w_{\rm o},w_{u})$.

Let $V_{\rm i}$ and $V_{\rm o}$ be disjoint copies of $V$ and let
$V^{*}:=V_{\rm o}\cup V\cup V_{\rm i}$. (For an intuition, we think on these
three sets to be drawn in three parallel horizontal lines so that $V_{\rm o}$
is the lower, $V$ is the middle, and $V_{\rm i}$ is the upper set, and their
elements are positioned in such a way that $v_{\rm o},\ v,\ v_{\rm i}$ are in
a vertical position for every $v\in V$.)

Define a digraph $D^{*}=(V^{*},A^{*})$ as follows. For every node $v\in V$,
let $v_{\rm i}v$ and $vv_{\rm o}$ be ‘vertical’ arcs of $D^{*}$ (which are
directed downward). Furthermore, for every arc
$uv\in\stackrel{{\scriptstyle\leftrightarrow}}{{A}}$, let $uv$, $uv_{\rm i}$,
and $u_{\rm o}v$ be arcs in $D^{*}$. (Therefore $D^{*}$ has $3|V|$ nodes and
$2|V|+6|A|$ arcs, and the restriction of $D^{*}$ to $V$ is just
$\stackrel{{\scriptstyle\leftrightarrow}}{{D}}$. See Figure 1.)

$u$$v$$V$$u_{\text{i}}$$v_{\text{i}}$$V_{\text{i}}$$u$$v$$V$$u_{\text{o}}$$v_{\text{o}}$$V_{\text{o}}$
Figure 1: Auxiliary digraph $D^{*}$ associated with $D$

On the arc-set of $D^{*}$, we define a lower bound function
$f^{*}:A^{*}\rightarrow{\bf R}^{+}$ and a cost-function
$c^{*}:A^{*}\rightarrow\\{0,1\\}$, as follows.

$f^{*}(e):=\begin{cases}w_{\rm i}(v)&\ \ \hbox{if}\ \ \ e=v_{\rm i}v\ \ (v\in
V)\cr w_{\rm o}(v)&\ \ \hbox{if}\ \ \ e=vv_{\rm o}\ \ (v\in V)\cr 0&\ \
\hbox{otherwise,}\end{cases}$ (5)

$c^{*}(e):=\begin{cases}1&\ \ \hbox{if}\ \ \ e=uv\ \ (uv\in A)\cr 1&\ \
\hbox{if}\ \ \ e=uv_{\rm i}\ \ (uv\in A)\cr 1&\ \ \hbox{if}\ \ \ e=u_{\rm o}v\
\ (uv\in A)\cr 0&\ \ \hbox{otherwise.}\end{cases}$ (6)

Let $Q^{*}$ denote the $(0,\pm 1)$-valued incidence matrix of $D^{*}$, in
which the columns correspond to the nodes and the rows correspond to the arcs
of $D^{*}$. An entry of the row corresponding to $e=uv$ is $+1$ in the column
of $v$ and $-1$ in the column of $u$, and 0 otherwise. Consider the following
(primal) polyhedron of feasible circulations.

$R_{\rm pr}:=\\{x^{*}:\ Q^{*}x^{*}=0,\ x^{*}\geq f^{*}\\}.$ (7)

Below we refer to the members of $R_{\rm pr}$ as feasible circulations.
Consider the primal linear program

${\rm OPT}_{\rm pr}:=\min\\{c^{*}x^{*}:Q^{*}x^{*}=0,\ x^{*}\geq f^{*}\\},$ (8)

which is a cheapest feasible circulation problem.

The dual polyhedron belonging to (8) and the dual linear program are the
following

$R_{\rm du}:=\\{(\pi^{*},y^{*}):\pi^{*}Q^{*}+y^{*}=c^{*},\ y^{*}\geq 0\\},$
(9)

${\rm OPT}_{\rm du}:=\max\\{f^{*}y^{*}:\pi^{*}Q^{*}+y^{*}=c^{*},\ y^{*}\geq
0\\},$ (10)

where $\pi^{*}=(\pi_{\rm o},\pi,\pi_{\rm i})$ is a function defined on
$V^{*}$, while $y^{*}$ is defined on $A^{*}$.

The duality theorem of linear programming states that OPT${}_{\rm pr}=$ OPTdu.
As the describing incidence matrix $Q^{*}$ is known to be totally unimodular
(TU) and $c^{*}$ is $(0,1)$-valued, the dual optimum is attained at an
integral vector. If $f^{*}$ is integer-valued (that is, if $(w_{\rm o},w_{\rm
i})$ is integer-valued), then the primal optimum is also attained at an
integral vector.

The constraint equality $\pi^{*}Q^{*}+y^{*}=c^{*}$ in the dual program
requires for every arc $a\in A^{*}$ that

$\Delta_{\pi^{*}}(a)+y^{*}(a)=c^{*}(a).$

In particular, it follows that

$y^{*}(a)=-\Delta_{\pi^{*}}(a)\ \hbox{holds for each vertical arc $a\in A^{*}$
of $D^{*}$. }\ $ (11)

Since $y^{*}$ is non-negative, $\pi^{*}$ is a $c^{*}$-feasible potential, that
is, $\Delta_{\pi^{*}}(a)\leq c^{*}(a)$ holds for each arc $a\in A^{*}$.
Therefore, if we associate a vector $y^{*}:=c^{*}-\Delta_{\pi^{*}}$ (on
$A^{*}$) with a $c^{*}$-feasible potential $\pi^{*}$, the vector
$(\pi^{*},y^{*})$ obtained in this way is in the dual polyhedron (9). (This
means that the polyhedron of $c^{*}$-feasible potentials is the projection of
$R_{\rm du}$.) By applying (11), we get that the weight $M(\pi^{*})$ of
$\pi^{*}$ in the dual linear program is

$M(\pi^{*}):=f^{*}y^{*}=\sum\ [-\Delta_{\pi^{*}}(a)f^{*}(a):\ a\in A^{*}\
\hbox{a vertical arc}].$ (12)

###  4.3 From feasible potentials in $D^{*}$ to so-si pairs in $D$

Consider an integer-valued $c^{*}$-feasible potential $\pi^{*}=(\pi_{\rm
o},\pi,\pi_{\rm i})$ along with the vector $y^{*}$ for which
$(\pi^{*},y^{*})\in R_{\rm du}$. We show how to associate a so-si pair
$(Y_{\rm o},Y_{\rm i})$ with $\pi^{*}$ for which

$\widetilde{w}_{\rm o}(Y_{\rm o})+\widetilde{w}_{\rm i}(Y_{\rm i})=M(\pi^{*})\
\ (=f^{*}y^{*})$ (13)

holds.

######  Claim 4.2.

The potential $\pi$ (on $V$) occurring in $\pi^{*}=(\pi_{\rm o},\pi,\pi_{\rm
i})$ is small-dropping on the arc-set of $D$, that is,
$\Delta_{\pi}(e)\in\\{0,1\\}$ holds for each arc $e\in A$.

Proof. What we prove is that $0\leq\Delta_{\pi}(e)\leq 1$. On one hand,
clearly

$\Delta_{\pi}(e)=\Delta_{\pi^{*}}(e)\leq c^{*}(e)=1.$

On the other hand,
$\Delta_{\pi}(e)+\Delta_{\pi}(\stackrel{{\scriptstyle\leftarrow}}{{e}})=0$
holds for the arc
$\stackrel{{\scriptstyle\leftarrow}}{{e}}\in\stackrel{{\scriptstyle\leftarrow}}{{A}}$
arising by reversing $e$, and hence

$-\Delta_{\pi}(e)=\Delta_{\pi}(\stackrel{{\scriptstyle\leftarrow}}{{e}})=\Delta_{\pi^{*}}(\stackrel{{\scriptstyle\leftarrow}}{{e}})\leq
c^{*}(\stackrel{{\scriptstyle\leftarrow}}{{e}})=0,$

that is, $\Delta_{\pi}(e)\geq 0$.

######  Claim 4.3.

For every node $v\in V$, the sum $y^{*}(v_{\rm i}v)+y^{*}(vv_{\rm o})$ is
either $0$ or $1$. In particular, the non-negativity of $y^{*}$ implies that
$y^{*}(v_{\rm i}v)\in\\{0,1\\}$ and $y^{*}(vv_{\rm o})\in\\{0,1\\}.$

Proof. Assume first that there is an arc $vu\in A$ leaving $v$. By (11) we
have

$y^{*}(v_{\rm i}v)+y^{*}(vv_{\rm o})=[\pi^{*}(v_{\rm
i})-\pi^{*}(v)]+[\pi^{*}(v)-\pi^{*}(v_{\rm o})]=\pi^{*}(v_{\rm
i})-\pi^{*}(v_{\rm o})=$ $[\pi^{*}(v_{\rm
i})-\pi^{*}(u)]+[\pi^{*}(u)-\pi^{*}(v_{\rm o})]\leq c^{*}(uv_{\rm
i})+c^{*}(v_{\rm o}u)=0+1=1.$

If no arc of $D$ leaves $v$, then there is an arc $uv\in A$ entering $v$, for
which the proof runs analogously:

$y^{*}(v_{\rm i}v)+y^{*}(vv_{\rm o})=[\pi^{*}(v_{\rm
i})-\pi^{*}(v)]+[\pi^{*}(v)-\pi^{*}(v_{\rm o})]=\pi^{*}(v_{\rm
i})-\pi^{*}(v_{\rm o})=$ $[\pi^{*}(v_{\rm
i})-\pi^{*}(u)]+[\pi^{*}(u)-\pi^{*}(v_{\rm o})]\leq c^{*}(uv_{\rm
i})+c^{*}(v_{\rm o}u)=1+0=1.$

Define subsets $Y_{\rm o}$ and $Y_{\text{i}}$ of $V$, as follows.

$\begin{cases}Y_{\rm o}:=\\{v\in V:y^{*}(vv_{\rm o})=1\\},\cr Y_{\rm
i}:=\\{v\in V:y^{*}(v_{\rm i}v)=1\\}.\end{cases}$ (14)

######  Lemma 4.4.

The pair $(Y_{\rm o},Y_{\rm i})$ of subsets defined in (14) forms a source-
sink pair for which (13) holds.

Proof. Observe first that $Y_{\rm o}\cap Y_{\rm i}=\emptyset$ since if there
were a node $v\in Y_{\rm o}\cap Y_{\rm i}$, then $y^{*}(v_{\rm
i}v)=1=y^{*}(vv_{\rm o})$, contradicting Claim 4.3. Furthermore, we have

$\widetilde{w}_{\rm o}(Y_{\rm o})=\sum\ [w_{\rm o}(v)y^{*}(vv_{\rm o}):v\in
V]=\sum\ [f^{*}(vv_{\rm o})y^{*}(vv_{\rm o}):v\in V],$

and

$\widetilde{w}_{\rm i}(Y_{\rm i})=\sum\ [w_{\rm i}(v)y^{*}(v_{\rm i}v):v\in
V]=\sum\ [f^{*}(v_{\rm i}v)y^{*}(v_{\rm i}v):v\in V],$

from which (13) follows immediately.

By Claim 4.2, $\pi$ is small-dropping on the arc-set of $D$. Next, we show
that $Y_{\rm o}$ is a source set in the dicut-equivalent reorientation
$D^{\prime}$ of $D$ defined by $\pi$ so that we reverse those arcs $uv$ of $A$
for which $\Delta_{\pi}(uv)=1$. Consider an arbitrary node $v\in Y_{\rm o}$.
By Theorem 3.3, it is enough to show for every arc $vt\in A$ leaving $v$ is
that $\pi^{*}(t)-\pi^{*}(v)=0$, and for every arc $sv\in A$ entering $v$ that
$\pi^{*}(v)-\pi^{*}(s)=1$.

By (11) it follows for $v_{\rm o}\in V_{\rm o}$ that $\pi^{*}(v_{\rm
o})-\pi^{*}(v)=-y^{*}(v_{\rm o}v)=-1$, and hence we have for each arc $vt\in
A$ the following.

$\pi^{*}(t)-\pi^{*}(v)=[\pi^{*}(t)-\pi^{*}(v_{\rm o})]+[\pi^{*}(v_{\rm
o})-\pi^{*}(v)]=$ $[\pi^{*}(t)-\pi^{*}(v_{\rm o})]-1\leq c^{*}(v_{\rm
o}t)-1=0,$

that is, $\pi^{*}(t)-\pi^{*}(v)\leq 0$. On the other hand, as
$tv\in\stackrel{{\scriptstyle\leftarrow}}{{A}}$, we have
$\pi^{*}(v)-\pi^{*}(t)\leq c^{*}(tv)=0$, from which
$0\leq\pi^{*}(t)-\pi^{*}(v)\leq 0$, that is, $\pi^{*}(t)-\pi^{*}(v)=0$
follows.

Similarly, for an arc $sv\in A$ we get:

$\pi^{*}(s)-\pi^{*}(v)=[\pi^{*}(s)-\pi^{*}(v_{\rm o})]+[\pi^{*}(v_{\rm
o})-\pi^{*}(v)]=$ $[\pi^{*}(s)-\pi^{*}(v_{\rm o})]-1\leq c^{*}(v_{\rm
o}s)-1=-1,$

from which $\pi^{*}(v)-\pi^{*}(s)\geq 1$. On the other hand
$\pi^{*}(v)-\pi^{*}(s)\leq c^{*}(cs)=1$, and hence
$1\leq\pi^{*}(v)-\pi^{*}(s)\leq 1$, that is, $\pi^{*}(s)-\pi^{*}(v)=1$
follows.

An analogous argument shows that $Y_{\rm i}$ is a sink set in $D^{\prime}$,
completing the proof of the lemma.

It follows from Lemma 4.4 that:

$\displaystyle\max\\{\widetilde{w}_{\rm o}(Y_{\rm o})+\widetilde{w}_{\rm
i}(Y_{\rm i}):(Y_{0},Y_{\rm i})\ \hbox{is a so-si pair}\\}$
$\displaystyle\geq$ (15) $\displaystyle\max\\{M(\pi^{*}):\ \pi^{*}\ \ \hbox{is
a $c^{*}$-feasible potential}\\}\ $ $\displaystyle=$ $\displaystyle{\rm
OPT}_{\rm du}.$ (16)

###  4.4 From feasible circulations in $D^{*}$ to circular covers of $(w_{\rm
o},w_{\rm i})$

Consider an optimal solution $z^{*}$ of (8), which may be assumed to be
integer-valued when $(w_{\rm o},w_{\rm i})$ is integer-valued. Next, we
associate a circular cover $(z_{\rm o},z_{\rm i})$ of $(w_{\rm o},w_{\rm i})$
with $z^{*}$ in such a way that $c(z_{\rm o}+z_{\rm i})=c^{*}z^{*}$ (where
$c=\chi_{A}$ is defined in (3)). Here both $z_{\rm o}$ and $z_{\rm i}$ are
non-negative vectors on the arc-set
$\stackrel{{\scriptstyle\leftrightarrow}}{{A}}$, and their sum $z_{\rm
o}+z_{\rm i}$ is a circulation in
$\stackrel{{\scriptstyle\leftrightarrow}}{{D}}$.

We may assume that $z^{*}(uv)=0$ for every arc $uv\in A$ since if
$\alpha=z^{*}(uv)$ were positive, then by decreasing $z^{*}(uv)$ to $0$ and
increasing both $z^{*}(uv_{\rm i})$ and $z^{*}(v_{\rm i}v)$ by $\alpha$, we
obtain a new circulation which is also $f^{*}$-feasible and its $c^{*}$-cost
is unchanged.

Define functions $z_{\rm
i}:\stackrel{{\scriptstyle\leftrightarrow}}{{A}}\rightarrow{\bf R_{+}}$ and
$z_{\rm o}:\stackrel{{\scriptstyle\leftrightarrow}}{{A}}\rightarrow{\bf
R_{+}}$ as follows.

$z_{\rm o}(uv):=z^{*}(u_{\rm o}v)\ \hbox{and}\ \ z_{\rm i}(uv):=z^{*}(uv_{\rm
i}).$ (17)

Note that this $(z_{\rm o},z_{\rm i})$ is integer-valued when $(w_{\rm
o},w_{\rm i})$ is integer-valued. Observe that the pair $(z_{\rm o},z_{\rm
i})$ may be viewed as a vector arising from $z^{*}$ by deleting the arcs in
$A$ and contracting the arcs $v_{\rm o}v$ and $v_{\rm i}v$ for every $v\in V$.
Hence the sum $z:=z_{\rm o}+z_{\rm i}$ is a circulation in
$\stackrel{{\scriptstyle\leftrightarrow}}{{D}}$ for which $cz=c^{*}z^{*}$.
Moreover, we have for every node $u\in V$ the following.

$\begin{cases}\delta_{z_{\rm o}}(u)=\delta_{z^{*}}(u_{\rm o})=z^{*}(uu_{\rm
o})\geq f^{*}(uu_{\rm o})=w_{\rm o}(u)\cr\varrho_{z_{\rm
i}}(u)=\varrho_{z^{*}}(u_{\rm i})=z^{*}(u_{\rm i}u)\geq f^{*}(u_{\rm
i}u)=w_{\rm i}(u),\end{cases}$ (18)

from which it follows that $(z_{\rm o},z_{\rm i})$ is indeed a circular cover
of $(w_{\rm o},w_{\rm i})$.

This implies that:

$\displaystyle\min\\{c(x_{\rm o}+x_{\rm i}):(x_{\rm o},x_{\rm i})\ \hbox{a
circular cover of}\ (w_{\rm o},w_{\rm i})\\}\leq$ (19) $\displaystyle c(z_{\rm
o}+z_{\rm i})\ =\ c^{*}z^{*}\ =\ {\rm OPT}_{\rm pr}.$ (20)

##  5 The proof of Theorem 4.1

###  5.1 Proving $\max\leq\min$

######  Claim 5.1.

Let $D^{\prime}=(V,A^{\prime})$ be a dicut-equivalent reorientation of $D$ and
let $c^{\prime}:=\chi_{A^{\prime}}$ denote the characteristic function of
$A^{\prime}$ on $\stackrel{{\scriptstyle\leftrightarrow}}{{A}}$. Then
$cz=c^{\prime}z$ holds for every circulation $z\geq 0$ (defined on digraph
$\stackrel{{\scriptstyle\leftrightarrow}}{{D}}$).

Proof. Recall the notation $\widetilde{c}$. Since a non-negative circulation
can be expressed as the non-negative linear combination of one-way circuits it
suffices to show that $\widetilde{c}(K)=\widetilde{c}^{\prime}(K)$ holds for
every one-way circuit $K$ of $\stackrel{{\scriptstyle\leftrightarrow}}{{D}}$.
But this will follow once we prove it for the case when $D^{\prime}$ arises
from $D$ by reversing a single dicut.

Let this dicut be the set of arcs of $D$ entering a subset $Z\subset V$ of
nodes with no leaving arcs of $D$. In this case $c^{\prime}$ arises from $c$
in such a way that the $c$-cost of $A$-arcs entering $Z$ is changed from $1$
to $0$ while the $c$-cost of $\stackrel{{\scriptstyle\leftarrow}}{{A}}$-arcs
leaving $Z$ is changed from $0$ to $1.$ But this implies, as
$\varrho_{K}(Z)=\delta_{K}(Z)$, that the cost of one-way circuit $K$ does not
change, that is, $\widetilde{c}(K)=\widetilde{c}^{\prime}(K)$.

######  Remark 5.2.

_A more concise proof of Claim 5.1, where the non-negativity of $z$ is not
used, is as follows. By Claim 3.1, there is a potential $\pi\in
V\rightarrow{\bf Z}$ (which is small-dropping on $A$) for which $A^{\prime}$
arises from $A$ by reorienting those arcs $e\in A$ for which
$\Delta_{\pi}(e)=1$. Now $c^{\prime}=c-\Delta_{\pi}$ and $z\Delta_{\pi}=0$
since the scalar product of a circulation and a tension is always zero.
Therefore $c^{\prime}z=cz$ follows indeed._ $\bullet$

The requested inequality $\max\leq\min$ immediately follows from the following
claim.

######  Claim 5.3.

Let $(Y_{\rm o},Y_{\rm i})$ be a so-si pair in $D$, and let $(z_{\rm o},z_{\rm
i})$ be a circular cover of $(w_{\rm o},w_{\rm i})$. Then
$cz\geq\widetilde{w}_{\rm o}(Y_{\rm o})+\widetilde{w}_{\rm i}(Y_{\rm i})$
holds for the circulation $z=z_{\rm o}+z_{\rm i}$.

Proof. Consider the dicut-equivalent reorientation $D^{\prime}$ of $D$ for
which the elements of $Y_{\rm o}$ are source nodes and the elements of $Y_{\rm
i}$ are sink nodes. For a vector
$x:\stackrel{{\scriptstyle\leftrightarrow}}{{A}}\rightarrow{\bf Z}$ and for a
subset $Z\subset V$, let $\delta^{\prime}_{x}(Z):=\sum\ [x(e):e\in
A^{\prime},\ e$ leaves $Z]$ and $\varrho^{\prime}_{x}(Z):=\sum\ [x(e):e\in
A^{\prime},\ e$ enters $Z$$]$. By Claim 5.1, $cz=c^{\prime}z\
(=c^{\prime}z_{\rm o}+c^{\prime}z_{\rm i})$. But we have $c^{\prime}z_{\rm
o}\geq\delta^{\prime}_{z_{\rm o}}(Y_{\rm o})\geq\widetilde{w}_{\rm o}(Y_{\rm
o})$ and $c^{\prime}z_{\rm i}\geq\varrho^{\prime}_{z_{\rm i}}(Y_{\rm
i})\geq\widetilde{w}_{\rm i}(Y_{\rm i})$ from which $cz\geq\widetilde{w}_{\rm
o}(Y_{\rm o})+\widetilde{w}_{\rm i}(Y_{\rm i})$ follows.

###  5.2 Proving $\max\geq\min$

By combining (20) with inequality (16), we get the following.

$\begin{cases}\hbox{$\max\\{\widetilde{w}_{\rm o}(Y_{\rm
o})+\widetilde{w}_{\rm i}(Y_{\rm i}):(Y_{\rm o},Y_{\rm i})$ \ a so-si
pair$\\}\ \geq$}\ &\cr{\rm OPT}_{\rm du}\ =\ {\rm OPT}_{\rm pr}\
\geq&\cr\hbox{$\min\\{c(z_{\rm o}+z_{\rm i}):(z_{\rm o},z_{\rm i})$ a circular
cover of $(w_{\rm o},w_{\rm i})\\}$, }\ \end{cases}$ (21)

and this is exactly the non-trivial inequality $\max\geq\min$ of Theorem 4.1.

Finally, observe that if $(w_{\rm o},w_{\rm i})$ is integer-valued, then
$f^{*}$ in the primal linear program (8) is also integer-valued, and hence the
optimal circulation can be chosen integer-valued. In this case, the pair
$(z_{\rm o},z_{\rm i})$ associated with $z^{*}$ in (17) is an integer-valued
circular cover of $(w_{\rm o},w_{\rm i})$, and hence the proof of Theorem 4.1
is complete.

######  Corollary 5.4.

Let $z^{*}$ be an optimal solution to the primal linear program (8), and let
$(z_{\rm o},z_{\rm i})$ be the circular cover of $(w_{\rm o},w_{\rm i})$
associated with $z^{*}$ in (17), which is integer-valued when $(w_{\rm
o},w_{\rm i})$ is integer-valued. Let $(\pi^{*},y^{*})$ be an optimal integral
solution to the dual linear program (10), and let $(Y_{0},Y_{\rm i})$ be the
so-si pair associated with $\pi^{*}$ in (14). Then $c(z_{\rm o}+z_{\rm
i})=\widetilde{w}_{\rm o}(Y_{0})+\widetilde{w}_{\rm i}(Y_{\rm i})$. Moreover,
$(z_{\rm o},z_{\rm i})$ is a minimum $c$-cost circular cover of $(w_{\rm
o},w_{\rm i})$, and $(Y_{0},Y_{\rm i})$ is a maximum $(w_{\rm o},w_{\rm
i})$-weight so-si pair.

###  5.3 Algorithmic aspects

In the proof of Theorem 4.1, we introduced a network circulation problem on a
digraph $D^{*}=(V^{*},A^{*})$ along with its dual tension problem (see
Formulas (8) and (10)) where values ${\rm OPT}_{\rm pr}={\rm OPT}_{\rm du}$
give the optimal value for the double-weighted source-sink pair problem (2).
These circulation and tension problems are special in the sense that the
(primal) cost-function $c^{*}$ on $A^{*}$ is $(0,1)$-valued. It is a standard
reduction to reformulate such a circulation problem as a minimum cost network
flow problem in which the cost-function is $(0,1)$-valued (see e.g. Section
3.4.2. in [10] on the equivalence of circulations and flows). The min-cost
flow algorithm of Ford and Fulkerson [9] in this case is strongly polynomial,
provided that a strongly polynomial subroutine is used for the intermediate
maximum flow computations (for example, the classic shortest augmenting path
type algorithms of Dinitz or Edmonds and Karp or the push-relabel algorithm of
Goldberg and Tarjan).

Therefore, an optimal solution to the primal and to the dual linear programs
(8) and (10) can be computed in strongly polynomial time, where the dual
optimal vector is integer-valued and the primal optimal vector is integer-
valued when $(w_{\rm o},w_{\rm i})$ is integer-valued. By Corollary 5.4, a
maximum $(w_{\rm o},w_{\rm i})$-weight so-si pair occurring in Theorem 4.1 as
well as a minimum $c$-cost circular cover of $(w_{\rm o},w_{\rm i})$ can be
computed in strongly polynomial time.

###  5.4 Consequences

Theorem 5.1 in [7] provided a min-max formula for the maximum $w$-weight of a
sink-stable set of a digraph $D=(V,A)$ for an integer-valued weight-function
$w$. Here we show how this formula follows from Theorem 4.1.

We say that a family (with the agreement that such a family is allowed to
contain repeated copies of a given member) of one-way circuits of digraph
$\stackrel{{\scriptstyle\leftrightarrow}}{{D}}$ covers $w$ if every node $u\in
V$ belongs to at least $w(u)$ circuits. The $A$-value of a one-way circuit $K$
of digraph $\stackrel{{\scriptstyle\leftrightarrow}}{{D}}$ is $|K\cap A|$. In
particular, $\\{e,\stackrel{{\scriptstyle\leftarrow}}{{e}}\\}$ is a two-
element one-way circuit of $\stackrel{{\scriptstyle\leftrightarrow}}{{D}}$ for
every arc $e\in A$, whose $A$-value is $1$, thus a cover always exists for
every weighting $w$ if $D$ is weakly connected and has at least two nodes.
With this terminology, Theorem 5.1 in [7] is equivalent to the following.222A
slightly different notion was used for a cover in [7]. Here we define a cover
as a family of one-way circuits of
$\stackrel{{\scriptstyle\leftrightarrow}}{{D}}$, whereas a cover in [7]
consisted of circles and arcs of $D$.

######  Theorem 5.5.

Let $w$ be a non-negative, integer-valued weight-function on the arc-set of a
digraph $D=(V,A)$. Then the maximum $w$-weight of a sink-stable set of $D$ is
equal to the minimum sum of $A$-values of a family of one-way circuits of
digraph $\stackrel{{\scriptstyle\leftrightarrow}}{{D}}$ that cover $w$.

Proof. Let $w_{\rm o}:\equiv 0$ and $w_{\rm i}:=w$. For a so-si pair $(Y_{\rm
o},Y_{\rm i})$, the set $Y_{\rm i}$ is a sink-stable set for which
$\widetilde{w}_{\rm o}(Y_{\rm o})+\widetilde{w}_{\rm i}(Y_{\rm
i})=\widetilde{w}(Y_{\rm i})$. For a sink-stable set $Y$, pair $(\emptyset,Y)$
is a so-si pair for which $\widetilde{w}_{\rm o}(\emptyset)+\widetilde{w}_{\rm
i}(Y)=\widetilde{w}(Y)$. Thus the maximum $(w_{\rm o},w_{\rm i})$-weight of a
so-si pair is equal to the maximum $w$-weight of a sink set. By Theorem 4.1,
this latter maximum equals the minimum of $c(z_{\rm o}+z_{\rm i})$ over (non-
negative, integer-valued) circular covers $(z_{\rm o},z_{\rm i})$ of $(0,w)$.
We show that this minimum equals the minimum sum of $A$-values of a family of
one-way circuits of digraph $\stackrel{{\scriptstyle\leftrightarrow}}{{D}}$
that cover $w$.

First, let $(z_{\rm o},z_{\rm i})$ be a minimum cost circular cover of
$(0,w)$. Then $z=z_{\rm o}+z_{\rm i}$ is a circulation in
$\stackrel{{\scriptstyle\leftrightarrow}}{{D}}$ such that $(0,z)$ is a
circular cover of $(0,w)$ and $c(z_{\rm o}+z_{\rm i})=cz$. But $z$ can be
obtained as a non-negative integral combination of one-way circuits of
$\stackrel{{\scriptstyle\leftrightarrow}}{{D}}$, and these coefficients define
a family of one-way circuits. The property that $(0,z)$ covers $(0,w)$ means
that every node $u$ belongs to at least $w(u)$ one-way circuits in the family.
That is, this family of circuits covers $w$ and the sum of $A$-values of the
circuits is $cz$.

Second, if a family of one-way circuits of digraph
$\stackrel{{\scriptstyle\leftrightarrow}}{{D}}$ covers $w$, then the sum of
the incidence vectors of the circuits in the family gives a circulation $z$
such that $(0,z)$ is a circular cover of $(0,w)$, and cost $c(0+z)$ equals the
sum of $A$-values of the circuits in the family.

######  Remark 5.6.

_Theorem 5.1 of [7] (and hence the present Theorem 5.5) does not imply
directly the min-max theorem of Abeledo and Atkinson (Theorem 8 of [3]) on the
maximum cardinality of a Clar-set of bounded faces of $G=(S,T;E)$. Instead, a
sharpening (Theorem 5.4 of [7]) of a special case of Theorem 5.1 of [7] (when
there exists a so-called ”thin” subset of edges) was derived in [7] from which
the Abeledo-Atkinson theorem followed immediately. Therefore the present
Theorem 5.5 can imply only a weaker version of the Abeledo-Atkinson theorem
stating that, in a perfectly matchable plane bipartite graph, the Clar number
is equal to the minimum total value of (minimal) cuts intersecting all bounded
faces, where the value of a cut $[Z,\overline{Z}]$ is the in-degree of
$Z\subset S\cup Z$ in the digraph
${\stackrel{{\scriptstyle\rightarrow}}{{G}}_{M}}$ arising from $G$ by
orienting the elements of an arbitrary perfect matching $M$ toward $S$ while
the other edges of $G$ toward $T$. The content of the original theorem of
Abeledo-Atkinson is that the minimum can actually be attained on a family of
such cuts $[Z,\overline{Z}]$ for which no element of
$\stackrel{{\scriptstyle\rightarrow}}{{M}}$ leaves $Z$ and every arc in
${\stackrel{{\scriptstyle\rightarrow}}{{G}}}_{M}$ entering $Z$ belongs to
$\stackrel{{\scriptstyle\rightarrow}}{{M}}$. Finally, we note (without going
into details) that it is not difficult to obtain this sharpened version form
the weaker one._ $\bullet$

Next, we show a min-max formula concerning maximum weight resonant sets.
Recall the definition of a circular cover $(z_{\rm o},z_{\rm i})$ of $(w_{\rm
o},w_{\rm i})$ introduced in Section 4.1 and the cost-function $c$ on arc-set
$\stackrel{{\scriptstyle\leftrightarrow}}{{A}}$ given in (3). In the special
case when $w:=w_{\rm o}=w_{\rm i}$, Theorem 4.1 is as follows.

######  Theorem 5.7.

Let $w:V\rightarrow{\bf R}_{+}$ be a non-negative weight-function on the node-
set of digraph $D=(V,A)$. Then

$\begin{cases}\hbox{ $\max\\{\widetilde{w}(Y):Y\subseteq V$ \ a resonant
set$\\}$}\ &\cr\hbox{ $=$ }\ &\cr\hbox{ $\min\\{c(z_{\rm o}+z_{\rm i}):\
(z_{\rm o},z_{\rm i})$ a circular cover of $(w,w)\\}$.}\ \cr\end{cases}$ (22)

When $w$ is integer-valued, a circular cover of minimum $c$-cost can be chosen
integer-valued.

We say for a non-negative integer vector $z_{\rm i}$ on arc-set
$\stackrel{{\scriptstyle\leftrightarrow}}{{A}}$ that it is an in-cover of a
subset $U\subseteq V$ of nodes if $\varrho_{z_{\rm i}}(v)\geq 1$ holds for
each node $v\in U$. A non-negative integer vector $z_{\rm o}$ defined on arc-
set $\stackrel{{\scriptstyle\leftrightarrow}}{{A}}$ is an out-cover of $U$ if
$\delta_{z_{\rm o}}(v)\geq 1$ holds for every node $v\in U$. Let $U_{\rm
o}\subseteq V$ and $U_{\rm i}\subseteq V$ be two disjoint subsets. We say that
the pair $(z_{\rm o},z_{\rm i})$ of vectors is a cover of the pair $(U_{\rm
o},U_{\rm i})$ of sets if $z_{\rm o}$ is an out-cover of $U_{\rm o}$ and
$z_{\rm i}$ is an in-cover of $U_{\rm i}$.

By applying Theorem 4.1 to weight-functions $w_{\rm o}:=\chi_{U_{\rm o}}$ and
$w_{\rm i}:=\chi_{U_{\rm i}}$, we obtain the following.

######  Theorem 5.8.

In a digraph $D=(V,A)$, let $U_{\rm o}\subseteq V$ and $U_{\rm i}\subseteq V$
be two disjoint subsets of nodes. Then

$\begin{cases}\hbox{ $\max\\{|Y_{\rm o}|+|Y_{\rm i}|:(Y_{\rm o},Y_{\rm i})$ \
a so-si pair, \ $Y_{\rm o}\subseteq U_{\rm o},\ Y_{\rm i}\subseteq U_{\rm
i}\\}$}\ \ &\cr\hbox{ $=$ }\ &\cr\hbox{ $\min\\{c(z_{\rm o}+z_{\rm i}):\
(z_{\rm o},z_{\rm i})$ \ a circular cover of $(U_{\rm o},U_{\rm i})$$\\}$.}\
\cr\end{cases}$ (23)

In the special case when $U:=U_{\rm o}=U_{\rm i}$, this reduces to the the
following.

######  Corollary 5.9.

In a digraph $D=(V,A)$, the maximum cardinality of a resonant subset of a
given subset $U\subseteq V$ is equal to the minimum $c$-cost of a circulation
$z$ (in $\stackrel{{\scriptstyle\leftrightarrow}}{{D}}$) $(*)$ which arises as
the sum of non-negative integer-valued vectors $z_{\rm o}$ and $z_{\rm i}$ for
which $\varrho_{z_{\rm o}}(u)\geq 1$ and $\delta_{z_{\rm i}}(u)\geq 1$ hold
for each node $u\in U$ (that is, $(z_{\rm o},z_{\rm i})$ is a circular pair
covering the pair $(U,U)$). In particular, $U$ is a resonant set if and only
if $cz\geq|U|$ holds for every circulation $z$ (in
$\stackrel{{\scriptstyle\leftrightarrow}}{{D}}$) satisfying $(*)$.

$a_{1}$$a_{2}$$a_{3}$$x$$b_{1}$$b_{2}$$b_{3}$ Figure 2: A digraph $D=(V,A)$
where $U=\\{a_{1},b_{1},x\\}$ is not resonant

As an example, consider the digraph in Figure 2. It is not difficult to check
that the four-element set $\\{a_{2},a_{3},b_{1},b_{2}\\}$ is resonant, on the
other hand we claim that set $U:=\\{a_{1},b_{1},x\\}$ is not. To show this,
define $z_{\rm o}$ and $z_{\rm i}$ on the arc-set
$\stackrel{{\scriptstyle\leftrightarrow}}{{A}}$ as follows. Let $z_{\rm o}$ be
$1$ on the arcs $a_{1}a_{2},a_{2}a_{3},b_{1}x,xb_{3}$ while $0$ otherwise, and
let $z_{\rm i}$ be $1$ on the arcs $b_{3}b_{2},b_{2}b_{1},a_{3}x,xa_{1}$ while
$0$ otherwise. Then $z_{\rm i}$ is an in-cover of $U$ and $z_{\rm o}$ is an
out-cover of $U$ for which $z:=z_{\rm i}+z_{\rm o}$ is a $(0,1)$-valued
circulation. Furthermore $z_{\rm o}$ is $1$ only on one element of $A$
(namely, on $b_{1}x$) and $z_{\rm i}$ is $1$ only on one element of $A$
(namely, on $xa_{1}$), that is, $cz_{\rm o}=1$ and $cz_{\rm i}=1$, and hence
$cz=c(z_{\rm o}+z_{\rm i})=2$, implying that the 3-element node-set
$\\{a_{1},b_{1},x\\}$ cannot indeed be a resonant set of $D$.

######  Remark 5.10.

_There is a somewhat surprising discrepancy between the characterization of
Clar-sets and resonant sets. Theorem 4.1 in[7] states roughly that a stable
set $U\subseteq V$ is sink-stable if and only if a certain inequality holds
for every circuit of digraph $D$. This result was extended by Theorem 3.3 in
the present work where the equivalence of Parts (A) and (C) indicated that a
pair $(Y_{\rm o},Y_{\rm i})$ of node-sets is a source-sink pair if and only if
a certain inequality holds for every circuit of $D$. On the other hand, the
characterization of resonant sets in the second part of Corollary 5.9 requires
an inequality not only for circuits but for certain integer-valued
circulations, as well. The question naturally arises whether this
characterization can be simplified in such a way that a certain inequality
should be required only for circuits and not for more general circulations.
The example in Figure 2 demonstrates that such a simplification is not
possible. Here $D$ has exactly two circuits, and $U:=\\{a_{1},b_{1},x\\}$ is a
set which is clearly resonant when restricted to any of these two circuits,
but $U$ is not a resonant set of $D$ as we pointed out above. Therefore no
characterization of resonant sets may exist that requires an inequality only
for single circuits._ $\bullet$

Finally we remark that Theorem 4.1 can be applied to manage further special
cases. For example, the one when we are interested in finding a maximum weight
resonant set including a specified subset. Or more generally, one may be
interested in finding a (maximum weight) so-si pair $(Y_{\rm i},Y_{\rm o})$
for which $U_{\rm o}^{\prime}\subseteq Y_{\rm o}\subseteq U_{\rm o}$ and
$U_{\rm i}^{\prime}\subseteq Y_{\rm i}\subseteq U_{\rm i}$. By defining
$w_{\rm o}$ ($w_{\rm i}$) to be an appropriately large number on the elements
of $U_{\rm o}^{\prime}$ ($U_{\rm i}^{\prime}$), and zero on the elements of
$V-U_{\rm o}$ ($V-U_{\rm i}$), Theorem 4.1 and the algorithmic approach
described above can be applied.

###  5.5 Conclusion

In [7], the notion of Clar-sets of a perfectly matchable plane bipartite graph
was extended to the one of sink-stable sets of a general digraph, along with a
network flow approach for developing min-max formulas and purely combinatorial
algorithms for various generalizations, including the one of finding a maximum
weight Clar-set. Fries-set is another important notion in mathematical
chemistry, but unlike the situation with Clar-sets, the literature does not
seem to include any strongly polynomial purely combinatorial algorithm for
computing the Fries number, the largest cardinality of a Fries-set. In the
present paper, we did provide such an algorithm, actually in a much more
general setting which may be considered as a common framework for Clar-sets
and for Fries-sets. Namely, we introduced the notion of a source-sink pair of
node-sets as well as a resonant node-set in a digraph, and developed a network
flow approach that gave rise to min-max formulas and to purely combinatorial
strongly polynomial algorithms for computing both a maximum double-weight
source-sink pair and a maximum weight resonant subset. The algorithm also
provides an optimal solution to the dual problem formulated in the min-max
theorem.

### Acknowledgement

We thank the anonymous reviewer for his/her careful reading of our manuscript
and for the many insightful comments and suggestions. This research was
supported by the ÚNKP-22-5 New National Excellence Program of the Ministry for
Culture and Innovation from the source of the National Research, Development
and Innovation Fund. This research has been implemented with the support
provided by the Ministry of Innovation and Technology of Hungary from the
National Research, Development and Innovation Fund, financed under the ELTE
TKP 2021-NKTA-62 funding scheme, and supported by the János Bolyai Research
Scholarship of the Hungarian Academy of Science.

## References

  * [1] H. Abeledo, personal communication, 2010
  * [2] H. Abeledo and G.W. Atkinson, Unimodularity of the Clar number problem, Linear Algebra and its Applications, 420(2-3) (2007) 441–448.
  * [3] H. Abeledo and G.W. Atkinson, A min-max theorem for plane bipartite graphs, Discrete Applied Mathematics, 158(5) (2010) 375–378.
  * [4] E.R. Bérczi-Kovács and A. Bernáth, The complexity of the Clar number problem and an exact algorithm, J. of Mathematical Chemistry, 56 (2018) 597–605.
  * [5] S. Bessy and S. Thomassé, Spanning a strong digraph by $\alpha$ circuits: A proof of Gallai’s conjecture, Combinatorica, 27(6) (2007) 659–667.
  * [6] E. Clar, The aromatic sextet, John Wiley and Sons, London, 1972.
  * [7] D. Erdős, A. Frank, K. Kun, Sink-stable sets of digraphs, SIAM J. on Discrete Mathematics, 28(4) (2014) 1651–1674.
  * [8] I. Fáry, On the straight line representation of planar graphs, Acta Scientiarum Mathematicarum, 11(4) (1948) 229–233.
  * [9] L.R. Ford and D.R. Fulkerson, Flows in Networks, Princeton Univ. Press, Princeton NJ., 1962.
  * [10] A. Frank, Connections in Combinatorial Optimization, Oxford University Press, 2011, Oxford Lecture Series in Mathematics and its Applications, 38
  * [11] K. Fries, Über bicyclische Verbindungen und ihre Vergleich mit dem Naphtalin, (3. Mitteilung), Justus Liebigs Annalen der Chemistry, 454(1) (1927) 121–324.
  * [12] T. Gallai, Maximum-Minimum Sätze über Graphen, Acta Mathematica Academiae Scientiarum Hungariae, 9(3-4) (1958) 395–434.
  * [13] J.E. Graver, E.J. Hartung, A.Y. Souid, Clar and Fries numbers for benzenoids, J. of Mathematical Chemistry, 51(8) (2013) 1981–1989.
  * [14] P. Hansen and M. Zheng, Upper bounds for the Clar number of a benzenoid hydrocarbon, J. of the Chemical Society, Faraday Transactions, 88(12) (1992) 1621–1625.
  * [15] P. Hansen and M. Zheng, The Clar number of a benzenoid hydrocarbon and linear programming, J. of Mathematical Chemistry, 15(1) (1994) 93–107.
  * [16] P. Hansen and M. Zheng, Numerical bounds for the perfect matching vectors of a polyhex, J. of Chemical Information and Computer Sciences, 34(2) (1994) 305–308.
  * [17] E.J. Hartung, Clar chains and a counter-example, J. of Mathematical Chemistry, 52(3) (2014) 990–1006.
  * [18] A.J. Hoffman and J.B. Kruskal, Jr, Integral boundary points of convex polyhedra, Linear Inequalities and Related Systems, Annals of Mathematics Study, 38 (1956) 223–346, Princeton University Press.
  * [19] H. Lei, Y-N. Yeh, H. Zhang, Anti-forcing numbers of perfect matchings in graphs, Discrete Applied Mathematics, 202 (2016) 95–105.
  * [20] M. Salami and M. B. Ahmadi, A mathematical programming model for computing the Fries number of a fullerene, Applied Mathematical Modelling, 39(18) (2015) 5473–5479.
  * [21] A. Sebő, Minmax relations for cyclically ordered digraphs, J. Combinatorial Theory, Ser. B, 97(4) (2007) 518–552.
  * [22] L. Shi, H. Wang, H. Zhang, On the maximum forcing and anti-forcing numbers of (4,6)-fullerenes, Discrete Applied Mathematics, 233 (2017) 187–194.
  * [23] L. Shi and H. Zhang, The maximum number of alternating hexagonal faces in (4, 6)-fullerenes, Advances in Mathematics (China), 51(3) (2022) 407–414.
  * [24] A. Schrijver, Theory of Linear and Integer Programming, Wiley, Chichester, 1986.
  * [25] É. Tardos, A strongly polynomial algorithm to solve combinatorial linear programs, Operations Research, 32(2) (1986) 250–256.
  * [26] W.T. Tutte, How to draw a graph, Proceedings of the London Mathematical Society, 13(3) (1963) 743–768.
  * [27] Y. Wang, Extension and Quantification of the Fries Rule and Its Connection to Aromaticity: Large-Scale Validation by Wave-Function-Based Resonance Analysis, J. of Chemical Information and Modeling, 62(21) (2022) 5136–5148.
  * [28] L. Xu, B. Hong, F. Zhang, Maximum forcing number of hexagonal systems, MATCH Communications in Mathematical and in Computer Chemistry, 70(2) (2013) 493–500.
  * [29] S. Zhai, D. Alrowaili, D. Ye, Clar structures vs Fries structure in hexagonal systems, Applied Mathematics and Computation, 329 (2018) 384–394.
  * [30] S. Zhou, H. Zhang, I. Gutman, Relations between Clar structures, Clar covers, and the sextet-rotation tree of a hexagonal system, Discrete Applied Mathematics, 156(10) (2008) 1809–1821.