{"ID":23475150,"CreatedAt":"2026-09-18T01:09:05.407443952Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.19943","arxiv_id":"2609.19943","title":"Counting Triangles in Graph Streams with Repeatable and Forgettable Edges","abstract":"Most existing graph streaming algorithms assume the ideal scenario where each edge arrives only once. Real-world graph streams, such as communication or transaction logs, often contain many repeated occurrences of the same edge. In general, the algorithms developed for the single-edge arrival case can fail when edges can arrive multiple times. Motivated by this, we study the {\\em repeated-edge arrival graph streaming model} where an edge is allowed to arrive multiple times. In this work, we study the triangle counting problem in the repeated-edge arrival model: approximate the number of triangles in the underlying {\\em simple graph} despite arbitrary edge repetitions. We design the first algorithms for triangle counting with optimal space complexity. In particular, we present a single-pass algorithm that computes an $(\\varepsilon,δ)$-approximation of the number of triangles with optimal space complexity. We introduce {\\em right-to-be-forgotten graph streaming} (RFGS) model, where a forget operation can cause all previous occurrences of an edge to disappear. We show that our single-pass algorithm can be extended to the RFGS model with optimal space complexity. Finally, we present optimal constant-pass algorithms that compute an $(\\varepsilon,δ)$-approximation of the number of triangles and cliques for the repeated-edge arrival graph streams.","short_abstract":"Most existing graph streaming algorithms assume the ideal scenario where each edge arrives only once. Real-world graph streams, such as communication or transaction logs, often contain many repeated occurrences of the same edge. In general, the algorithms developed for the single-edge arrival case can fail when edges c...","url_abs":"https://arxiv.org/abs/2609.19943","url_pdf":"https://arxiv.org/pdf/2609.19943v1","authors":"[\"Sourav Chakraborty\",\"Debarshi Chanda\",\"Arijit Ghosh\",\"A. Pavan\",\"Chhaya Trehan\",\"N. V. Vinodchandran\"]","published":"2026-09-17T09:17:14Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}