Search Results

Documents authored by Tamaki, Hisao

Document
DOI: 10.4230/LIPIcs.IPEC.2023.34
A Contraction-Recursive Algorithm for Treewidth

Authors: Hisao Tamaki

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract
Let tw(G) denote the treewidth of graph G. Given a graph G and a positive integer k such that tw(G) ≤ k + 1, we are to decide if tw(G) ≤ k. We give a certifying algorithm RTW ("R" for recursive) for this task: it returns one or more tree-decompositions of G of width ≤ k if the answer is YES and a minimal contraction H of G such that tw(H) > k otherwise. Starting from a greedy upper bound on tw(G) and repeatedly improving the upper bound by this algorithm, we obtain tw(G) with certificates. RTW uses a heuristic variant of Tamaki’s PID algorithm for treewidth (ESA2017), which we call HPID. Informally speaking, PID builds potential subtrees of tree-decompositions of width ≤ k in a bottom up manner, until such a tree-decomposition is constructed or the set of potential subtrees is exhausted without success. HPID uses the same method of generating a new subtree from existing ones but with a different generation order which is not intended for exhaustion but for quick generation of a full tree-decomposition when possible. RTW, given G and k, interleaves the execution of HPID with recursive calls on G /e for edges e of G, where G / e denotes the graph obtained from G by contracting edge e. If we find that tw(G / e) > k, then we have tw(G) > k with the same certificate. If we find that tw(G / e) ≤ k, we "uncontract" the bags of the certifying tree-decompositions of G / e into bags of G and feed them to HPID to help progress. If the question is not resolved after the recursive calls are made for all edges, we finish HPID in an exhaustive mode. If it turns out that tw(G) > k, then G is a certificate for tw(G') > k for every G' of which G is a contraction, because we have found tw(G / e) ≤ k for every edge e of G. This final round of HPID guarantees the correctness of the algorithm, while its practical efficiency derives from our methods of "uncontracting" bags of tree-decompositions of G / e to useful bags of G, as well as of exploiting those bags in HPID. Experiments show that our algorithm drastically extends the scope of practically solvable instances. In particular, when applied to the 100 instances in the PACE 2017 bonus set, the number of instances solved by our implementation on a typical laptop, with the timeout of 100, 1000, and 10000 seconds per instance, are 72, 92, and 98 respectively, while these numbers are 11, 38, and 68 for Tamaki’s PID solver and 65, 82, and 85 for his new solver (SEA 2022).
Cite as

Hisao Tamaki. A Contraction-Recursive Algorithm for Treewidth. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{tamaki:LIPIcs.IPEC.2023.34,
  author =	{Tamaki, Hisao},
  title =	{{A Contraction-Recursive Algorithm for Treewidth}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{34:1--34:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.34},
  URN =		{urn:nbn:de:0030-drops-194536},
  doi =		{10.4230/LIPIcs.IPEC.2023.34},
  annote =	{Keywords: graph algorithm, treewidth, exact computation, BT dynamic programming, contraction, certifying algorithms}
}
Document
DOI: 10.4230/LIPIcs.SEA.2022.17
Heuristic Computation of Exact Treewidth

Authors: Hisao Tamaki

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)

Abstract
We are interested in computing the treewidth tw(G) of a given graph G. Our approach is to design heuristic algorithms for computing a sequence of improving upper bounds and a sequence of improving lower bounds, which would hopefully converge to tw(G) from both sides. The upper bound algorithm extends and simplifies the present author’s unpublished work on a heuristic use of the dynamic programming algorithm for deciding treewidth due to Bouchitté and Todinca. The lower bound algorithm is based on the well-known fact that, for every minor H of G, we have tw(H) ≤ tw(G). Starting from a greedily computed minor H_0 of G, the algorithm tries to construct a sequence of minors H_0, H_1, ..., H_k with tw(H_i) < tw(H_{i + 1}) for 0 ≤ i < k and hopefully tw(H_k) = tw(G). We have implemented a treewidth solver based on this approach and have evaluated it on the bonus instances from the exact treewidth track of PACE 2017 algorithm implementation challenge. The results show that our approach is extremely effective in tackling instances that are hard for conventional solvers. Our solver has an additional advantage over conventional ones in that it attaches a compact certificate to the lower bound it computes.
Cite as

Hisao Tamaki. Heuristic Computation of Exact Treewidth. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{tamaki:LIPIcs.SEA.2022.17,
  author =	{Tamaki, Hisao},
  title =	{{Heuristic Computation of Exact Treewidth}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{17:1--17:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.17},
  URN =		{urn:nbn:de:0030-drops-165512},
  doi =		{10.4230/LIPIcs.SEA.2022.17},
  annote =	{Keywords: graph algorithm, treewidth, heuristics, BT dynamic programming, contraction, obstruction, minimal forbidden minor, certifying algorithms}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2017.25
An Improved Fixed-Parameter Algorithm for One-Page Crossing Minimization

Authors: Yasuaki Kobayashi, Hiromu Ohtsuka, and Hisao Tamaki

Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Abstract
Book embedding is one of the most well-known graph drawing models and is extensively studied in the literature. The special case where the number of pages is one is of particular interest: an embedding in this case has a natural circular representation useful for visualization and graphs that can be embedded in one page without crossings form an important graph class, namely that of outerplanar graphs. In this paper, we consider the problem of minimizing the number of crossings in a one-page book embedding, which we call one-page crossing minimization. Here, we are given a graph G with n vertices together with a non-negative integer k and are asked whether G can be embedded into a single page with at most k crossings. Bannister and Eppstein (GD 2014) showed that this problem is fixed-parameter tractable. Their algorithm is derived through the application of Courcelle's theorem (on graph properties definable in the monadic second-order logic of graphs) and runs in f(L)n time, where L = 2^{O(k^2)} is the length of the formula defining the property that the one-page crossing number is at most k and f is a computable function without any known upper bound expressible as an elementary function. We give an explicit dynamic programming algorithm with a drastically improved running time of 2^{O(k log k)}n.
Cite as

Yasuaki Kobayashi, Hiromu Ohtsuka, and Hisao Tamaki. An Improved Fixed-Parameter Algorithm for One-Page Crossing Minimization. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 25:1-25:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kobayashi_et_al:LIPIcs.IPEC.2017.25,
  author =	{Kobayashi, Yasuaki and Ohtsuka, Hiromu and Tamaki, Hisao},
  title =	{{An Improved Fixed-Parameter Algorithm for One-Page Crossing Minimization}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{25:1--25:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Lokshtanov, Daniel and Nishimura, Naomi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.25},
  URN =		{urn:nbn:de:0030-drops-85661},
  doi =		{10.4230/LIPIcs.IPEC.2017.25},
  annote =	{Keywords: Book Embedding, Fixed-Parameter Tractability, Graph Drawing, Treewidth}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.68
Positive-Instance Driven Dynamic Programming for Treewidth

Authors: Hisao Tamaki

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
Consider a dynamic programming scheme for a decision problem in which all subproblems involved are also decision problems. An implementation of such a scheme is positive-instance driven (PID), if it generates positive subproblem instances, but not negative ones, building each on smaller positive instances. We take the dynamic programming scheme due to Bouchitté and Todinca for treewidth computation, which is based on minimal separators and potential maximal cliques, and design a variant (for the decision version of the problem) with a natural PID implementation. The resulting algorithm performs extremely well: it solves a number of standard benchmark instances for which the optimal solutions have not previously been known. Incorporating a new heuristic algorithm for detecting safe separators, it also solves all of the 100 public instances posed by the exact treewidth track in PACE 2017, a competition on algorithm implementation. We describe the algorithm and prove its correctness. We also perform an experimental analysis counting combinatorial structures involved, which gives insights into the advantage of our approach over more conventional approaches and points to the future direction of theoretical and engineering research on treewidth computation.
Cite as

Hisao Tamaki. Positive-Instance Driven Dynamic Programming for Treewidth. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 68:1-68:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{tamaki:LIPIcs.ESA.2017.68,
  author =	{Tamaki, Hisao},
  title =	{{Positive-Instance Driven Dynamic Programming for Treewidth}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{68:1--68:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.68},
  URN =		{urn:nbn:de:0030-drops-78804},
  doi =		{10.4230/LIPIcs.ESA.2017.68},
  annote =	{Keywords: treewidth, dynamic programming, minimal separators, potential maximal cliques, positive instances}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2016.18
Treedepth Parameterized by Vertex Cover Number

Authors: Yasuaki Kobayashi and Hisao Tamaki

Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)

Abstract
To solve hard graph problems from the parameterized perspective, structural parameters have commonly been used. In particular, vertex cover number is frequently used in this context. In this paper, we study the problem of computing the treedepth of a given graph G. We show that there are an O(tau(G)^3) vertex kernel and an O(4^{tau(G)}*tau(G)*n) time fixed-parameter algorithm for this problem, where tau(G) is the size of a minimum vertex cover of G and n is the number of vertices of G.
Cite as

Yasuaki Kobayashi and Hisao Tamaki. Treedepth Parameterized by Vertex Cover Number. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 18:1-18:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kobayashi_et_al:LIPIcs.IPEC.2016.18,
  author =	{Kobayashi, Yasuaki and Tamaki, Hisao},
  title =	{{Treedepth Parameterized by Vertex Cover Number}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{18:1--18:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.18},
  URN =		{urn:nbn:de:0030-drops-69438},
  doi =		{10.4230/LIPIcs.IPEC.2016.18},
  annote =	{Keywords: Fixed-parameter algorithm, Polynomial kernelization, Structural parameterization, Treedepth, Vertex cover}
}
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