Search Results

Documents authored by Iwata, Yoichi

Document
DOI: 10.4230/LIPIcs.IPEC.2019.22
Improved Analysis of Highest-Degree Branching for Feedback Vertex Set

Authors: Yoichi Iwata and Yusuke Kobayashi

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Abstract
Recent empirical evaluations of exact algorithms for Feedback Vertex Set have demonstrated the efficiency of a highest-degree branching algorithm with a degree-based pruning heuristic. In this paper, we prove that this empirically fast algorithm runs in O(3.460^k n) time, where k is the solution size. This improves the previous best O(3.619^k n)-time deterministic algorithm obtained by Kociumaka and Pilipczuk (Inf. Process. Lett., 2014).
Cite as

Yoichi Iwata and Yusuke Kobayashi. Improved Analysis of Highest-Degree Branching for Feedback Vertex Set. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 22:1-22:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{iwata_et_al:LIPIcs.IPEC.2019.22,
  author =	{Iwata, Yoichi and Kobayashi, Yusuke},
  title =	{{Improved Analysis of Highest-Degree Branching for Feedback Vertex Set}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{22:1--22:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.22},
  URN =		{urn:nbn:de:0030-drops-114833},
  doi =		{10.4230/LIPIcs.IPEC.2019.22},
  annote =	{Keywords: Feedback Vertex Set, Branch and bound, Measure and conquer}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.23
Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP

Authors: Édouard Bonnet, Yoichi Iwata, Bart M. P. Jansen, and Łukasz Kowalik

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
The Traveling Salesman Problem asks to find a minimum-weight Hamiltonian cycle in an edge-weighted complete graph. Local search is a widely-employed strategy for finding good solutions to TSP. A popular neighborhood operator for local search is k-opt, which turns a Hamiltonian cycle C into a new Hamiltonian cycle C' by replacing k edges. We analyze the problem of determining whether the weight of a given cycle can be decreased by a k-opt move. Earlier work has shown that (i) assuming the Exponential Time Hypothesis, there is no algorithm that can detect whether or not a given Hamiltonian cycle C in an n-vertex input can be improved by a k-opt move in time f(k) n^o(k / log k) for any function f, while (ii) it is possible to improve on the brute-force running time of O(n^k) and save linear factors in the exponent. Modern TSP heuristics are very successful at identifying the most promising edges to be used in k-opt moves, and experiments show that very good global solutions can already be reached using only the top-O(1) most promising edges incident to each vertex. This leads to the following question: can improving k-opt moves be found efficiently in graphs of bounded degree? We answer this question in various regimes, presenting new algorithms and conditional lower bounds. We show that the aforementioned ETH lower bound also holds for graphs of maximum degree three, but that in bounded-degree graphs the best improving k-move can be found in time O(n^((23/135+epsilon_k)k)), where lim_{k -> infty} epsilon_k = 0. This improves upon the best-known bounds for general graphs. Due to its practical importance, we devote special attention to the range of k in which improving k-moves in bounded-degree graphs can be found in quasi-linear time. For k <= 7, we give quasi-linear time algorithms for general weights. For k=8 we obtain a quasi-linear time algorithm when the weights are bounded by O(polylog n). On the other hand, based on established fine-grained complexity hypotheses about the impossibility of detecting a triangle in edge-linear time, we prove that the k = 9 case does not admit quasi-linear time algorithms. Hence we fully characterize the values of k for which quasi-linear time algorithms exist for polylogarithmic weights on bounded-degree graphs.
Cite as

Édouard Bonnet, Yoichi Iwata, Bart M. P. Jansen, and Łukasz Kowalik. Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.ESA.2019.23,
  author =	{Bonnet, \'{E}douard and Iwata, Yoichi and Jansen, Bart M. P. and Kowalik, {\L}ukasz},
  title =	{{Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.23},
  URN =		{urn:nbn:de:0030-drops-111444},
  doi =		{10.4230/LIPIcs.ESA.2019.23},
  annote =	{Keywords: traveling salesman problem, k-OPT, bounded degree}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.41
On the Power of Tree-Depth for Fully Polynomial FPT Algorithms

Authors: Yoichi Iwata, Tomoaki Ogasawara, and Naoto Ohsaka

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
There are many classical problems in P whose time complexities have not been improved over the past decades. Recent studies of "Hardness in P" have revealed that, for several of such problems, the current fastest algorithm is the best possible under some complexity assumptions. To bypass this difficulty, the concept of "FPT inside P" has been introduced. For a problem with the current best time complexity O(n^c), the goal is to design an algorithm running in k^{O(1)}n^{c'} time for a parameter k and a constant c'<c. In this paper, we investigate the complexity of graph problems in P parameterized by tree-depth, a graph parameter related to tree-width. We show that a simple divide-and-conquer method can solve many graph problems, including Weighted Matching, Negative Cycle Detection, Minimum Weight Cycle, Replacement Paths, and 2-hop Cover, in O(td m) time or O(td (m+nlog n)) time, where td is the tree-depth of the input graph. Because any graph of tree-width tw has tree-depth at most (tw+1)log_2 n, our algorithms also run in O(tw mlog n) time or O(tw (m+nlog n)log n) time. These results match or improve the previous best algorithms parameterized by tree-width. Especially, we solve an open problem of fully polynomial FPT algorithm for Weighted Matching parameterized by tree-width posed by Fomin et al. (SODA 2017).
Cite as

Yoichi Iwata, Tomoaki Ogasawara, and Naoto Ohsaka. On the Power of Tree-Depth for Fully Polynomial FPT Algorithms. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 41:1-41:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{iwata_et_al:LIPIcs.STACS.2018.41,
  author =	{Iwata, Yoichi and Ogasawara, Tomoaki and Ohsaka, Naoto},
  title =	{{On the Power of Tree-Depth for Fully Polynomial FPT Algorithms}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{41:1--41:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.41},
  URN =		{urn:nbn:de:0030-drops-85255},
  doi =		{10.4230/LIPIcs.STACS.2018.41},
  annote =	{Keywords: Fully Polynomial FPT Algorithm, Tree-Depth, Divide-and-Conquer}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.68
Linear-Time Kernelization for Feedback Vertex Set

Authors: Yoichi Iwata

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
In this paper, we give an algorithm that, given an undirected graph G of m edges and an integer k, computes a graph G' and an integer k' in O(k^4 m) time such that (1) the size of the graph G' is O(k^2), (2) k' \leq k, and (3) G has a feedback vertex set of size at most k if and only if G' has a feedback vertex set of size at most k'. This is the first linear-time polynomial-size kernel for Feedback Vertex Set. The size of our kernel is 2k^2+k vertices and 4k^2 edges, which is smaller than the previous best of 4k^2 vertices and 8k^2 edges. Thus, we improve the size and the running time simultaneously. We note that under the assumption of NP \not\subseteq coNP/poly, Feedback Vertex Set does not admit an O(k^{2-\epsilon})-size kernel for any \epsilon>0. Our kernel exploits k-submodular relaxation, which is a recently developed technique for obtaining efficient FPT algorithms for various problems. The dual of k-submodular relaxation of Feedback Vertex Set can be seen as a half-integral variant of A-path packing, and to obtain the linear-time complexity, we give an efficient augmenting-path algorithm for this problem. We believe that this combinatorial algorithm is of independent interest. A solver based on the proposed method won first place in the 1st Parameterized Algorithms and Computational Experiments (PACE) challenge.
Cite as

Yoichi Iwata. Linear-Time Kernelization for Feedback Vertex Set. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 68:1-68:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{iwata:LIPIcs.ICALP.2017.68,
  author =	{Iwata, Yoichi},
  title =	{{Linear-Time Kernelization for Feedback Vertex Set}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{68:1--68:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.68},
  URN =		{urn:nbn:de:0030-drops-74301},
  doi =		{10.4230/LIPIcs.ICALP.2017.68},
  annote =	{Keywords: FPT Algorithms, Kernelization, Path Packing, Half-integrality}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.127
Exact and Approximation Algorithms for the Maximum Constraint Satisfaction Problem over the Point Algebra

Authors: Yoichi Iwata and Yuichi Yoshida

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
We study the constraint satisfaction problem over the point algebra. In this problem, an instance consists of a set of variables and a set of binary constraints of forms (x < y), (x <= y), (x \neq y) or (x = y). Then, the objective is to assign integers to variables so as to satisfy as many constraints as possible.This problem contains many important problems such as Correlation Clustering, Maximum Acyclic Subgraph, and Feedback Arc Set. We first give an exact algorithm that runs in O^*(3^{\frac{log 5}{log 6}n}) time, which improves the previous best O^*(3^n) obtained by a standard dynamic programming. Our algorithm combines the dynamic programming with the split-and-list technique. The split-and-list technique involves matrix products and we make use of sparsity of matrices to speed up the computation. As for approximation, we give a 0.4586-approximation algorithm when the objective is maximizing the number of satisfied constraints, and give an O(log n log log n)-approximation algorithm when the objective is minimizing the number of unsatisfied constraints.
Cite as

Yoichi Iwata and Yuichi Yoshida. Exact and Approximation Algorithms for the Maximum Constraint Satisfaction Problem over the Point Algebra. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 127-138, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{iwata_et_al:LIPIcs.STACS.2013.127,
  author =	{Iwata, Yoichi and Yoshida, Yuichi},
  title =	{{Exact and Approximation Algorithms for the Maximum Constraint Satisfaction Problem over the Point Algebra}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{127--138},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha 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.2013.127},
  URN =		{urn:nbn:de:0030-drops-39282},
  doi =		{10.4230/LIPIcs.STACS.2013.127},
  annote =	{Keywords: Constraint Satisfaction Problems, Point Algebra, Exact Algorithms, Approximation Algorithms}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact