Abstract Fairly allocating indivisible goods is a frequently occurring task in everyday life. Given an initial allocation of the goods, we consider the problem of reforming it via a sequence of exchanges to attain fairness in the form of envy-freeness up to one good (EF1). We present a vast array of results on the complexity of determining whether it is possible to reach an EF1 allocation from the initial allocation and, if so, the minimum number of exchanges required. In particular, we uncover several distinctions based on the number of agents involved and their utility functions. Furthermore, we derive essentially tight bounds on the worst-case number of exchanges needed to achieve EF1 when the initial allocation is balanced.

Abstract. We prove that the computation of a combinatorial shortest path between two vertices of a graph associahedron, introduced by Carr and Devadoss, is NP-hard. This resolves an open problem raised by Cardinal. A graph associahedron is a generalization of the well-known associahedron. The associahedron is obtained as the graph associahedron of a path. Whether the combinatorial (i.e., graph-theoretic) distance between vertices of the associahedron can be computed in polynomial time is a tantalizing and important open problem, which is identical to the computation of the flip distance between two triangulations of a convex polygon, and the rotation distance between two rooted binary trees. Our result shows that an approach for this open problem is not promising if it is applicable to the generalized problem on graph associahedra. As a corollary of our theorem, we prove that the computation of a combinatorial shortest path between two vertices of a polymatroid base polytope cannot be done in polynomial time unless [Formula: see text]. Since a combinatorial shortest path on the matroid base polytope can be computed in polynomial time, our result reveals an unexpected contrast between matroids and polymatroids.

We study the electrical distribution network reconfiguration problem, defined as follows. We are given an undirected graph with a root vertex, demand at each non-root vertex, and resistance on each edge. Then, we want to find a spanning tree of the graph that specifies the routing of power from the root to each vertex so that all the demands are satisfied and the energy loss is minimized. This problem is known to be NP-hard in general. When restricted to grids with uniform resistance and the root located at a corner, Gupta, Khodabaksh, Mortagy and Nikolova [Mathematical Programming 2022] invented the so-called Min-Min algorithm whose approximation factor is theoretically guaranteed. Our contributions are twofold. First, we prove that the problem is NP-hard even for grids; this resolves the open problem posed by Gupta et al. Second, we give a refined analysis of the Min-Min algorithm and improve its approximation factor under the same setup. In the analysis, we formulate the problem of giving an upper bound for the approximation factor as a non-linear optimization problem that maximizes a convex function over a polytope.

Contextual Inverse Optimization (CIO) is a generalized framework of the predict-then-optimize approach, also referred to as decision-focused learning or contextual optimization, aiming to learn a model that predicts the unknown parameters of a nominal optimization problem using related covariates without compromising the solution quality. Unlike the predict-then-optimize approach, which assumes access to datasets containing realized unknown parameters, CIO considers a setting where only historical optimal solutions are available. Previous work has primarily focused on CIO under linear programming problems and proposed methods based on optimality conditions. In this study, we propose a general algorithm based on inverse optimization as a more general approach that does not require optimality conditions. To validate its effectiveness, we apply the proposed method to multiple CIO problems and demonstrate that it performs comparably to or better than existing predict-then-optimize methods, even without ground-truth unknown parameters.

The minimum sum coloring problem with bundles was introduced by Darbouy and Friggstad (SWAT 2024) as a common generalization of the minimum coloring problem and the minimum sum coloring problem. During their presentation, the following open problem was raised: whether the minimum sum coloring problem with bundles could be solved in polynomial time for trees. We answer their question in the negative by proving that the minimum sum coloring problem with bundles is NP-hard even for paths. We complement this hardness by providing algorithms of the following types. First, we provide a fixed-parameter algorithm for trees when the number of bundles is a parameter; this can be extended to graphs of bounded treewidth. Second, we provide a polynomial-time algorithm for trees when bundles form a partition of the vertex set and the difference between the number of vertices and the number of bundles is constant. Third, we provide a polynomial-time algorithm for trees when bundles form a partition of the vertex set and each bundle induces a connected subgraph. We further show that for bipartite graphs, the problem with weights is NP-hard even when the number of bundles is at least three, but is polynomial-time solvable when the number of bundles is at most two. The threshold shifts to three versus four for the problem without weights.

Fairly allocating indivisible goods is a frequently occurring task in everyday life. Given an initial allocation of the goods, we consider the problem of reforming it via a sequence of exchanges to attain fairness in the form of envy-freeness up to one good (EF1). We present a vast array of results on the complexity of determining whether it is possible to reach an EF1 allocation from the initial allocation and, if so, the minimum number of exchanges required. In particular, we uncover several distinctions based on the number of agents involved and their utility functions. Furthermore, we derive essentially tight bounds on the worst-case number of exchanges needed to achieve EF1.

ABSTRACT A dynamic network is a directed graph where an arc has a capacity and a transit time. A dynamic flow is a flow defined in a dynamic network. We consider the problem of finding a minimum‐cost dynamic flow in a dynamic network where an arc has a cost. It is known that this problem is NP‐hard. Klinz and Woeginger asked whether the minimum‐cost dynamic flow problem in a fixed graph (i.e., a graph is given a priori, and it is not a part of the input) can be solved in polynomial time. We prove that if the cost of each arc is non‐negative, the capacity of each arc is an integer, and the target flow value is a constant integer, then this problem can be solved in polynomial time.

Abstract. We consider a many-to-one variant of the stable matching problem. More concretely, we consider the variant of the stable matching problem where the preference of each agent may contain ties and one side has a matroid constraint. We consider the problem of checking the existence of a strongly stable matching, and finding a strongly stable matching if one exists. For this problem, we propose a polynomial-time algorithm.

The qubit routing problem, also known as the swap minimization problem, is a (classical) combinatorial optimization problem that arises in the design of compilers of quantum programs. We study the qubit routing problem from the viewpoint of theoretical computer science, while most of the existing studies investigated the practical aspects. We concentrate on the linear nearest neighbor (LNN) architectures of quantum computers, in which the graph topology is a path. Our results are three-fold. (1) We prove that the qubit routing problem is NP-hard. (2) We show that the qubit routing problem on a path can be solved in a fixed-parameter time where the number of two-qubit gates is a parameter. (3) We show that the qubit routing problem on a path can be solved in polynomial time if each qubit is involved in at most one two-qubit gate.

In the allocation of indivisible goods, a prominent fairness notion is envy-freeness up to one good (EF1). We initiate the study of reachability problems in fair division by investigating the problem of whether one EF1 allocation can be reached from another EF1 allocation via a sequence of exchanges such that every intermediate allocation is also EF1. We show that two EF1 allocations may not be reachable from each other even in the case of two agents, and deciding their reachability is PSPACE-complete in general. On the other hand, we prove that reachability is guaranteed for two agents with identical or binary utilities as well as for any number of agents with identical binary utilities. We also examine the complexity of deciding whether there is an EF1 exchange sequence that is optimal in the number of exchanges required.

Abstract In the allocation of indivisible goods, a prominent fairness notion is envy-freeness up to one good (EF1). We initiate the study of reachability problems in fair division by investigating the problem of whether one EF1 allocation can be reached from another EF1 allocation via a sequence of exchanges such that every intermediate allocation is also EF1. We show that two EF1 allocations may not be reachable from each other even in the case of two agents, and deciding their reachability is PSPACE-complete in general. On the other hand, we prove that reachability is guaranteed for two agents with identical or binary utilities as well as for any number of agents with identical binary utilities. We also examine the complexity of deciding whether there is an EF1 exchange sequence that is optimal in the number of exchanges required.

In fair division problems, we are given a set S of m items and a set N of n agents with individual preferences, and the goal is to find an allocation of items among agents so that each agent finds the allocation fair. There are several established fairness concepts and envy-freeness is one of the most extensively studied ones. However envy-free allocations do not always exist when items are indivisible and this has motivated relaxations of envy-freeness: envy-freeness up to one item (EF1) and envy-freeness up to any item (EFX) are two well-studied relaxations. We consider the problem of finding EF1 and EFX allocations for utility functions that are not necessarily monotone, and propose four possible extensions of different strength to this setting. In particular, we present a polynomial time algorithm for finding an EF1 allocation for two agents with arbitrary utility functions. An example is given showing that EFX allocations need not exist for two agents with non-monotone, non-additive, identical utility functions. However, when all agents have monotone (not necessarily additive) identical utility functions, we give a pseudo-polynomial time algorithm that always finds an EFX allocation of chores. As a step toward understanding the general case, we discuss two subclasses of utility functions: Boolean utilities that are {0,+1}-valued functions, and negative Boolean utilities that are {0,−1}-valued functions. For the latter, we give a polynomial time algorithm that finds an EFX allocation when the utility functions are identical.

We initiate the study of k -edge-connected orientations of undirected graphs through edge flips for k ≥ 2. We prove that in every orientation of an undirected 2k -edge-connected graph, there exists a sequence of edges such that flipping their directions one by one does not decrease the edge connectivity, and the final orientation is k -edge connected. This yields an “edge-flip based” new proof of Nash-Williams’ theorem: A undirected graph G has a k -edge-connected orientation if and only if G is 2k -edge connected. As another consequence of the theorem, we prove that the edge-flip graph of k -edge-connected orientations of an undirected graph G is connected if G is (2k+2) -edge connected. This has been known to be true only when k=1 .

We consider the problem of reforming an envy-free matching when each agent is assigned a single item. Given an envy-free matching, we consider an operation to exchange the item of an agent with an unassigned item preferred by the agent that results in another envy-free matching. We repeat this operation as long as we can. We prove that the resulting envy-free matching is uniquely determined up to the choice of an initial envy-free matching, and can be found in polynomial time. We call the resulting matching a reformist envy-free matching, and then we study a shortest sequence to obtain the reformist envy-free matching from an initial envy-free matching. We prove that a shortest sequence is computationally hard to obtain even when each agent accepts at most four items and each item is accepted by at most three agents. On the other hand, we give polynomial-time algorithms when each agent accepts at most three items or each item is accepted by at most two agents. Inapproximability and fixed-parameter (in)tractability are also discussed.

We initiate the study of k-edge-connected orientations of undirected graphs through edge flips for k ≥ 2. We prove that in every orientation of an undirected 2k-edge-connected graph, there exists a sequence of edges such that flipping their directions one by one does not decrease the edge-connectivity, and the final orientation is k-edge-connected. This yields an “edge-flip based” new proof of Nash-Williams' theorem: an undirected graph G has a k-edge-connected orientation if and only if G is 2k-edge-connected. As another consequence of the theorem, we prove that the edge-flip graph of k-edge-connected orientations of an undirected graph G is connected if G is (2k + 2)-edge-connected. This has been known to be true only when k = 1.

Motivated by adjacency in perfect matching polytopes, we study the shortest reconfiguration problem of perfect matchings via alternating cycles. Namely, we want to find a shortest sequence of perfect matchings which transforms one given perfect matching to another given perfect matching such that the symmetric difference of each pair of consecutive perfect matchings is a single cycle. The problem is equivalent to the combinatorial shortest path problem in perfect matching polytopes. We prove that the problem is NP-hard even when a given graph is planar or bipartite, but it can be solved in polynomial time when the graph is outerplanar.

A super-stable matching is a solution concept in the variant of the stable matching problem in which the preferences may contain ties. Irving proposed a polynomial-time algorithm for the problem of checking the existence of a super-stable matching and finding a super-stable matching if a super-stable matching exists. In this paper, we consider a matroid generalization of a super-stable matching. We call our generalization of a super-stable matching a super-stable common independent set. This can be considered as a generalization of the matroid generalization of a stable matching for strict preferences proposed by Fleiner. We propose a polynomial-time algorithm for the problem of checking the existence of a super-stable common independent set and finding a super-stable common independent set if a super-stable common independent set exists.

Abstract A dynamic network introduced by Ford and Fulkerson is a directed graph in which each arc has a capacity and a transit time. The evacuation problem is one of the fundamental problems in a dynamic network. The goal of this problem is to find the minimum time limit Θ such that we can send all the supplies to the sinks within time Θ. An earliest arrival flow is an optimal flow for the evacuation problem such that the amount of supplies which have reached the sinks is maximized at every time step. It is known that in a dynamic network with multiple sinks, if the sinks have capacities, then an earliest arrival flow does not necessarily exist. In this paper, to cope with this issue, we first introduce a lexicographically optimal earliest arrival flow in a dynamic network with multiple sinks. Then we propose a pseudo‐polynomial‐time algorithm for finding a lexicographically optimal earliest arrival flow. Furthermore, we prove that if the transit time of every arc is zero, then we can find a lexicographically optimal earliest arrival flow in polynomial time.

Motivated by adjacency in perfect matching polytopes, we study the shortest reconfiguration problem of perfect matchings via alternating cycles. Namely, we want to find a shortest sequence of perfect matchings which transforms one given perfect matching to another given perfect matching such that the symmetric difference of each pair of consecutive perfect matchings is a single cycle. The problem is equivalent to the combinatorial shortest path problem in perfect matching polytopes. We prove that the problem is NP-hard even when a given graph is planar or bipartite, but it can be solved in polynomial time when the graph is outerplanar.

The Pareto stability is one of the solution concepts in two-sided matching markets with ties. It is known that there always exists a Pareto stable matching in the many-to-many setting. In this paper, we consider the following generalization of the Pareto stable matching problem in the many-to-many setting. Each agent $v$ of one side has a matroid defined on the set of edges incident to $v$, and the set of edges assigned to $v$ must be an independent set of this matroid. By extending the algorithm of Kamiyama for the many-to-many setting, we prove that there always exists a Pareto stable matching in this setting, and a Pareto stable matching can be found in polynomial time.

In this paper, we consider the complexity of the problem of finding a stable fractional matching in a hypergraphic preference system. Aharoni and Fleiner proved that there exists a stable fractional matching in every hypergraphic preference system. Furthermore, Kintali, Poplawski, Rajaraman, Sundaram, and Teng proved that the problem of finding a stable fractional matching in a hypergraphic preference system is PPAD-complete. In this paper, we consider the complexity of the problem of finding a stable fractional matching in a hypergraphic preference system whose maximum degree is bounded by some constant. The proof by Kintali, Poplawski, Rajaraman, Sundaram, and Teng implies the PPAD-completeness of the problem of finding a stable fractional matching in a hypergraphic preference system whose maximum degree is 5. In this paper, we prove that (i) this problem is PPAD-complete even if the maximum degree is 3, and (ii) if the maximum degree is 2, then this problem can be solved in polynomial time. Furthermore, we prove that the problem of finding an approximate stable fractional matching in a hypergraphic preference system is PPAD-complete.

In this paper, we introduce the concept of b-branchings in digraphs, which is a generalization of branchings serving as a counterpart of b-matchings. Here b is a positive integer vector on the vertex set of a digraph, and a b-branching is defined as a common independent set of two matroids defined by b: an arc set is a b-branching if it has at most b(v) arcs sharing the terminal vertex v, and it is an independent set of a certain sparsity matroid defined by b. We demonstrate that b-branchings yield an appropriate generalization of branchings by extending several classical results on branchings. We first present a multi-phase greedy algorithm for finding a maximum-weight b-branching. We then prove a packing theorem extending Edmonds' disjoint branchings theorem, and provide a strongly polynomial algorithm for finding optimal disjoint b-branchings. As a consequence of the packing theorem, we prove the integer decomposition property of the b-branching polytope. Finally, we deal with a further generalization in which a matroid constraint is imposed on the b(v) arcs sharing the terminal vertex v.

Assume that we are given a set of applicants and a set of posts such that each applicant has a preference list over the posts. A matching $M$ between the applicants and the posts is said to be popular if there is no other matching $N$ such that the number of applicants that prefer $N$ to $M$ is larger than the number of applicants that prefer $M$ to $N$. Then, the goal of the popular matching problem is to decide whether there is a popular matching, and find a popular matching if one exists. Abraham, Irving, Kavitha, and Mehlhorn proved that this problem can be solved in polynomial time even if the preference lists contain ties. In this paper, we consider the popular matching problem with matroid constraints. In this problem, for each post, we are given a matroid on the set of applicants. A set of applicants assigned to each post must be an independent set of its matroid. Kamiyama proved that if there is not a tie in the preference lists, then this problem can be solved in polynomial time. In this paper, we prove that even if there are ties in the preference lists, this problem can be solved in polynomial time.

In SODA'10, Huang introduced the laminar classified stable matching problem (LCSM for short) that is motivated by academic hiring. This problem is an extension of the well-known hospitals/residents problem in which a hospital has laminar classes of residents and it sets lower and upper bounds on the number of residents that it would hire in that class. Against the intuition that stable matching problems with lower quotas are difficult in general, Huang proved that this problem can be solved in polynomial time. In this paper, we propose a matroid-based approach to this problem and we obtain the following results. (i) We solve a generalization of the LCSM problem. (ii) We exhibit a polyhedral description for stable assignments of the LCSM problem, which gives a positive answer to Huang's question. (iii) We prove that the set of stable assignments of the LCSM problem has a lattice structure similarly to the ordinary stable matching model.