The class PLS (Polynomial Local Search) captures the complexity of finding a solution that is locally optimal and has proven to be an important concept in the theory of local search. It has been shown that local search versions of various combinatorial optimization problems, such as Maximum Independent Set and Max Cut, are complete for this class. Such computational intractability typically arises in local search problems allowing arbitrary weights; in contrast, for unweighted problems, locally optimal solutions can be found in polynomial time under standard settings. In this paper, we pursue the complexity of local search problems from a different angle: We show that computing two locally optimal solutions is NP-hard for various natural unweighted local search problems, including Maximum Independent Set, Minimum Dominating Set, Max SAT, and Max Cut. We also discuss several tractable cases for finding two (or more) local optimal solutions.

An LZ-like factorization of a string divides it into factors, each being either a single character or a copy of a preceding substring. While grammar-based compression schemes support efficient random access with space linear in the compressed size, no comparable guarantees are known for general LZ-like factorizations. This limitation motivated restricted variants such as LZ-End [Kreft and Navarro, 2013] and height-bounded LZ (LZHB) [Bannai et al., 2024], which trade off some compression efficiency for faster access. In this paper, we introduce LZ-Begin-End (LZBE), a new LZ-like variant in which every copy factor must refer to a contiguous sequence of preceding factors. This structural restriction ensures that any context-free grammar can be transformed into an LZBE factorization of the same size. We further study the greedy LZBE factorization, which selects each copy factor to be as long as possible while processing the input from left to right, and show that it can be computed in linear time. Moreover, we exhibit a family of strings for which the greedy LZBE factorization is asymptotically smaller than the smallest grammar. These results demonstrate that the LZBE scheme is strictly more expressive than grammar-based compression in the worst case. To support fast queries, we propose a data structure for LZBE-compressed strings that permits O(log n)-time random access within space linear in the compressed size, where n is the length of the input string.

Consider a matroid $M$ whose ground set is equipped with a labeling to an abelian group. A basis of $M$ is called $F$-avoiding if the sum of the labels of its elements is not in a forbidden label set $F$. Hörsch, Imolay, Mizutani, Oki, and Schwarcz (2024) conjectured that if an $F$-avoiding basis exists, then any basis can be transformed into an $F$-avoiding basis by exchanging at most $|F|$ elements. This proximity conjecture is known to hold for certain specific groups; in the case where $|F| \le 2$; or when the matroid is subsequence-interchangeably base orderable (SIBO), which is a weakening of the so-called strongly base orderable (SBO) property. In this paper, we settle the proximity conjecture for sparse paving matroids or in the case where $|F| \le 4$. Related to the latter result, we present the first known example of a non-SIBO matroid. We further address the setting of multiple group-label constraints, showing proximity results for the cases of two labelings, SIBO matroids, matroids representable over a fixed, finite field, and sparse paving matroids.

Bérczi K., Király T., Kobayashi Y., et al. Finding spanning trees with perfect matchings. Discrete Applied Mathematics 371, 137 (2025); https://doi.org/10.1016/j.dam.2025.04.001.

In this paper, we propose a randomized Õ(µ(G))-round algorithm for the maximum cardinality matching problem in the CONGEST model, where µ(G) means the maximum size of a matching of the input graph G. The proposed algorithm substantially improves the current best worst-case running time. The key technical ingredient is a new randomized algorithm of finding an augmenting path of length ℓ with high probability within Õ(ℓ) rounds, which positively settles an open problem left in the prior work by Ahmadi and Kuhn [DISC’20].

We consider the Shortest Odd Path problem, where given an undirected graph G , a weight function on its edges, and two vertices s and t in G , the aim is to find an ( s , t ) -path with odd length and, among all such paths, of minimum weight. For the case when the weight function is conservative, i.e., when every cycle has non-negative total weight, the complexity of the Shortest Odd Path problem had been open for 20 years, and was recently shown to be NP -hard. We give a polynomial-time algorithm for the special case when the weight function is conservative and the set E − of negative-weight edges forms a single tree. Our algorithm exploits the strong connection between Shortest Odd Path and the problem of finding two internally vertex-disjoint paths between two terminals in an undirected edge-weighted graph. It also relies on solving an intermediary problem variant called Shortest Parity-Constrained Odd Path where for certain edges we have parity constraints on their position along the path. Also, we exhibit two FPT algorithms for solving Shortest Odd Path . The first FPT algorithm is parameterized by | E − | , the number of negative edges, or more generally, by the maximum size of a matching in the subgraph of G spanned by E − , when the weight function is conservative. Our second FPT algorithm is parameterized by the treewidth of G , and the algorithm does not rely on conservativeness.

Abstract. Matroid intersection is one of the most powerful frameworks of matroid theory that generalizes various problems in combinatorial optimization. Edmonds’ fundamental theorem provides a min-max characterization for the unweighted setting, while Frank’s weight-splitting theorem provides one for the weighted case. Several efficient algorithms were developed for these problems, all relying on the usage of one of the conventional oracles for both matroids. In the present paper, we consider the tractability of the matroid intersection problem under restricted oracles. In particular, we focus on the rank sum, common independence, and maximum rank oracles. We give a strongly polynomial-time algorithm for weighted matroid intersection under the rank sum oracle. In the common independence oracle model, we prove that the unweighted matroid intersection problem is tractable when one of the matroids is a partition matroid and that even the weighted case is solvable when one of the matroids is an elementary split matroid. Finally, we show that the common independence and maximum rank oracles together are strong enough to realize the steps of our algorithm under the rank sum oracle.

In the list coloring problem for two matroids, we are given matroids $M_1=(S,{\mathcal{I}}_1)$ and $M_2=(S,{\mathcal{I}}_2)$ on the same ground set $S$, and the goal is to determine the smallest number $k$ such that, given arbitrary lists $L_s$ of $k$ colors for $s\in S$, it is possible to choose a color from each list so that every monochromatic set is independent in both $M_1$ and $M_2$. When both $M_1$ and $M_2$ are partition matroids, Galvin's celebrated list coloring theorem for bipartite graphs gives the answer. However, not much is known about the general case. One of the main open questions is to decide if there exists a constant $c$ such that if the coloring number is $k$ (i.e., the ground set can be partitioned into $k$ common independent sets), then the list coloring number is at most $c\cdot k$. In the present paper, we consider matroid classes that appear naturally in combinatorial and graph optimization problems, specifically graphic matroids, paving matroids and gammoids. We show that if both matroids are from these fundamental classes, then the list coloring number is at most twice the coloring number. The proof is based on a new approach that reduces a matroid to a partition matroid without increasing its coloring number too much and might be of independent combinatorial interest. In particular, we show that if $M=(S,{\mathcal{I}})$ is a matroid in which $S$ can be partitioned into $k$ independent sets, then there exists a partition matroid $N=(S,{\mathcal{J}})$ with ${\mathcal{J}}\subseteq{\mathcal{I}}$ in which $S$ can be partitioned into (A) $k$ independent sets if $M$ is a transversal matroid, (B) $2k-1$ independent sets if $M$ is a graphic matroid, (C) $\lceil kr/(r-1)\rceil$ independent sets if $M$ is a paving matroid of rank $r$, and (D) $2k-2$ independent sets if $M$ is a gammoid. It should be emphasized that in cases (A), (B), and (D) the rank of $N$ is the same as that of $M$. We further extend our results to a much broader family by showing that taking direct sum, homomorphic image, or truncation of matroids from these classes results in a matroid admitting a reduction to a partition matroid with coloring number at most twice the original one.

We study a constrained shortest path problem in group-labeled graphs with nonnegative edge length, called the shortest non-zero path problem. Depending on the group in question, this problem includes two types of tractable variants in undirected graphs: one is the parity-constrained shortest path/cycle problem, and the other is computing a shortest noncontractible cycle in surface-embedded graphs. For the shortest non-zero path problem with respect to finite abelian groups, Kobayashi and Toyooka (2017) proposed a randomized, pseudopolynomial algorithm via permanent computation. For a slightly more general class of groups, Yamaguchi (2016) showed a reduction of the problem to the weighted linear matroid parity problem. In particular, some cases are solved in strongly polynomial time via the reduction with the aid of a deterministic, polynomial algorithm for the weighted linear matroid parity problem developed by Iwata and Kobayashi (2017), which generalizes a well-known fact that the parity-constrained shortest path problem is solved via weighted matching. In this paper, as the first general solution independent of the group, we present a rather simple, deterministic, and strongly polynomial algorithm for the shortest non-zero path problem. The algorithm is based on Dijkstra's algorithm for the unconstrained shortest path problem and Edmonds' blossom shrinking technique in matching algorithms, and clarifies a common tractable feature behind the parity and topological constraints in the shortest path/cycle problem.

A recent trend in the design of FPT algorithms is exploiting the half-integrality of LP relaxations. In other words, starting with a half-integral optimal solution to an LP relaxation, we assign integral values to variables one-by-one by branch and bound. This technique is general and the resulting time complexity has a low dependency on the parameter. However, the time complexity often becomes a large polynomial in the input size because we need to compute half-integral optimal LP solutions. In this paper, we address this issue by providing an O(km)-time algorithm for solving the LPs arising from various FPT problems, where k is the optimal value and m is the number of edges/constraints. Our algorithm is based on interesting connections among 0/1/all constraints, which has been studied in the field of constraints satisfaction, A-path packing, which has been studied in the field of combinatorial optimization, and the LPs used in FPT algorithms. With the aid of this algorithm, we obtain linear-time FPT algorithms for various problems. The obtained running time for each problem is linear in the input size and has the current smallest dependency on the parameter. Most importantly, instead of using problem-specific approaches, we obtain all of these results by a unified approach, i.e., the branch-and-bound framework combined with the efficient computation of half-integral LPs, which demonstrates its generality.

We study a decentralized matching market in which each firm sequentially makes offers to potential workers. For each offer, the worker can choose "accept" or "reject," but the decision is irrevocable. The acceptance of an offer guarantees her job at the firm, but it may also eliminate chances of better offers from other firms in the future. We formulate this market as a perfect-information extensive-form game played by the workers. Each instance of this game has a unique subgame perfect equilibrium (SPE), which does not necessarily lead to a stable matching and has some perplexing properties. Our aim is to establish the complexity of computing the SPE, or more precisely, deciding whether each offer is accepted in the SPE. We show that the tractability of this problem drastically changes according to the number of potential offers related to each firm and worker. If each firm makes offers to at most two workers (or each worker receives offers from at most two firms), then the problem is efficiently solved by a variant of the deferred acceptance algorithm. In contrast, the problem is PSPACE-hard even if both firms and workers are related to at most three offers.

We consider a stochastic variant of the packing-type integer linear programming problem, which contains random variables in the objective vector. We are allowed to reveal each entry of the objective vector by conducting a query, and the task is to find a good solution by conducting a small number of queries. We propose a general framework of adaptive and non-adaptive algorithms for this problem, and provide a unified methodology for analyzing the performance of those algorithms. We also demonstrate our framework by applying it to a variety of stochastic combinatorial optimization problems such as matching, matroid, and stable set problems.

The Dulmage--Mendelsohn decomposition (or the DM-decomposition) gives a unique partition of the vertex set of a bipartite graph reflecting the structure of all the maximum matchings therein. A bipartite graph is said to be DM-irreducible if its DM-decomposition consists of a single component. In this paper, we focus on the problem of making a given bipartite graph DM-irreducible by adding edges. When the input bipartite graph is balanced (i.e., both sides have the same number of vertices) and has a perfect matching, this problem is equivalent to making a directed graph strongly connected by adding edges, for which the minimum number of additional edges was characterized by Eswaran and Tarjan [ SIAM J. Comput., 5 (1976), pp. 653--665]. We give a general solution to this problem, which is divided into three parts. We first show that our problem can be formulated as a special case of a general framework of covering supermodular functions, which was introduced by Frank and Jordán [ J. Combin. Theory Ser. B, 65 (1995), pp. 73--110] to investigate the directed connectivity augmentation problem. Second, when the input graph is not balanced, the problem is solved via matroid intersection. This result can be extended to the minimum cost version in which the addition of an edge gives rise to an individual cost. Third, for balanced input graphs, we devise a combinatorial algorithm that finds a minimum number of additional edges to attain the DM-irreducibility, while the minimum cost version of this problem is NP-hard. These results also lead to min-max characterizations of the minimum number, which generalize the result of Eswaran and Tarjan.

Mader's disjoint S-paths problem unifies two generalizations of bipartite matching: (a) non-bipartite matching and (b) disjoint s–t paths. Lovász (1980, 1981) first proposed an efficient algorithm for this problem via a reduction to matroid matching, which also unifies two generalizations of bipartite matching: (a) non-bipartite matching and (c) matroid intersection. While the weighted versions of the problems (a)-(c) in which we aim to minimize the total weight of a designated-size feasible solution are known to be solvable in polynomial time, the tractability of such a weighted version of Mader's problem has been open for a long while. In this paper, we present the first solution to this problem with the aid of a linear representation for Lovász' reduction (which leads to a reduction to linear matroid parity) due to Schrijver (2003) and polynomial-time algorithms for a weighted version of linear matroid parity announced by Iwata (2013) and by Pap (2013). Specifically, we give a reduction of the weighted version of Mader's problem to weighted linear matroid parity, which leads to an O(n^5)-time algorithm for the former problem, where n denotes the number of vertices in the input graph. Our reduction technique is also applicable to a further generalized framework, packing non-zero A-paths in group-labeled graphs, introduced by Chudnovsky, Geelen, Gerards, Goddyn, Lohman, and Seymour (2006). The extension leads to the tractability of a broader class of weighted problems not restricted to Mader’s setting.

Mader's disjoint ${\cal S}$-paths problem is a common generalization of non-bipartite matching and Menger's disjoint paths problems. Lovász [J. Combin. Theory Ser. B, 28 (1980), pp. 208--236]) proposed a polynomial-time algorithm for this problem through a reduction to matroid matching. A more direct reduction to the linear matroid parity problem was given later by Schrijver [Combinatorial Optimization: Polyhedra and Efficiency, Springer-Verlag, Berlin, 2003], which led to faster algorithms. As a generalization of Mader's problem, Chudnovsky et al. [Combinatorica, 26 (2006), pp. 521--532] introduced a framework of packing non-zero $A$-paths in group-labelled graphs and proved a min-max theorem. Chudnovsky, Cunningham, and Geelen [Combinatorica, 28 (2008), pp. 145--161] provided an efficient combinatorial algorithm for this generalized problem. On the other hand, Pap [Combinatorica, 27 (2007), pp. 247--251] introduced a framework of packing non-returning $A$-paths as a further generalization. In this paper, we discuss possible extensions of Schrijver's reduction technique and the algorithm of Chudnovsky, Cunningham, and Geelen [Combinatorica, 28 (2008), pp. 145--161] to another framework introduced by Pap [A Constructive Approach to Matching and Its Generalizations, Ph.D. thesis, Institute of Mathematics, Eötvös Loránd University, Budapest, Hungary, 2006], under the name of the subgroup model, which apparently generalizes but in fact is equivalent to packing nonreturning $A$-paths. Extracting combinatorial aspects of Schrijver's reduction, we introduce the concept of coherent representation and provide a necessary and sufficient condition for the groups in question to admit a reduction to the linear matroid parity problem with coherent representations. As a consequence, we give faster algorithms for important special cases of packing nonzero $A$-paths. In addition, it turns out that packing nonreturning $A$-paths admits such a reduction to the linear matroid parity problem if and only if the size of the input label set is at most four, which leads to its efficient solvability in this special case.

Mader's disjoint S-paths problem is a common generalization of non-bipartite matching and Menger's disjoint paths problems. Lovász (1980) suggested a polynomial-time algorithm for this problem through a reduction to matroid matching. A more direct reduction to the linear matroid parity problem was given later by Schrijver (2003), which leads to faster algorithms. As a generalization of Mader's problem, Chudnovsky, Geelen, Gerards, Goddyn, Lohman, and Seymour (2006) introduced a framework of packing non-zero A-paths in group-labelled graphs, and proved a min-max theorem. Chudnovsky, Cunningham, and Geelen (2008) provided an efficient combinatorial algorithm for this generalized problem. On the other hand, Pap (2007) introduced a framework of packing non-returning A-paths as a further genaralization. In this paper, we discuss a possible extension of Schrijver's reduction technique to another framework introduced by Pap (2006), under the name of the subgroup model, which apparently generalizes but in fact is equivalent to packing non-returning A-paths. We provide a necessary and sufficient condition for the groups in question to admit a reduction to the linear matroid parity problem. As a consequence, we give faster algorithms for important special cases of packing non-zero A-paths such as odd-length A-paths. In addition, it turns out that packing non-returning A-paths admits a reduction to the linear matroid parity problem, which leads to the quite efficient solvability, if and only if the size of the input label set is at most four.