Engineering a delegatable and error-Tolerant algorithm for counting small subgraphs

Thumbnail Image

Access rights

openAccess

URL

Journal Title

Journal ISSN

Volume Title

A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)

Authors

Date

2018

Department

Department of Computer Science

Major/Subject

Mcode

Degree programme

Language

en

Pages

15
184-198

Series

2018 Proceedings of the 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018, Volume 2018-January

Abstract

We study the problem of counting the number of occurrences of a given six-vertex pattern graph S in an n-vertex host graph H. We engineer an open-source GPU implementation of a distributed algorithm design of Björklund and Kaski [PODC 2016] where (i) the execution of the algorithm can be delegated [Goldwasser, Kalai, and Rothblum, J. ACM 2015] to produce a noninteractive probabilistically checkable proof of correctness, and (ii) the execution of the algorithm when preparing the proof tolerates a controllable number of adversarial errors. Experiments with NVIDIA Tesla K80 and Tesla P100 Accelerators demonstrate that the framework is practical for inputs of up to 512 vertices, with proof checking being several orders of magnitude more efficient than preparing the proof; however, proof preparation still carries at least one order of magnitude overhead compared with just solving the problem.

Description

Keywords

Other note

DOI

10.1137/1.9781611975055.16

Citation

Kaski, P 2018, Engineering a delegatable and error-Tolerant algorithm for counting small subgraphs . in 2018 Proceedings of the 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018 . vol. 2018-January, Society for Industrial and Applied Mathematics, pp. 184-198, Workshop on Algorithm Engineering and Experiments, New Orleans, Louisiana, United States, 07/01/2018 . https://doi.org/10.1137/1.9781611975055.16

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202101251493

Collections

[article-cris] Perustieteiden korkeakoulu / SCI