Hardness of peeling with stashes

DOI10.1016/J.IPL.2016.05.006MaRDI QIDQ2630336zbMATH OpenOpenAlexFDO

Authors Vikram Nathan, Michael Mitzenmacher

Publication date 27 July 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.5169

zbMATH Keywords

graph algorithmshashingNP-completenesspeeling processstash

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Abstract: The analysis of several algorithms and data structures can be framed as a peeling process on a random hypergraph: vertices with degree less than k and their adjacent edges are removed until no vertices of degree less than k are left. Often the question is whether the remaining hypergraph, the k-core, is empty or not. In some settings, it may be possible to remove either vertices or edges from the hypergraph before peeling, at some cost. For example, in hashing applications where keys correspond to edges and buckets to vertices, one might use an additional side data structure, commonly referred to as a stash, to separately handle some keys in order to avoid collisions. The natural question in such cases is to find the minimum number of edges (or vertices) that need to be stashed in order to realize an empty k-core. We show that both these problems are NP-complete for all $kgeq2$ on graphs and regular hypergraphs, with the sole exception being that the edge variant of stashing is solvable in polynomial time for $k=2$ on standard (2-uniform) graphs.

Recommendations

• The stripping process can be slow. I.
• Analysis of Algorithms on the Cores of Random Graphs
• Sudden emergence of a giant k-core in a random graph

Cites work

• Cuckoo hashing
• Efficient erasure correcting codes
• scientific article; zbMATH DE number 437557 (Why is no real title available?)
• scientific article; zbMATH DE number 6469129 (Why is no real title available?)
• Preventing unraveling in social networks: the anchored k-core problem
• The pure literal rule threshold and cores in random hypergraphs
• Tight thresholds for Cuckoo hashing via XORSAT (extended abstract)

Cited in

(2)

• Peeling or not peeling—is that the question?
• The stripping process can be slow. I.

This page was built for publication: Hardness of peeling with stashes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2630336)