36

ベルジュ双対のための非二部的Dulmage‐Mendelsohn 分解(Nonbipartite Dulmage‐Mendelsohn Decomposition
for Berge Duality)
国立情報学研究所

喜多 奈々緒Nanao Kita

National Institute of Informatics

Abstract

The Dulmage‐Mendelsohn decomposition is a classical canonical decompositionin matching theory applicable for bipartite graphs and is famous not only for its
application in the field of matrix computation, but also for providing a prototypal
structure in matroidal optimization theory. The Dulmage‐Mendelsohn decompo‐
sition is stated and proved using the two color classes of a bipartite graph, andtherefore generalizing this decomposition for nonbipartite graphs has been a difficult
task. In our study, we obtain a new canonical decomposition that is a generalizationof the Dulmage‐Mendelsohn decomposition for arbitrary graphs using a recently in‐troduced tool in matching theory, the basilica decomposition. Our result enables us
to understand all known canonical decompositions in a unified way. Furthermore,
we apply our result to derive a new theorem regarding barriers. The duality theo‐
rem for the maximum matching problem is the celebrated Berge formula, in which
dual optimizers are known as barriers. Several results regarding maximal barriers
have been derived by known canonical decompositions; however, no characterization
has been known for general graphs. In our study, we provide a characterization of
the family of maximal barriers in general graphs, in which the known results aredeveloped and unified.

1

Introduction

We establish the Dulmage‐Mendelsohn decomposition for general graphs. The Dulmage‐Mendelsohn decomposition [2−4], or the DM decomposition in short, is a classical canonicaldecomposition in matching theory [15] applicable for bipartite graphs. This decomposition
is famous for its application for combinatorial matrix theory, especially for providing anefficient solution for a system of linear equations [1, 4] and is also important in matroidal
optimization theory. Furthermore, its connection with matrices and matroids gave rise toa branch of combinatorial matrix theory known as mixed matrix theory [16].
Canonical decompositions of a graph are fundamental tools in matching theory [15].
A canonical decomposition partitions a given graph in a way uniquely determined for37
the graph and describes the structure of maximum matchings using this partition. The

classical canonical decompositions are the Gallai‐Edmonds [5, 6] and Kotzig‐Lovász de‐compositions [11−13] in addition to the DM decomposition. The DM and Kotzig‐Lovász
decompositions are applicable for bipartite graphs and factor‐connected graphs, respec‐tively. The Gallai‐Edmonds decomposition partitions an arbitrary graph into three parts:that is, the so‐called D(G), A(G) , and C(G) parts. Comparably recently, a new canon‐

ical decomposition was proposed: the basilica decomposition [7−9]. This decomposition
is applicable for arbitrary graphs and contains a generalization of the Kotzig‐Lovász de‐composition and a refinement the Gallai‐Edmonds decomposition. (The C(G) part canbe decomposed nontrivially.)
In our study, we establish an analogue of the DM decomposition for general graphs
using the basilica decomposition. Our results accordingly provide a paradigm that enables
us to handle any graph and understand the known canonical decompositions in a unified
way. In the original theory of DM decomposition, the concept of the DM components
of a bipartite graph is first defined, and then it is proved that these components forma poset with respect to a certain binary relation. This theory depends heavily on thetwo color classes of a bipartite graph and cannot be easily generalized for nonbipartite
graphs. In our generalization, we first define a generalization of the DM components
using the basilica decomposition. To capture the structure formed by these components
in nonbipartite graphs, we introduce a slightly more complex concept: posets with atransitive forbidden relation. We then prove that the generalized DM components form a
poset with a transitive forbidden relation for certain binary relations.
Furthermore, we apply our generalized DM decomposition to derive a characterizationof the family of maximal barriers in general graphs. The Berge formula is a combinatorialmin‐max theorem in which maximum matchings are the optimizers of one hand, and the

optimizers of the other hand are known as barriers [15]. That is, barriers are the dual
optimizers of the maximum matchings problem. Barriers are heavily employed as a tool

for studying matchings. However, not as much is known about barriers themselves [15].
Aside from several observations that are derived rather easily from the Berge formula,several substantial results about (inclusion‐wise) maximal barriers have been provided bycanonical decompositions.
Our result for maximal barriers proves that our generalization of the DM decompo‐
sition has a reasonable consistency with the relationship between each known canonicaldecomposition and maximal barriers. Each known canonical decomposition can be used
to state the structure of maximal barriers. The original DM decomposition provides acharacterization of the family of maximal barriers in a bipartite graph in terms of ideals
in the poset; minimum vertex covers in bipartite graphs are equivalent to maximal barri‐ers. The Gallai‐Edmonds decomposition derives a characterization of the intersection of

all maximal barriers (that is, the A(G) part) [15]; this characterization is known as theGallai‐Edmonds description. The Kotzig‐Lovász decomposition is used for characterizing

the family of maximal barriers in factor‐connected graphs [15]; this result is known as
Lovász’s canonical partition theorem [14, 15]. The basilica decomposition provides the
structure of a given maximal barrier in general graphs, which contains a common gen‐eralization of the Gallai‐Edmonds description and Lovász’s canonical partition theorem.
Hence, a generalization of the DM decomposition would be reasonable if it can character‐ize the family of maximal barriers, and our generalization attains this in a way analogical38
to the classical DM decomposition, that is, in terms of ideals in the poset with a transitive
forbidden relation.

Our results imply a new possibility in matroidal optimization theory. Submodular
function theory is a systematic field of study that captures many well‐solved problems interms of submodular functions and generalizations. In this theory, the bipartite maximum
matching problem is an important exemplary problem. According to the Hall‐Ore theo‐rem [17], which is the duality theorem for the bipartite maximum matching problem, thisproblem can be understood as a special case of the submodular function minimization.
The DM decomposition therefore has a special meaning in this theory as it describes the
structure of the family of minimizers of a submodular function. The nonbipartite max‐
imum matching problem is also an important well‐solved problem, and is even referred

to as the archetype of well‐solved problems [15, 17]. In fact, the idea of polyhedral com‐binatorics and some of its central concepts, such as the total dual integrality, have been
discovered from the nonbipartite maximum matching problem. However, the nonbipartite
maximum matching problem and its duality shown by the Berge formula are not included
in submodular function theory today and nor in any of its generalizations. Our nonbi‐
partite DM decomposition may provide a clue to a new aspect of submodular function
theory that can be brought in by capturing these concepts.

2Notation

For basic notation for sets, graphs, and algorithms, we mostly follow Schrijver [17]. In
this section, unless otherwise stated, let G be a graph. The vertex set and the edge setof G are denoted by V(G) and E(G) , respectively. We often treat a graph as the set ofits vertices.

In the remainder of this section, let X\subseteq V(G) . The subgraph of G induced by X isdenoted by G[X] . The graph G[V(G)\backslash X] is denoted by G-X . The contraction of G
by X is denoted by G/X . Let F\subseteq E(G) . The graph obtained by deleting F from G
without removing vertices is denoted by G-F . Let H be a subgraph of G . The graphobtained by adding F to H is denoted by H+F . Regarding these operations, we identify
vertices, edges, subgraphs of the newly created graph with the naturally corresponding
items of old graphs.
A neighbor of X is a vertex from V(G)\backslash X that is adjacent to some vertex from X.
The neighbor set of X is denoted by N_{G}(X) . Let Y\subseteq V(G) . The set of edges joining X
and Y is denoted by E_{G}[X, Y] . The set E_{G}[X, V(G)\backslash X] is denoted by \delta_{G}(X) .
A set M\subseteq E(G) is a matching if |\delta_{G}(v)\cap M|\leq 1 holds for each v\in V(G) . For amatching M , we say that M covers a vertex v if |\delta_{G}(v)\cap M|=1 ; otherwise, we say that
M exposes v . A matching is maximum if it consists of the maximum number of edges. A
graph can possess an exponentially large number of matchings. A matching is perfect if
it covers every vertex. A graph is factorizable if it has a perfect matchings. A graph isfactor‐critical if, for each vertex v, G-v is factorizable. A graph with only one vertex
is defined to be factor‐critical. The number of edges in a maximum matching is denotedby v(G) . The number of vertices exposed by a maximum matching is denoted by def(G) ;that is, def(G) :=|V(G)|-2\nu(G) .

39
3

Basics on Matchings

We now explain the Berge Formula and the definition of barriers. An odd component(resp. even component) of a graph is a connected component with an odd (resp. even)number of vertices. The number of odd components of G-X is denoted by q_{G}(X) . The

set of vertices from odd components (resp. even components) of G-X is denoted by D_{X}(resp. C_{X} ).

Theorem 3.1 (Berge Formula [15]). For a graph G, def(G) is equal to the maximum
value of q_{G}(X)-|X| , where X is taken over all subsets of V(G) .
The set of vertices that attains the maximum value in this relation is called a barrier.

That is, a set of vertices X is a barrier if def(G)=q_{G}(X)-|X|.
The set of vertices that can be exposed by maximum matchings is denoted by D(G) .
The neighbor set of D(G) is denoted by A(G) , and the set V(G)\backslash D(G)\backslash A(G) is denotedby C(G) . The following statement about D(G), A(G) , and C(G) is the celebrated Gallai‐

Edmonds structure theorem [5, 6, 15].
Theorem 3.2 (Gallai‐Edmonds Structure Theorem). For any graph G,(i) A(G) is a barrier for which D_{A(G)}=D(G) and C_{A(G)}=C(G) ;(ii) each odd component of G-A(G) is factor‐critical; and,(iii) any edge in E_{G}[A(G), D(G)] is allowed.
An edge is allowed if it is contained in some maximum matching. Two vertices arefactor‐connected if they are connected by a path whose edges are allowed. A subgraphis factor‐connected if any two vertices are factor‐connected. A maximal factor‐connected
subgraph is called a factor‐connected component or factor‐component. A graph consistsof its factor‐components and edges joining them that are not allowed. The set of factor‐
components of G is denoted by \mathcal{G}(G) .
A factor‐component C is inconsistent if V(C)\cap D(G)\neq\emptyset . Otherwise, C is said to beconsistent. We denote the sets of consistent and inconsistent factor‐components of G by\mathcal{G}^{+}(G) and \mathcal{G}^{-}(G) , respectively.

4

Basilica Decomposition

We now introduce the basilica decomposition of graphs [8, 9]. The theory of basilica
decomposition is made up of the three central concepts:(i) a canonical partial order between factor‐components (Theorem 4.2),(ii) the general Kotzig‐Lovász decomposition (Theorem 4.4), and(iii) an interreıationship between the two (Theorem 4.5).
In this section, we explain these three concepts and give the definition of the basilica

decomposition. Every statement in the following is from Kita [8, 9]. In the following, let
G be a graph unless otherwise stated.

40
Definition 4.1. A set X\subseteq V(G) is said to be separating if there exist H_{1} ,, H_{k}\in \mathcal{G}(G) ,where k\geq 1 , such that X=V(H_{1})\cup\cdots\cup V(H_{k}) . For G_{1}, G_{2}\in \mathcal{G}(G) , we say G_{1}\triangleleft G_{2} ifthere exists a separating set X\subseteq V(G) with V(G_{1})\cup V(G_{2})\subseteq X such that G[X]/G_{1} isa factor‐critical graph.

Theorem 4.2. For a graph G , the binary relation \triangleleft is a partial order over \mathcal{G}(G) .
Definition 4.3. For u, v\in V(G)\backslash D(G) , we say u\sim Gv if u and v are identical or if uand v are factor‐connected and satisfy def(G-u-v)>def(G) .
Theorem 4.4. For a graph G , the binary relation ∼ G is an equivalence relation.
We denote as \mathcal{P}(G) the family of equivalence classes determined by\sim G . This family is
known as the general Kotzig‐Lovász decomposition orjust the Kotzig‐Lovász decompositionof G . From the definition of ∼ G , for each H\in \mathcal{G}(G) , the family \{S\in \mathcal{P}(G) : S\subseteq V(H)\}
forms a partition of V(H)\backslash D(G) . We denote this family by \mathcal{P}_{G}(H) .
Let H\in \mathcal{G}(G) . The sets of strict and nonstrict upper bounds of H are denotedby \mathcal{U}_{G}(H) and \mathcal{U}_{G}^{*}(H) , respectively. The sets of vertices \cup\{V(I) : I\in \mathcal{U}_{G}(H)\} and\cup\{V(I) : I\in \mathcal{U}_{G}^{*}(H)\} are denoted by U_{G}(H) and U_{G}^{*}(H) , respectively.

Theorem 4.5. Let G be a graph, and let H\in \mathcal{G}(G) . Then, for each connected component
K of G[U_{G}(H)] , there exists S\in \mathcal{P}_{G}(H) such that N_{G}(K)\cap V(H)\subseteq S.
Under Theorem 4.5, for S\in \mathcal{P}_{G}(H) , we denote by \mathcal{U}_{G}(S) the set of factor‐componentsthat are contained in a connected component K of G[U_{G}(H)] with N_{G}(K)\cap V(H)\subseteq S.
The set \cup\{V(I) : I\in U_{G}(H)\} is denoted by U_{G}(S) . We denote U_{G}(H)\backslash S\backslash U_{G}(S) by

TU_{G}(S).

Theorem 4.5 integrates the two structures given by Theorems 4.2 and 4.4 into a struc‐ture of graphs that is reminiscent of an architectural building. We call this integrated
structure the basilica decomposition of a graph.

5

TFR Poset

We now introduce the new concept of posets with a transitive forbidden relation, which
serves as a language to describe the nonbipartite DM decomposition.
Definition 5.1. Let X be a set, and let \preceq be a partial order over X . Let
relation over X such that,\smilebe a binary(i) for each x, y, z\in X , if x\preceq y and y\smile z hold, then x\smile z holds (transitivity);(ii) for each x\in X, x\smile x does not hold (nonreflexivity); and,(iii) for each x, y\in X , if x\smile y holds, then y\smile x also holds (symmetry).
We call this poset endowed with this additional binary relation a poset with a transitive
forbidden relation or TFR poset in short, and denote this by (X, \preceq, \smile) . We call a pair of
two elements x and y with x\smile y forbidden.

41
41
Let (X, \preceq, \smile) be a TFR poset. For two elements x, y\in X with x\smile y , we say thatx\smile\star y if, there is no z\in X\backslash \{x, y\} with x\preceq z and z\smile y . We call such a forbidden pairof x and y immediate. A TFR poset can be visualized in a similar way to an ordinary
posets. We represent \preceq just in the same way as the Hasse diagrams and depict
byindicating every immediate forbidden pairs.
\smileDefinition 5.2. Let P be a TFR poset (X, \preceq, \smile) . A lower or upper ideal Y of P islegitimate if no elements x, y\in Y satisfy x\smile y . Otherwise, we say that Y is illegitimate.
Let Y be a consistent lower or upper ideal, and let Z be the subset of X\backslash Y such that,for each x\in Z , there exists y\in Y with x\smile y . We say that Y is spanning if Y\cup Z=X.

6

DM Decomposition Theory for General Graphs

We now provide our new theory of the DM decomposition for general graphs. In thissection, unless otherwise stated, let G be a graph.
Definition 6.1. A Dulmage‐Mendelsohn component, or a DM component in short, is a
subgraph of the form G[S\cup^{T}U_{G}(S)] , where S\in \mathcal{P}(G) , endowed with S as an attributeknown as the base. For a DM component C , the base of C is denoted by \pi(C) . Conversely,for S\in \mathcal{P}(G), K(S) denotes the DM components whose base is S . We denote by \mathcal{D}(G)the set of DM components of G.

Hence, distinct DM components can be equivalent as a subgraph of G . Each member
from \mathcal{P}(G) serves as an identifier of a DM component.
Definition 6.2. A DM component C is said to be inconsistent if \pi(C)\in \mathcal{P}_{G}(H) for someH\in \mathcal{G}^{-}(G) ; otherwise, C is said to be consistent. The sets of consistent and inconsistent
DM components are denoted by \mathcal{D}^{+}(G) and \mathcal{D}^{-}(G) , respectively.
Definition 6.3. We define binary relations \preceq^{\circ}and\preceq over \mathcal{D}(G) as follows: for D_{1}, D_{2}\in\mathcal{D}(G) , we let D{\imath}\preceq^{\circ}D_{2} if D_{1}=D_{2} or if N_{G}(^{T}U_{G}(S_{1}) ) \cap S_{2}\neq\emptyset ; we let D_{1}\preceq D_{2} if there
exist C_{1} , . . . , C_{k}\in \mathcal{D}(G) , where k\geq 1 , such that \pi(C_{1})=\pi(D_{1}), \pi(C_{k})=\pi(D_{2}) , andC_{t}\preceq^{\circ}C_{i+1} for each i\in\{1, . . . , k\}\backslash \{k\}.
Definition 6.4. We define binary relations \smile\circ and\smile over \mathcal{D}(G) as follows: for D_{1}, D_{2}\in\mathcal{D}(G) , we let D_{1}\smile\circ D_{2} if \pi(D_{2})\subseteq V(D_{1})\backslash \pi(D_{1}) holds; we let D_{1}\smile D_{2} if there exists
D'\in \mathcal{D}(G) with D_{1}\preceq D' and D'\smile\circ D_{2}.

Theorem 6.5. For a graph G , the triple (\mathcal{D}(G), \preceq, \smile) is a TFR poset.
For a graph G , the TFR poset (\mathcal{D}(G),\underline{S}, \smile) is uniquely determined. We denote thisTFR poset by \mathcal{O}(G) . We call this canonical structure that \mathcal{O}(G) describes the nonbipartite
Dulmage‐Mendelsohn (DM) decomposition of G . This is a generalization of the classicalDM decomposition for bipartite graphs.
Remark 6.6. As mentioned previously, a DM component is identified by its base. There‐
fore, the nonbipartite DM decomposition is essentially the relations between the membersof \mathcal{P}(G) .

Immediate forbidded pairs in \mathcal{O}(G) can be characterized as follows:42
Theorem 6.7. Let G be a graph. Let S, T\in \mathcal{P}(G) . Then, K(S) and K(T) are immediate
forbidden pairs if and only if S and T are contained in the same factor‐component.

Given a graph G , its basilica decomposition can be computed in O(|V(G)|\cdot|E(G)|)

time [8, 9]. Therefore, the next thereom can be stated.

Theorem 6.8. Given a graph G , the TFR poset \mathcal{O}(G) can be computed in O(|V(G)| .

|E(G)|) time.

7

Characterization of Barriers

We now derive the characterization of the family of maximal barriers in generaı graphs
using the nonbipartite DM decomposition. In this section, unless otherwise stated, let
G be a graph. It is a known fact that a graph has an exponentially many number ofmaximal barriers, however the family of maximal barriers can be fully characterized interms of ideals of \mathcal{O}(G) .

Theorem 7.1. Let G be a graph. A set of vertices X\subseteq V(G) is a maximal barrier if
and only if there exists a spanning legitimate normalized upper ideal \mathcal{I} of the TFR poset\mathcal{O}(G) such that X=\cup\{\pi(C) : C\in \mathcal{I}\}.
Acknowledgment and Note

This work is supported by JSPS KAKENHI

15J09683.

A full version of this work is available online [10].
References[1] Duff, I.S., Erisman, A.M., Reid, J.K.: Direct methods for sparse matrices. Clarendon
press Oxford (1986)[2] Dulmage, A.L., Mendelsohn, N.S.: Coverings of bipartite graphs. Canadian Journalof Mathematics 10(4), 516‐534 (1958)[3] Dulmage, A.L., Mendelsohn, N.S.: A structure theory of bi‐partite graphs. Trans.
Royal Society of Canada. Sec. 3. 53, 1‐13 (1959)[4] Dulmage, A.L., Mendelsohn, N.S.: Two algorithms for bipartite graphs. Journal of
the Society for Industrial and Applied Mathematics 11(1), 183‐194 (1963)[5] Edmonds, J.: Paths, trees and flowers. Canadian Journal of Mathematics 17, 449−467(1965)[6] Gallai, T.: Maximale systeme unabhängiger kanten. A Magyer Tudományos
Akadémia: Intézetének Közleményei 8, 401‐413 (1964)[7] Kita, N.:

New canonical decomposition in matching theory. arXiv preprint

arXiv:1708.01051 Under review

43[8] Kita, N.: A Partially Ordered Structure and a Generalization of the Canonical Par‐
tition for General Graphs with Perfect Matchings. In: Chao, K.M., Hsu, T.s., Lee,

D.T. (eds.) 23rd Int. Symp. Algorithms Comput. ISAAC 2012. Lecture Notes in
Computer Science, vol. 7676, pp. 85‐94. Springer (2012)[9] Kita, N.: A partially ordered structure and a generalization of the canonical partition
for general graphs with perfect matchings. arXiv preprint arXiv:1205.3816 (2012)[10] Kita, N.: Nonbipartite Dulmage‐Mendelsohn decomposition for Berge duality. arXiv
preprint arXiv: 1708.00503 (2017)[11] Kotzig, A.: Z teórie konečných grafov s lineárnym faktorom. I. Mathematica Slovaca
9(2), 73‐91 (1959), in Slovak[12] Kotzig, A.: Z teórie konečných grafov s lineárnym faktorom. II. Mathematica Slovaca
9(3), 136‐159 (1959), in Slovak[13] Kotzig, A.: Z teórie konečných grafov s lineárnym faktorom. III. Mathematica Slo‐vaca 10(4), 205‐215 (1960), in Slovak[14] Lovász, L.: On the structure of factorizable graphs. Acta Math. Hungarica 23(1 ‐ 2) ,179‐195 (1972)[15] Lovász, L., Plummer, M.D.: Matching theory, vol. 367. American Mathematical Soc.
(2009)[16] Murota, K.: Matrices and matroids for systems analysis, vol. 20. Springer Science &Business Media (2009)[17] Schrijver, A.: Combinatorial optimization: polyhedra and efficiency, vol. 24. Springer
Science & Business Media (2002)