Matroids are often represented as oracles since there are no unified and compact representations for general matroids. This paper initiates the study of binary decision diagrams (BDDs) and zero-suppressed binary decision diagrams (ZDDs) as relatively compact data structures for representing matroids in a computer. This study particularly focuses on the sizes of BDDs and ZDDs representing matroids. First, we compare the sizes of different variations of BDDs and ZDDs for a matroid. These comparisons involve concise transformations between specific decision diagrams. Second, we provide upper bounds on the size of BDDs and ZDDs for several classes of matroids. These bounds are closely related to the number of minors of the matroid on some subsets of its ground set and depend only on the connectivity function or pathwidth of the matroid, which deeply relates to the classes of matroids called strongly pigeonhole classes. In essence, these results indicate upper bounds on the number of minors for specific classes of matroids and new strongly pigeonhole classes. © 2025 The Author(s)

The graph coloring problem is a well-known combinatorial problem that seeks a coloring pattern such that no two adjacent vertices share the same color. In this paper, we propose an efficient method not only for finding one solution but also for efficiently enumerating all solutions that satisfy the graph coloring constraints. Our method uses ZDDs (Zero-suppressed Binary Decision Diagrams) for efficiently indexing sets of graph coloring patterns. In addition, we propose an algorithm to generate all coloring patterns that do not split any cell of a given set partition. Our experimental results demonstrate that the proposed method significantly outperforms existing solvers. Compared to the leading ASP (Answer Set Programming) solver, our approach generates all coloring patterns more than 1,000 times faster. Our method is applicable to many practical graph instances with up to around 25 vertices, in a feasible computation time. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2026.

We introduce the Multi-Objective Combinatorial Reconfiguration Optimization Problem (MO-CROP), and propose an Answer Set Programming (ASP) based approach for its solution. MO-CROP involves finding the Pareto-optimal sequences (or Pareto front) of adjacent feasible solutions between two given feasible solutions of a combinatorial problem, considering both cost and length. Our algorithm is compactly implemented through multi-shot ASP solving, and its implementing solver optirecon provides an effective tool for solving MO-CROP. As a concrete example of MO-CROP, we present an ASP encoding for solving the multi-objective independent set reconfiguration optimization problem. Experimental results on the benchmark set from the recent CoRe Challenge demonstrate our approach's ability to capture diverse optimal sequences that reveal trade-offs between cost and length, a capability often lacking in traditional combinatorial reconfiguration methods. © 2025 The Authors.