License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2023.11
URN: urn:nbn:de:0030-drops-183613
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18361/
Go to the corresponding LIPIcs Volume Portal

Nakamura, Kengo ; Nishino, Masaaki ; Yasuda, Norihito ; Minato, Shin-ichi

CompDP: A Framework for Simultaneous Subgraph Counting Under Connectivity Constraints

pdf-format:
LIPIcs-SEA-2023-11.pdf (1 MB)

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.

BibTeX - Entry

@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.dagstuhl.de/opus/volltexte/2023/18361},
  URN =		{urn:nbn:de:0030-drops-183613},
  doi =		{10.4230/LIPIcs.SEA.2023.11},
  annote =	{Keywords: Subgraph counting, Connectivity, Zero-suppressed Binary Decision Diagram}
}

Keywords: Subgraph counting, Connectivity, Zero-suppressed Binary Decision Diagram
Collection: 21st International Symposium on Experimental Algorithms (SEA 2023)
Issue Date: 2023
Date of publication: 19.07.2023
Supplementary Material: Software: https://github.com/nttcslab/compdp-counting

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI