We present SRIP, a SAT-based system for solving the Independent Set Reconfiguration Problem (ISRP) under the Token Jumping (TJ) rule. SRIP formulates ISRP with SAT problems employing a clique-partition-based constraint model and a set of pruning constraints that strengthen propagation and reduce the search space for reconfiguration. The resulting model is compiled into a sequence of SAT problems and solved using incremental SAT within a bounded model checking framework, enabling SRIP to compute shortest reconfiguration sequences efficiently. We evaluate SRIP on benchmark instances from the CoRe Challenge, a competition series dedicated to ISRP under TJ. SRIP finds optimal (shortest) reconfiguration sequences for 477 out of 693 instances, achieving the best results among state-of-the-art solvers on this benchmark suite.

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.

In this article, we consider a transformation of k disjoint paths in a graph. For a graph and a pair of k disjoint paths \(\mathcal{P}\) and \(\mathcal{Q}\) connecting the same set of terminal pairs, we aim to determine whether \(\mathcal{P}\) can be transformed to \(\mathcal{Q}\) by repeatedly replacing one path with another path so that the intermediates are also k disjoint paths. The problem is called Disjoint Paths Reconfiguration . We first show that Disjoint Paths Reconfiguration is \(\mathsf{PSPACE}\) -complete even when \(k=2\) . On the other hand, we prove that, when the graph is embedded on a plane and all paths in \(\mathcal{P}\) and \(\mathcal{Q}\) connect the boundaries of two faces, Disjoint Paths Reconfiguration can be solved in polynomial time. The algorithm is based on a topological characterization for rerouting curves on a plane using the algebraic intersection number. We also consider a transformation of disjoint s - t paths as a variant. We show that the disjoint s - t paths reconfiguration problem in planar graphs can be determined in polynomial time, while the problem is \(\mathsf{PSPACE}\) -complete in general.

A ladder lottery , known as “Amidakuji” in Japan, is a common way to decide an assignment at random. In this paper, we investigate reconfiguration and enumeration problems of cyclic ladder lotteries. First, when a permutation π and an optimal displacement vector x are given, we investigate the reconfiguration and enumeration problems of the “optimal” cyclic ladder lotteries of π and x . Next, for a given permutation π we consider reconfiguration and enumeration problems of the optimal displacement vectors of π .

In this paper, we consider a transformation of $k$ disjoint paths in a graph. For a graph and a pair of $k$ disjoint paths $\mathcal{P}$ and $\mathcal{Q}$ connecting the same set of terminal pairs, we aim to determine whether $\mathcal{P}$ can be transformed to $\mathcal{Q}$ by repeatedly replacing one path with another path so that the intermediates are also $k$ disjoint paths. The problem is called Disjoint Paths Reconfiguration. We first show that Disjoint Paths Reconfiguration is PSPACE-complete even when $k=2$. On the other hand, we prove that, when the graph is embedded on a plane and all paths in $\mathcal{P}$ and $\mathcal{Q}$ connect the boundaries of two faces, Disjoint Paths Reconfiguration can be solved in polynomial time. The algorithm is based on a topological characterization for rerouting curves on a plane using the algebraic intersection number. We also consider a transformation of disjoint $s$-$t$ paths as a variant. We show that the disjoint $s$-$t$ paths reconfiguration problem in planar graphs can be determined in polynomial time, while the problem is PSPACE-complete in general.

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.