Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs

Zhang, Y; Li, RH; Zhang, Q; Qin, H; Qin, L; Wang, G

Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs

Zhang, Y Li, RH Zhang, Q Qin, H Qin, L

Wang, G

Permalink

Publisher:: ASSOC COMPUTING MACHINERY
Publication Type:: Conference Proceeding
Citation:: Proceedings of the VLDB Endowment, 2024, 17, (11), pp. 2722-2734
Issue Date:: 2024-01-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Published versionAdobe PDF (1.28 MB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Zhang, Y
dc.contributor.author	Li, RH
dc.contributor.author	Zhang, Q
dc.contributor.author	Qin, H
dc.contributor.author	Qin, L https://orcid.org/0000-0001-6068-5062
dc.contributor.author	Wang, G
dc.date.accessioned	2025-03-12T03:12:10Z
dc.date.available	2025-03-12T03:12:10Z
dc.date.issued	2024-01-01
dc.identifier.citation	Proceedings of the VLDB Endowment, 2024, 17, (11), pp. 2722-2734
dc.identifier.issn	2150-8097
dc.identifier.issn	2150-8097
dc.identifier.uri	http://hdl.handle.net/10453/185724
dc.description.abstract	The arboricity (G) of a graph G is defined as the minimum number of edge-disjoint forests that the edge set of G can be partitioned into. It is a fundamental metric and has been widely used in many graph analysis applications. However, computing (G) is typically a challenging task. To address this, an easier to-compute alternative called pseudoarboricity was proposed. Pseudoarboricity has been shown to be closely connected to many important measures in graphs, including the arboricity and the densest subgraph density (G). Computing the exact pseudoarboricity can be achieved by employing a parametric max f low algorithm, but it becomes computationally expensive for large graphs. Existing 2-approximation algorithms, while more efficient, often lack satisfactory approximation accuracy. To overcome these limitations, we propose two new approximation algorithms with theoretical guarantees to approximate the pseudoarboricity. We show that our approximation algorithms can significantly reduce the number of times the max-flow algorithm is invoked, greatly improving its efficiency for exact pseudoarboricity computation. In addition, we also study the pseudoarboricity maintenance problem in dynamic graphs. We propose two novel and efficient algorithms for maintaining the pseudoarboricity when the graph is updated by edge insertions or deletions. Furthermore, we develop two incremental pseudoarboricity maintenance algorithms specifically designed for insertion-only scenarios. We conduct extensive ex periments on 195 real-world graphs, and the results demonstrate the high efficiency and scalability of the proposed algorithms in computing pseudoarboricity for both static and dynamic graphs.
dc.language	en
dc.publisher	ASSOC COMPUTING MACHINERY
dc.relation.ispartof	Proceedings of the VLDB Endowment
dc.relation.isbasedon	10.14778/3681954.3681958
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	0802 Computation Theory and Mathematics, 0806 Information Systems, 0807 Library and Information Studies
dc.subject.classification	4605 Data management and data science
dc.title	Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs
dc.type	Conference Proceeding
utslib.citation.volume	17
utslib.for	0802 Computation Theory and Mathematics
utslib.for	0806 Information Systems
utslib.for	0807 Library and Information Studies
pubs.organisational-group	University of Technology Sydney
pubs.organisational-group	University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	University of Technology Sydney/UTS Groups
pubs.organisational-group	University of Technology Sydney/UTS Groups/Australian Artificial Intelligence Institute (AAII)
utslib.copyright.status	open_access	*
dc.rights.license	This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License (CC BY-NC-ND 4.0). To view a copy of this license, visit https://creativecommons.org/licenses/by-nc-nd/4.0/
dc.date.updated	2025-03-12T03:12:09Z
pubs.issue	11
pubs.publication-status	Published
pubs.volume	17
utslib.citation.issue	11

Abstract:

The arboricity (G) of a graph G is defined as the minimum number of edge-disjoint forests that the edge set of G can be partitioned into. It is a fundamental metric and has been widely used in many graph analysis applications. However, computing (G) is typically a challenging task. To address this, an easier to-compute alternative called pseudoarboricity was proposed. Pseudoarboricity has been shown to be closely connected to many important measures in graphs, including the arboricity and the densest subgraph density (G). Computing the exact pseudoarboricity can be achieved by employing a parametric max f low algorithm, but it becomes computationally expensive for large graphs. Existing 2-approximation algorithms, while more efficient, often lack satisfactory approximation accuracy. To overcome these limitations, we propose two new approximation algorithms with theoretical guarantees to approximate the pseudoarboricity. We show that our approximation algorithms can significantly reduce the number of times the max-flow algorithm is invoked, greatly improving its efficiency for exact pseudoarboricity computation. In addition, we also study the pseudoarboricity maintenance problem in dynamic graphs. We propose two novel and efficient algorithms for maintaining the pseudoarboricity when the graph is updated by edge insertions or deletions. Furthermore, we develop two incremental pseudoarboricity maintenance algorithms specifically designed for insertion-only scenarios. We conduct extensive ex periments on 195 real-world graphs, and the results demonstrate the high efficiency and scalability of the proposed algorithms in computing pseudoarboricity for both static and dynamic graphs.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/185724