3 Search Results for "Nishino, Masaaki"

Document
DOI: 10.4230/LIPIcs.SEA.2023.11
CompDP: A Framework for Simultaneous Subgraph Counting Under Connectivity Constraints

Authors: Kengo Nakamura, Masaaki Nishino, Norihito Yasuda, and Shin-ichi Minato

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

Abstract
The subgraph counting problem computes the number of subgraphs of a given graph that satisfy some constraints. Among various constraints imposed on a graph, those regarding the connectivity of vertices, such as "these two vertices must be connected," have great importance since they are indispensable for determining various graph substructures, e.g., paths, Steiner trees, and rooted spanning forests. In this view, the subgraph counting problem under connectivity constraints is also important because counting such substructures often corresponds to measuring the importance of a vertex in network infrastructures. However, we must solve the subgraph counting problems multiple times to compute such an importance measure for every vertex. Conventionally, they are solved separately by constructing decision diagrams such as BDD and ZDD for each problem. However, even solving a single subgraph counting is a computationally hard task, preventing us from solving it multiple times in a reasonable time. In this paper, we propose a dynamic programming framework that simultaneously counts subgraphs for every vertex by focusing on similar connectivity constraints. Experimental results show that the proposed method solved multiple subgraph counting problems about 10-20 times faster than the existing approach for many problem settings.
Cite as

Kengo Nakamura, Masaaki Nishino, Norihito Yasuda, and Shin-ichi Minato. CompDP: A Framework for Simultaneous Subgraph Counting Under Connectivity Constraints. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{nakamura_et_al:LIPIcs.SEA.2023.11,
  author =	{Nakamura, Kengo and Nishino, Masaaki and Yasuda, Norihito and Minato, Shin-ichi},
  title =	{{CompDP: A Framework for Simultaneous Subgraph Counting Under Connectivity Constraints}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{11:1--11:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.11},
  URN =		{urn:nbn:de:0030-drops-183613},
  doi =		{10.4230/LIPIcs.SEA.2023.11},
  annote =	{Keywords: Subgraph counting, Connectivity, Zero-suppressed Binary Decision Diagram}
}
Document
DOI: 10.4230/LIPIcs.SEA.2020.9
Enumerating All Subgraphs Under Given Constraints Using Zero-Suppressed Sentential Decision Diagrams

Authors: Yu Nakahata, Masaaki Nishino, Jun Kawahara, and Shin-ichi Minato

Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)

Abstract
Subgraph enumeration is a fundamental task in computer science. Since the number of subgraphs can be large, some enumeration algorithms exploit compressed representations for efficiency. One such representation is the Zero-suppressed Binary Decision Diagram (ZDD). ZDDs can represent the set of subgraphs compactly and support several poly-time queries, such as counting and random sampling. Researchers have proposed efficient algorithms to construct ZDDs representing the set of subgraphs under several constraints, which yield fruitful results in many applications. Recently, Zero-suppressed Sentential Decision Diagrams (ZSDDs) have been proposed as variants of ZDDs. ZSDDs can be smaller than ZDDs when representing the same set of subgraphs. However, efficient algorithms to construct ZSDDs are known only for specific types of subgraphs: matchings and paths. We propose a novel framework to construct ZSDDs representing sets of subgraphs under given constraints. Using our framework, we can construct ZSDDs representing several sets of subgraphs such as matchings, paths, cycles, and spanning trees. We show the bound of sizes of constructed ZSDDs by the branch-width of the input graph, which is smaller than that of ZDDs by the path-width. Experiments show that our methods can construct ZSDDs faster than ZDDs and that the constructed ZSDDs are smaller than ZDDs when representing the same set of subgraphs.
Cite as

Yu Nakahata, Masaaki Nishino, Jun Kawahara, and Shin-ichi Minato. Enumerating All Subgraphs Under Given Constraints Using Zero-Suppressed Sentential Decision Diagrams. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{nakahata_et_al:LIPIcs.SEA.2020.9,
  author =	{Nakahata, Yu and Nishino, Masaaki and Kawahara, Jun and Minato, Shin-ichi},
  title =	{{Enumerating All Subgraphs Under Given Constraints Using Zero-Suppressed Sentential Decision Diagrams}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Faro, Simone and Cantone, Domenico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.9},
  URN =		{urn:nbn:de:0030-drops-120831},
  doi =		{10.4230/LIPIcs.SEA.2020.9},
  annote =	{Keywords: Subgraph, Enumeration, Decision Diagram, Zero-suppressed Sentential Decision Diagram (ZSDD), Top-down construction algorithm}
}
Document
DOI: 10.4230/LIPIcs.SEA.2020.22
Variable Shift SDD: A More Succinct Sentential Decision Diagram

Authors: Kengo Nakamura, Shuhei Denzumi, and Masaaki Nishino

Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)

Abstract
The Sentential Decision Diagram (SDD) is a tractable representation of Boolean functions that subsumes the famous Ordered Binary Decision Diagram (OBDD) as a strict subset. SDDs are attracting much attention because they are more succinct than OBDDs, as well as having canonical forms and supporting many useful queries and transformations such as model counting and Apply operation. In this paper, we propose a more succinct variant of SDD named Variable Shift SDD (VS-SDD). The key idea is to create a unique representation for Boolean functions that are equivalent under a specific variable substitution. We show that VS-SDDs are never larger than SDDs and there are cases in which the size of a VS-SDD is exponentially smaller than that of an SDD. Moreover, despite such succinctness, we show that numerous basic operations that are supported in polytime with SDD are also supported in polytime with VS-SDD. Experiments confirm that VS-SDDs are significantly more succinct than SDDs when applied to classical planning instances, where inherent symmetry exists.
Cite as

Kengo Nakamura, Shuhei Denzumi, and Masaaki Nishino. Variable Shift SDD: A More Succinct Sentential Decision Diagram. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{nakamura_et_al:LIPIcs.SEA.2020.22,
  author =	{Nakamura, Kengo and Denzumi, Shuhei and Nishino, Masaaki},
  title =	{{Variable Shift SDD: A More Succinct Sentential Decision Diagram}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{22:1--22:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Faro, Simone and Cantone, Domenico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.22},
  URN =		{urn:nbn:de:0030-drops-120968},
  doi =		{10.4230/LIPIcs.SEA.2020.22},
  annote =	{Keywords: Boolean function, Data structure, Sentential decision diagram}
}
  • Refine by Author
  • 3 Nishino, Masaaki
  • 2 Minato, Shin-ichi
  • 2 Nakamura, Kengo
  • 1 Denzumi, Shuhei
  • 1 Kawahara, Jun
  • Show More...

  • Refine by Classification
  • 1 Computing methodologies → Knowledge representation and reasoning
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Data structures design and analysis

  • Refine by Keyword
  • 1 Boolean function
  • 1 Connectivity
  • 1 Data structure
  • 1 Decision Diagram
  • 1 Enumeration
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2020
  • 1 2023

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