3 Search Results for "Mizutani, Yosuke"

Document
DOI: 10.4230/DagRep.13.8.1
Recent Trends in Graph Decomposition (Dagstuhl Seminar 23331)

Authors: George Karypis, Christian Schulz, Darren Strash, Deepak Ajwani, Rob H. Bisseling, Katrin Casel, Ümit V. Çatalyürek, Cédric Chevalier, Florian Chudigiewitsch, Marcelo Fonseca Faraj, Michael Fellows, Lars Gottesbüren, Tobias Heuer, Kamer Kaya, Jakub Lacki, Johannes Langguth, Xiaoye Sherry Li, Ruben Mayer, Johannes Meintrup, Yosuke Mizutani, François Pellegrini, Fabrizio Petrini, Frances Rosamond, Ilya Safro, Sebastian Schlag, Roohani Sharma, Blair D. Sullivan, Bora Uçar, and Albert-Jan Yzelman

Published in: Dagstuhl Reports, Volume 13, Issue 8 (2024)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 23331 "Recent Trends in Graph Decomposition", which took place from 13. August to 18. August, 2023. The seminar brought together 33 experts from academia and industry to discuss graph decomposition, a pivotal technique for handling massive graphs in applications such as social networks and scientific simulations. The seminar addressed the challenges posed by contemporary hardware designs, the potential of deep neural networks and reinforcement learning in developing heuristics, the unique optimization requirements of large sparse data, and the need for scalable algorithms suitable for emerging architectures. Through presentations, discussions, and collaborative sessions, the event fostered an exchange of innovative ideas, leading to the creation of community notes highlighting key open problems in the field.
Cite as

George Karypis, Christian Schulz, Darren Strash, Deepak Ajwani, Rob H. Bisseling, Katrin Casel, Ümit V. Çatalyürek, Cédric Chevalier, Florian Chudigiewitsch, Marcelo Fonseca Faraj, Michael Fellows, Lars Gottesbüren, Tobias Heuer, Kamer Kaya, Jakub Lacki, Johannes Langguth, Xiaoye Sherry Li, Ruben Mayer, Johannes Meintrup, Yosuke Mizutani, François Pellegrini, Fabrizio Petrini, Frances Rosamond, Ilya Safro, Sebastian Schlag, Roohani Sharma, Blair D. Sullivan, Bora Uçar, and Albert-Jan Yzelman. Recent Trends in Graph Decomposition (Dagstuhl Seminar 23331). In Dagstuhl Reports, Volume 13, Issue 8, pp. 1-45, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{karypis_et_al:DagRep.13.8.1,
  author =	{Karypis, George and Schulz, Christian and Strash, Darren and Ajwani, Deepak and Bisseling, Rob H. and Casel, Katrin and \c{C}ataly\"{u}rek, \"{U}mit V. and Chevalier, C\'{e}dric and Chudigiewitsch, Florian and Faraj, Marcelo Fonseca and Fellows, Michael and Gottesb\"{u}ren, Lars and Heuer, Tobias and Kaya, Kamer and Lacki, Jakub and Langguth, Johannes and Li, Xiaoye Sherry and Mayer, Ruben and Meintrup, Johannes and Mizutani, Yosuke and Pellegrini, Fran\c{c}ois and Petrini, Fabrizio and Rosamond, Frances and Safro, Ilya and Schlag, Sebastian and Sharma, Roohani and Sullivan, Blair D. and U\c{c}ar, Bora and Yzelman, Albert-Jan},
  title =	{{Recent Trends in Graph Decomposition (Dagstuhl Seminar 23331)}},
  pages =	{1--45},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{13},
  number =	{8},
  editor =	{Karypis, George and Schulz, Christian and Strash, Darren},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.8.1},
  URN =		{urn:nbn:de:0030-drops-198114},
  doi =		{10.4230/DagRep.13.8.1},
  annote =	{Keywords: combinatorial optimization, experimental algorithmics, parallel algorithms}
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2023.36
PACE Solver Description: Hydra Prime

Authors: Yosuke Mizutani, David Dursteler, and Blair D. Sullivan

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

Abstract
This note describes our submission to the 2023 PACE Challenge on the computation of twin-width. Our solver Hydra Prime combines modular decomposition with a collection of upper- and lower-bound algorithms, which are alternatingly applied on the prime graphs resulting from the modular decomposition. We introduce two novel approaches which contributed to the solver’s winning performance in the Exact Track: timeline encoding and hydra decomposition. Timeline encoding is a new data structure for computing the width of a given contraction sequence, enabling faster local search; the hydra decomposition is an iterative refinement strategy featuring a small vertex separator.
Cite as

Yosuke Mizutani, David Dursteler, and Blair D. Sullivan. PACE Solver Description: Hydra Prime. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 36:1-36:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{mizutani_et_al:LIPIcs.IPEC.2023.36,
  author =	{Mizutani, Yosuke and Dursteler, David and Sullivan, Blair D.},
  title =	{{PACE Solver Description: Hydra Prime}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{36:1--36:5},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.36},
  URN =		{urn:nbn:de:0030-drops-194552},
  doi =		{10.4230/LIPIcs.IPEC.2023.36},
  annote =	{Keywords: Twin-width, PACE 2023}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2022.23
Parameterized Complexity of Maximum Happy Set and Densest k-Subgraph

Authors: Yosuke Mizutani and Blair D. Sullivan

Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

Abstract
We present fixed-parameter tractable (FPT) algorithms for two problems, Maximum Happy Set (MaxHS) and Densest k-Subgraph (DkS) - also known as Maximum Edge Happy Set. Given a graph G and an integer k, MaxHS asks for a set S of k vertices such that the number of happy vertices with respect to S is maximized, where a vertex v is happy if v and all its neighbors are in S. We show that MaxHS can be solved in time 𝒪(2^mw ⋅ mw ⋅ k² ⋅ |V(G)|) and 𝒪(8^cw ⋅ k² ⋅ |V(G)|), where mw and cw denote the modular-width and the clique-width of G, respectively. This answers the open questions on fixed-parameter tractability posed in [Asahiro et al., 2021]. The DkS problem asks for a subgraph with k vertices maximizing the number of edges. If we define happy edges as the edges whose endpoints are in S, then DkS can be seen as an edge-variant of MaxHS. In this paper we show that DkS can be solved in time f(nd)⋅|V(G)|^𝒪(1) and 𝒪(2^{cd}⋅ k² ⋅ |V(G)|), where nd and cd denote the neighborhood diversity and the cluster deletion number of G, respectively, and f is some computable function. This result implies that DkS is also fixed-parameter tractable by twin cover number.
Cite as

Yosuke Mizutani and Blair D. Sullivan. Parameterized Complexity of Maximum Happy Set and Densest k-Subgraph. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{mizutani_et_al:LIPIcs.IPEC.2022.23,
  author =	{Mizutani, Yosuke and Sullivan, Blair D.},
  title =	{{Parameterized Complexity of Maximum Happy Set and Densest k-Subgraph}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{23:1--23:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.23},
  URN =		{urn:nbn:de:0030-drops-173795},
  doi =		{10.4230/LIPIcs.IPEC.2022.23},
  annote =	{Keywords: parameterized algorithms, maximum happy set, densest k-subgraph, modular-width, clique-width, neighborhood diversity, cluster deletion number, twin cover}
}
  • Refine by Author
  • 3 Mizutani, Yosuke
  • 3 Sullivan, Blair D.
  • 1 Ajwani, Deepak
  • 1 Bisseling, Rob H.
  • 1 Casel, Katrin
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Fixed parameter tractability

  • Refine by Keyword
  • 1 PACE 2023
  • 1 Twin-width
  • 1 clique-width
  • 1 cluster deletion number
  • 1 combinatorial optimization
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2022
  • 1 2023
  • 1 2024

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 Imprint Privacy Contact