Search

In this paper, we consider the reconfiguration problem of integer linear systems. In this problem, we are given an integer linear system I and two feasible solutions s and t of I , and then asked to transform s to t by changing a value of only one variable at a time, while maintaining a feasible solution of I throughout. Z (I) for I is the complexity index introduced by Kimura and Makino (Discrete Applied Mathematics 200:67–78, 2016), which is defined by the sign pattern of the input matrix. We analyze the complexity of the reconfiguration problem of integer linear systems based on the complexity index Z (I) of given I. We then show that the problem is (i) solvable in constant time if Z (I) is less than one, (ii) weakly coNP-complete and pseudo-polynomially solvable if Z (I) is exactly one, and (iii) PSPACE-complete if Z (I) is greater than one. Since the complexity indices of Horn and two-variable-par-inequality integer linear systems are at most one, our results imply that the reconfiguration of these systems are in coNP and pseudo-polynomially solvable. Moreover, this is the first result that reveals coNP-completeness for a reconfiguration problem, to the best of our knowledge. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we consider a logic circuit (i.e., a combinatorial circuit consisting of gates, each of which computes a Boolean function) computing a symmetric Boolean function , and investigate a relationship between two complexity measures, energy and fan-in of , where the energy is the maximum number of gates outputting “1” over all inputs to , and the fan-in is the maximum number of inputs of every gate in . We first prove that any symmetric Boolean function of variables can be computed by a logic circuit of energy and fan-in , and then provide an almost tight lower bound where is the maximum numbers of consecutive “0”s or “1”s in the value vector of . Our results imply that there exists a tradeoff between the energy and fan-in of logic circuits computing a symmetric Boolean function. [Copyright &y& Elsevier]

Given a k -coloring of a graph G , a Kempe-change for two colors a and b produces another k -coloring of G , as follows: first choose a connected component in the subgraph of G induced by the two color classes of a and b , and then swap the colors a and b in the component. Two k -colorings are called Kempe-equivalent if one can be transformed into the other by a sequence of Kempe-changes. We consider two problems, defined as follows: First, given two k -colorings of a graph G , Kempe Reachability asks whether they are Kempe-equivalent; and second, given a graph G and a positive integer k , Kempe Connectivity asks whether any two k -colorings of G are Kempe-equivalent. We analyze the complexity of these problems from the viewpoint of graph classes. We prove that Kempe Reachability is PSPACE -complete for any fixed k ≥ 3 , and that it remains PSPACE -complete even when restricted to three colors and planar graphs of maximum degree six. Furthermore, we show that both problems admit polynomial-time algorithms on chordal graphs, bipartite graphs, and cographs. For each of these graph classes, we give a non-trivial upper bound on the number of Kempe-changes needed in order to certify that two k -colorings are Kempe-equivalent. [ABSTRACT FROM AUTHOR]

Subgraph reconfiguration is a family of problems focusing on the reachability of the solution space in which feasible solutions are subgraphs, represented either as sets of vertices or sets of edges, satisfying a prescribed graph structure property. Although there has been previous work that can be categorized as subgraph reconfiguration , most of the related results appear under the name of the property under consideration; for example, independent set, clique, and matching. In this paper, we systematically clarify the complexity status of subgraph reconfiguration with respect to graph structure properties. [ABSTRACT FROM AUTHOR]

We study the complexity of deciding whether for two given feedback vertex sets of a graph there is a step-by-step transformation between them, such that for each feedback vertex set in the transformation, the next one is obtained by exchanging a single vertex. We give a classification of the complexity of this question for planar graphs in terms of the maximum degree. We show that for planar graphs of maximum degree at most three the problem is tractable because there always exists a transformation, while it is PSPACE -complete when the maximum degree is at most four. The positive side of the classification extends to K 3 , 3 -minor-free graphs of maximum degree three. We then consider the Matroid Parity problem, which generalizes feedback vertex sets in graphs of maximum degree three as well as matchings and spanning trees in general graphs. Generalizing known results for the latter two we show that there always exists a transformation between any two non-maximum independent parity sets. [ABSTRACT FROM AUTHOR]

Various forms of sorting problems have been studied over the years. Recently, two kinds of sorting puzzle apps have gained popularity. In these puzzles, we are given a set of bins filled with colored units, balls or water, and some empty bins. These puzzles allow us to move colored units from a bin to another when the colors involved match in some way or the target bin is empty. The goal of these puzzles is to sort all the color units in order. We investigate computational complexities of these puzzles. We first show that these two puzzles are essentially the same from the viewpoint of solvability. That is, an instance is sortable by ball-moves if and only if it is sortable by water-moves. We also show that every yes-instance has a solution of polynomial length, which implies that these puzzles belong to NP. We then show that these puzzles are NP-complete. For some special cases, we give polynomial-time algorithms. We finally consider the number of empty bins sufficient for making all instances solvable and give non-trivial upper and lower bounds in terms of the number of filled bins and the capacity of bins. [ABSTRACT FROM AUTHOR]

Non-deterministic constraint logic (NCL) is a simple model of computation based on orientations of a constraint graph with edge weights and vertex demands. NCL captures PSPACE and has been a useful tool for proving algorithmic hardness of many puzzles, games, and reconfiguration problems. In particular, its usefulness stems from the fact that it remains PSPACE -complete even under severe restrictions of the weights (e.g., only edge-weights one and two are needed) and the structure of the constraint graph (e.g., planar and/or graphs of bounded bandwidth). While such restrictions on the structure of constraint graphs do not seem to limit the expressiveness of NCL , the building blocks of the constraint graphs cannot be limited without losing expressiveness: We consider as parameters the number of weight-one edges and the number of weight-two edges of a constraint graph, as well as the number of and or or vertices of an and/or constraint graph. We show that NCL is fixed-parameter tractable (FPT) for any of these parameters. In particular, for NCL parameterized by the number of weight-one edges or the number of and vertices, we obtain a linear kernel. It follows that, in a sense, NCL as introduced by Hearn and Demaine is defined in the most economical way for the purpose of capturing PSPACE. [ABSTRACT FROM AUTHOR]

Suppose that we are given two dominating sets D s and D t of a graph G whose cardinalities are at most a given threshold k . Then, we are asked whether there exists a sequence of dominating sets of G between D s and D t such that each dominating set in the sequence is of cardinality at most k and can be obtained from the previous one by either adding or deleting exactly one vertex. This decision problem is known to be PSPACE-complete in general. In this paper, we study the complexity of this problem from the viewpoint of graph classes. We first prove that the problem remains PSPACE-complete even for planar graphs, bounded bandwidth graphs, split graphs, and bipartite graphs. We then give a general scheme to construct linear-time algorithms and show that the problem can be solved in linear time for cographs, forests, and interval graphs. Furthermore, for these tractable cases, we can obtain a desired sequence if it exists such that the number of additions and deletions is bounded by O ( n ) , where n is the number of vertices in the input graph. [ABSTRACT FROM AUTHOR]

Consider a puzzle consisting of n tokens on an n -vertex graph, where each token has a distinct starting vertex and a distinct target vertex it wants to reach, and the only allowed transformation is to swap the tokens on adjacent vertices. We prove that every such puzzle is solvable in O ( n 2 ) token swaps, and thus focus on the problem of minimizing the number of token swaps to reach the target token placement. We give a polynomial-time 2-approximation algorithm for trees, and using this, obtain a polynomial-time 2 α -approximation algorithm for graphs whose tree α -spanners can be computed in polynomial time. Finally, we show that the problem can be solved exactly in polynomial time on complete bipartite graphs. [ABSTRACT FROM AUTHOR]