I specialize in discrete mathematics and theoretical computer science, with a particular focus on graph theory, discrete optimization (combinatorial optimization), and graph algorithms. My research explores graph structures with motivations rooted in optimization theory and algorithm design.
I have extensively worked on establishing fundamental graph decomposition theorems, such as canonical decompositions and constructive characterizations. My key achievements include the derivation of new canonical decompositions for matching theory and T-join (parity factor) theory, and their theoretical applications. The following sections provide an overview of these topics.
Matching is one of the most fundamental and classical concepts in combinatorics, and matching theory is a major branch of graph theory and discrete optimization. A matching (or 1-matching) in a graph is a set of edges that do not share any vertices. It is thus the most primitive concept that represents pairing in a network.
In addition to matchings themselves, a vast number of generalizations and variants of matchings have been proposed. The extensive body of research and theoretical frameworks surrounding these concepts is collectively known as matching theory. It is also well known that matchings are closely connected to concepts involving parity, such as permutations, and that they are related to determinants and permanents. Through these connections, matching theory has made significant contributions to combinatorial matrix theory as well.
In matching theory, a series of graph decomposition theorems (structural decomposition theorems), collectively referred to as canonical decomposition, form the theoretical foundation. Canonical decompositions emerged around the 1960s, with the three classical decompositions being established: the Gallai-Edmonds decomposition (Gallai '64, Edmonds '65), the Kotzig-Lovász decomposition (Kotzig '59-60, Lovász '72), and the Dulmage-Mendelsohn decomposition ('58-'63). These decompositions share several key characteristics: they are uniquely determined for a given graph, and they describe the structure common to all maximum matchings within that graph. Due to these similarities, the concept of canonical decomposition naturally emerged, and these three decompositions came to be understood as constituents of the canonical decomposition framework.
However, classical canonical decompositions faced several limitations, such as being restricted to specific graph classes or providing only coarse decompositions. Specifically, the Dulmage-Mendelsohn decomposition and the Kotzig-Lovász decomposition are applicable to bipartite graphs and factor-connected graphs, respectively. On the other hand, while the Gallai-Edmonds decomposition is defined for arbitrary graphs, it essentially partitions a graph into two parts and describes the internal structure of only one. Consequently, it often fails to extract sufficient information, frequently resulting in the target graph falling into an irreducible class. Furthermore, although the three classical canonical decompositions share common characteristics, their mutual logical relationships remained unclear, and the unifying framework encompassing them was unknown.
To address these issues, I derived new canonical decompositions that target general graphs and encompass existing ones. First, I derived the General Cathedral Decomposition (Kita '12, '25) for general graphs. This serves as a canonical decomposition that functions as both a refinement of the Gallai-Edmonds decomposition and a generalization of the Kotzig-Lovász decomposition. Furthermore, by modifying the General Cathedral Decomposition, I established the Non-bipartite Dulmage-Mendelsohn Decomposition (Kita '18), which generalizes the Dulmage-Mendelsohn decomposition to general graphs. Together, these two interrelated decompositions provide a unified framework for general graphs, encompassing existing canonical decompositions through refinement and generalization.
Lattice-Theoretical Characterization of Maximal Barriers
Duality is a core concept in optimization theory. For the maximum matching problem, a duality theorem known as the Berge formula is well-established. The dual solution defined by the Berge formula is called a barrier of the graph. Generally, very little is known about barriers. Regarding maximal barriers, structural insights described by each of the classical canonical decompositions were previously known. In Kita ('13), I elucidated the structure of maximal barriers in general graphs using the General Cathedral Decomposition. Building on this result, in Kita ('18), I characterized the family of maximal barriers in general graphs as the family of ideals of the partially ordered set (poset) given by the Non-bipartite Dulmage-Mendelsohn Decomposition. This achievement represents the first complete characterization of maximal barriers, encompassing the structural insights previously provided by classical canonical decompositions.
Short Proof of the Saturated Cathedral Theorem (Lovász ’72)
A graph is called saturated if the addition of any non-edge does not create a new matching. The Cathedral Theorem for saturated graphs due to Lovász (1972) provides an inductive characterization of saturated graphs and has been used in the enumeration of matchings. The saturated Cathedral Theorem is also presented in detail in the book by Lovász et al. [Lovász ’86], where a full section is devoted to it. In Kita ’14, an alternative proof of the saturated Cathedral Theorem was obtained in a natural way by utilizing the new canonical decomposition.
A New Graph-Theoretical Proof of the Tight Cut Lemma
The Tight Cut Lemma (Edmonds, Lovász & Pulleyblank, 1982) established that the dimension of the perfect matching polytope is characterized by the set of "bricks" constituting the graph. As such, it is a pivotal theorem that determined the future direction of research on the perfect matching polytope. It is discussed in detail in the seminal books by Lovász et al. [Lovász '86] and Schrijver [Schrijver '03] with dedicated sections or chapters. While the original proof by Edmonds et al. relied on linear programming arguments, in Kita ('17), I provided a purely graph-theoretical proof of the Tight Cut Lemma using the new canonical decomposition.
Pertinent Papers
N. Kita, A partially ordered structure and a generalization of the canonical partition for general graphs with perfect matchings. Lecture Notes in Computer Science, Vol. 7676, 2012, pp. 85–94.
N. Kita, Disclosing barriers: a generalization of the canonical partition based on Lovász’s formulation. Lecture Notes in Computer Science, Vol. 8286, 2013, pp. 402–413.
N. Kita, An alternative proof of Lovász’s cathedral theorem. Journal of the Operations Research Society of Japan, Vol. 57, No. 1, 2014, pp. 15–34.
N. Kita, Structure of towers and a new proof of the Tight Cut Lemma. Lecture Notes in Computer Science, Vol. 10627, 2017, pp. 225–239.
N. Kita, Nonbipartite Dulmage-Mendelsohn decomposition for Berge duality. Lecture Notes in Computer Science, Vol. 10976, 2018, pp. 293–304.
N. Kita, Basilica: new canonical decomposition in matching theory. Journal of Graph Theory, Vol. 108, Issue 3, 2025, pp. 508–543.
References
[Lovasz'86] L. Lovász and M. D. Plummer: Matching Theory. North-Holland Publishing Co, 1986.
[Schrijver'03] A. Schrijver: Combinatorial Optimization. Polyhedra and Efficiency. Springer-Verlag, 2003.
A T-join of a graph is a classical topic in combinatorial optimization that encompasses a variety of routing problems, including the undirected shortest path problem. Given a set of vertices T, an edge set J is called a T-join if, for every vertex, the following equivalence holds: the vertex belongs to T if and only if it is incident to an odd number of edges in J. Depending on the choice of the parameter set T, the T-join problem yields various optimization problems such as the undirected shortest path problem and the postman problem.
Moreover, in graphs that admit a 1-factor (perfect matching), if we take T to be the entire vertex set, then a minimum T-join coincides with a 1-factor; thus, T-joins can also be viewed as a generalization of 1-factors. Several alternative names are known for T-joins: they are also called joins of a graft, where a graft is a pair consisting of a graph and the parameter set T. T-joins are also well known in connection with fundamental problems related to the Ising model, an important model in statistical physics.
While T-joins serve as a generalization of 1-factors (perfect matchings), their properties are significantly more complex. Consequently, the theoretical foundation of T-joins remains underdeveloped compared to the well-established theory of matchings. Against this background, this research aims to build a solid foundation for T-join theory. We are working to achieve this by introducing a canonical decomposition theory specifically designed for T-joins. As a related existing result, Sebo (1987) proposed a T-join analogue of the Kotzig–Lovasz decomposition. However, since this result is restricted to a special class (factor-connected grafts), further developments are required.