Document

**Published in:** LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Linear programming (LP) problems with gainfree Leontief substitution systems have been intensively studied in economics and operations research, and include the feasibility problem of a class of Horn systems, which arises in, e.g., polyhedral combinatorics and logic. This subclass of LP problems admits a strongly polynomial time algorithm, where devising such an algorithm for general LP problems is one of the major theoretical open questions in mathematical optimization and computer science. Recently, much attention has been paid to devising certifying algorithms in software engineering, since those algorithms enable one to confirm the correctness of outputs of programs with simple computations. Devising a combinatorial certifying algorithm for the feasibility of the fundamental class of Horn systems remains open for almost a decade. In this paper, we provide the first combinatorial (and strongly polynomial time) certifying algorithm for LP problems with gainfree Leontief substitution systems. As a by-product, we resolve the open question on the feasibility of the class of Horn systems.

Kei Kimura and Kazuhisa Makino. A Combinatorial Certifying Algorithm for Linear Programming Problems with Gainfree Leontief Substitution Systems. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 47:1-47:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kimura_et_al:LIPIcs.ISAAC.2023.47, author = {Kimura, Kei and Makino, Kazuhisa}, title = {{A Combinatorial Certifying Algorithm for Linear Programming Problems with Gainfree Leontief Substitution Systems}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {47:1--47:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.47}, URN = {urn:nbn:de:0030-drops-193492}, doi = {10.4230/LIPIcs.ISAAC.2023.47}, annote = {Keywords: linear programming problem, certifying algorithm, Horn system} }

Document

**Published in:** LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

In the k-Recoloring problem, we are given two (vertex-)colorings of a graph using k colors, and asked to transform one into the other by recoloring only one vertex at a time, while at all times maintaining a proper k-coloring. This problem is known to be solvable in polynomial time if k ≤ 3, and is PSPACE-complete if k ≥ 4. In this paper, we consider a (directed) recolorability constraint on the k colors, which forbids some pairs of colors to be recolored directly. The recolorability constraint is given in terms of a digraph R, whose vertices correspond to the colors and whose arcs represent the pairs of colors that can be recolored directly. We provide algorithms for the problem based on the structure of recolorability constraints R, showing that the problem is solvable in linear time when R is a directed cycle or is in a class of multitrees.

Soichiro Fujii, Yuni Iwamasa, Kei Kimura, and Akira Suzuki. Algorithms for Coloring Reconfiguration Under Recolorability Digraphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fujii_et_al:LIPIcs.ISAAC.2022.4, author = {Fujii, Soichiro and Iwamasa, Yuni and Kimura, Kei and Suzuki, Akira}, title = {{Algorithms for Coloring Reconfiguration Under Recolorability Digraphs}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {4:1--4:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-258-7}, ISSN = {1868-8969}, year = {2022}, volume = {248}, editor = {Bae, Sang Won and Park, Heejin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.4}, URN = {urn:nbn:de:0030-drops-172896}, doi = {10.4230/LIPIcs.ISAAC.2022.4}, annote = {Keywords: combinatorial reconfiguration, graph coloring, recolorability, recoloring} }

Document

**Published in:** LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Picross 3D is a popular single-player puzzle video game for the Nintendo DS. It is a 3D variant of Nonogram, which is a popular pencil-and-paper puzzle. While Nonogram provides a rectangular grid of squares that must be filled in to create a picture, Picross 3D presents a rectangular parallelepiped (i.e., rectangular box) made of unit cubes, some of which must be removed to construct an image in three dimensions. Each row or column has at most one integer on it, and the integer indicates how many cubes in the corresponding 1D slice remain when the image is complete. It is shown by Kusano et al. that Picross 3D is NP-complete. We in this paper show that the fewest clues problem of Picross 3D is Sigma_2^P-complete and that the counting version and the another solution problem of Picross 3D are #P-complete and NP-complete, respectively.

Kei Kimura, Takuya Kamehashi, and Toshihiro Fujito. The Fewest Clues Problem of Picross 3D. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 25:1-25:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kimura_et_al:LIPIcs.FUN.2018.25, author = {Kimura, Kei and Kamehashi, Takuya and Fujito, Toshihiro}, title = {{The Fewest Clues Problem of Picross 3D}}, booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)}, pages = {25:1--25:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-067-5}, ISSN = {1868-8969}, year = {2018}, volume = {100}, editor = {Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.25}, URN = {urn:nbn:de:0030-drops-88168}, doi = {10.4230/LIPIcs.FUN.2018.25}, annote = {Keywords: Puzzle, computational complexity, fewest clues problem} }

Document

**Published in:** LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

This paper studies optimal matroid partitioning problems for various objective functions. In the problem, we are given a finite set E and k weighted matroids (E, \mathcal{I}_i, w_i), i = 1, \dots, k, and our task is to find a minimum partition (I_1,\dots,I_k) of E such that I_i \in \mathcal{I}_i for all i. For each objective function, we give a polynomial-time algorithm or prove NP-hardness. In particular, for the case when the given weighted matroids are identical and the objective function is the sum of the maximum weight in each set (i.e., \sum_{i=1}^k\max_{e\in I_i}w_i(e)), we show that the problem is strongly NP-hard but admits a PTAS.

Yasushi Kawase, Kei Kimura, Kazuhisa Makino, and Hanna Sumita. Optimal Matroid Partitioning Problems. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 51:1-51:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kawase_et_al:LIPIcs.ISAAC.2017.51, author = {Kawase, Yasushi and Kimura, Kei and Makino, Kazuhisa and Sumita, Hanna}, title = {{Optimal Matroid Partitioning Problems}}, booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)}, pages = {51:1--51:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-054-5}, ISSN = {1868-8969}, year = {2017}, volume = {92}, editor = {Okamoto, Yoshio and Tokuyama, Takeshi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.51}, URN = {urn:nbn:de:0030-drops-82712}, doi = {10.4230/LIPIcs.ISAAC.2017.51}, annote = {Keywords: Matroids, Partitioning problem, PTAS, NP-hardness} }

Document

**Published in:** LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

In this paper, we consider solving the integer linear systems, i.e.,
given a matrix A in R^{m*n}, a vector b in R^m, and a positive integer d, to compute an integer vector x in 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 h which is based only on the sign pattern of A. For a real r, let ILS_=(r) denote the family of the problem instances I with h(I)=r. We then show the following trichotomy:
- ILS_=(r) is linearly solvable, if r < 1,
- ILS_=(r) is weakly NP-hard and pseudo-polynomially solvable, if r = 1, and
- ILS_=(r) is strongly NP-hard, if r > 1.
This, for example, includes the existing results that quadratic systems and Horn systems can be solved in pseudo-polynomial time.

Kei Kimura and Kazuhisa Makino. Trichotomy for Integer Linear Systems Based on Their Sign Patterns. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 613-623, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{kimura_et_al:LIPIcs.STACS.2012.613, author = {Kimura, Kei and Makino, Kazuhisa}, title = {{Trichotomy for Integer Linear Systems Based on Their Sign Patterns}}, booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)}, pages = {613--623}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-35-4}, ISSN = {1868-8969}, year = {2012}, volume = {14}, editor = {D\"{u}rr, Christoph and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.613}, URN = {urn:nbn:de:0030-drops-34367}, doi = {10.4230/LIPIcs.STACS.2012.613}, annote = {Keywords: Integer linear system, Sign pattern, Complexity index, TVPI system, Horn system} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail