| 1. |
Algorithms for coloring reconfiguration under recolorability digraphs. |
| 2. |
Quantaloidal approach to constraint satisfaction. |
| 3. |
Trichotomy for the Reconfiguration Problem of Integer Linear Systems.
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 $oldsymbol{s}$ and $oldsymbol{t}$ of $I$, and then asked
to transform $oldsymbol{s}$ to $oldsymbol{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.. |
| 4. |
NP-Completeness of Fill-a-Pix and Sigma(P)(2)-Completeness of Its Fewest Clues Problem. |
| 5. |
A Fast Algorithm for Unbounded Monotone Integer Linear Systems with Two Variables per Inequality via Graph Decomposition.. |
| 6. |
Linear Satisfiability Preserving Assignments (Extended Abstract).. |
| 7. |
The Fewest Clues Problem of Picross 3D.. |
| 8. |
Toshihiro Fujito, Kei Kimura, Yuki Mizuno, Approximating Partially Bounded Degree Deletion on Directed Graphs, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 10.1007/978-3-319-75172-6_4, 10755, 32-43, 2018.03, The Bounded Degree Deletion problem (BDD) is that of computing a minimum vertex set in a graph G=(V,E) with degree bound b: V=Z+, such that, when it is removed from G, the degree of any remaining vertex v is no larger than b(v). It is a classic problem in graph theory and various results have been obtained including an approximation ratio of 2+In bmax [30], where bmax is the maximum degree bound. This paper considers BDD on directed graphs containing unbounded vertices, which we call Partially Bounded Degree Deletion (PBDD). Despite such a natural generalization of standard BDD, it appears that PBDD has never been studied and no algorithmic results are known, approximation or parameterized. It will be shown that (1) in case all the possible degrees are bounded, in-degrees by and out-degrees by, BDD on directed graphs can be approximated within, and (2) although it becomes NP-hard to approximate PBDD better than bmax (even on undirected graphs) once unbounded vertices are allowed, it can be within when only in-degrees (and none of out-degrees) are partially bounded by b.. |
| 9. |
Kei Kimura, Kazuhisa Makino, Autark assignments of Horn CNFs, Japan Journal of Industrial and Applied Mathematics, 10.1007/s13160-017-0284-6, 35, 1, 297-309, 2018.03, In this paper, we consider autark and linear autark assignments of Horn CNFs. We first study maximal autark assignments of Horn CNFs and devise a linear time algorithm of computing these assignments. This complements the previous work by Marek which reveals the properties of minimal autark assignments of Horn CNFs. We then consider linear autark assignments of Horn CNFs and give a combinatorial characterization of the existence of such an assignment. By making use of this characterization, we devise a linear time algorithm of finding linear autark assignments of Horn CNFs.. |
| 10. |
Yasushi Kawase, Kei Kimura, Kazuhisa Makino, Hanna Sumita, Optimal matroid partitioning problems, Leibniz International Proceedings in Informatics, LIPIcs, 10.4230/LIPIcs.ISAAC.2017.51, 92, 51:1-51:13, 2017.12, This paper studies optimal matroid partitioning problems for various objective functions. Inthe problem, we are given a finite set E and k weighted matroids (E, Ii,wi), i = 1, . . . , k, andour task is to find a minimum partition (I1, . . . , Ik) of E such that Ii 2 Ii for all i. For eachobjective function, we give a polynomial-Time algorithm or prove NP-hardness. In particular, forthe case when the given weighted matroids are identical and the objective function is the sum ofthe maximum weight in each set (i.e.,Pk i=1 maxe2Ii wi(e)), we show that the problem is strongly NP-hard but admits a PTAS.. |
| 11. |
Optimal Matroid Partitioning Problems. |
| 12. |
Kei Kimura, Kazuhisa Makino, Trichotomy for integer linear systems based on their sign patterns, DISCRETE APPLIED MATHEMATICS, 10.1016/j.dam.2015.07.004, 200, 67-78, 2016.02, In this paper, we consider solving the integer linear systems, i.e., given a matrix A is an element of R-mxn a vector b is an element of R-m, and a positive integer d, to compute an integer vector x is an element of D-n such that Ax >= b or to determine the infeasibility of the system, where m and n denote positive integers, R denotes the set of reals, and D = {0, 1, ...,d-1). The problem is one of the most fundamental NP-hard problems in computer science.
For the problem, we propose a complexity index eta which depends only on the sign pattern of A. For a real gamma, let ILS(gamma) denote the family of the problem instances I with eta(I) = gamma. We then show the following trichotomy:
ILS(gamma) is solvable in linear time, if gamma ILS(gamma) is weakly NP-hard and pseudo-polynomially solvable, if gamma = 1,
ILS(gamma) is strongly NP-hard, if gamma > 1.
This, for example, includes the previous results that Horn systems and two-variable-perinequality (TVPI) systems can be solved in pseudo-polynomial time. (C) 2015 Elsevier B.V. All rights reserved.. |
| 13. |
Norie Fu, Vorapong Suppakitpaisarn, Kei Kimura, Naonori Kakimura, Maximum Lifetime Coverage Problems with Battery Recovery Effects, 2014 IEEE GLOBAL COMMUNICATIONS CONFERENCE (GLOBECOM 2014), 10.1109/GLOCOM.2014.7036794, 118-124, 2014.12, Scheduling sensors to prolong the lifetime of covering targets in the field is one of the central problems in wireless sensor networks. This problem, called the maximum lifetime coverage problem (MLCP), can be formulated as a linear programming problem with exponential size, and has a constant-factor approximation algorithm. In reality, however, batteries of sensors have recovery effects, which is a phenomenon that the deliverable energy in batteries can be replenished by itself if it is left idling for sufficient duration. Thanks to that effects, we can obtain much longer lifetime of sensors if each sensor is forced to take a sleep at some interval. In this paper, we introduce two models that extend the MLCP, incorporating battery recovery effects. The first model represents battery recovery effects in a deterministic way, while the second one uses a probabilistic model to imitate the effects. We then propose efficient algorithms that work for both models by extending approximation algorithms for the original MLCP. Numerical experiments show that the lifetime of our schedule is 10-40% longer than one without battery recovery effects.. |
| 14. |
Satisfiability Preserving Assignments and Their Local and Linear Forms. |
| 15. |
Kei Kimura, Kazuhisa Makino, Trichotomy for Integer Linear Systems Based on Their Sign Patterns, 29TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, (STACS 2012), 10.4230/LIPIcs.STACS.2012.613, 14, 613-623, 2012.03, In this paper, we consider solving the integer linear systems, i.e., given a matrix A is an element of R-mxn, a vector b is an element of R-m, and a positive integer d, to compute an integer vector x is an element of D-n such that Ax >= b, where m and n denote positive integers, R denotes the set of reals, and D = {0, 1,..., d - 1}. The problem is one of the most fundamental NP-hard problems in computer science.
For the problem, we propose a complexity index eta which is based only on the sign pattern of A. For a real gamma, let ILS=(gamma) denote the family of the problem instances I with eta(I) = gamma. We then show the following trichotomy:
ILS=(gamma) is linearly solvable, if gamma ILS=(gamma) is weakly NP-hard and pseudo-polynomially solvable, if gamma = 1, and
ILS=(gamma) is strongly NP-hard, if gamma > 1.
This, for example, includes the existing results that quadratic systems and Horn systems can be solved in pseudo-polynomial time.. |
| 16. |
Trichotomy for Integer Linear Systems Based on Their Sign Patterns. |
