Certifying Induced Subgraphs in Large Graphs

Meyer, Ulrich, Tran, Hung and Tsakalidis, Konstantinos ORCID: 0000-0001-6470-9332 (2023) Certifying Induced Subgraphs in Large Graphs. .

PDF
jgaa-extmem-certifying.pdf - Author Accepted Manuscript
Download (499kB) | Preview

Official URL: http://dx.doi.org/10.1007/978-3-031-27051-2_20

Abstract

We introduce I/O-effiient certifying algorithms for bipartite graphs, as well as for the classes of split, threshold, bipartite chain, and trivially perfect graphs. When the input graph is a member of the respective class, the certifying algorithm returns a certificate that characterizes this class. Otherwise, it returns a forbidden induced subgraph as a certificate for non-membership. On a graph with n vertices and m edges, our algorithms take I/Os in the worst case for split, threshold and trivially perfect graphs. In the same complexity bipartite and bipartite chain graphs can be certified with high probability. We provide implementations for split and threshold graphs and provide a preliminary experimental evaluation.

Item Type:	Conference or Workshop Item (Unspecified)
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	12 Jan 2024 11:48
Last Modified:	12 Jan 2024 11:48
DOI:	10.1007/978-3-031-27051-2_20
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3177804