Nearly optimal independence oracle algorithms for edge estimation in hypergraphs

Holger Dell; John Lapinskas; Kitty Meeks

doi:10.48550/arXiv.2211.03874

Nearly optimal independence oracle algorithms for edge estimation in hypergraphs

Holger Dell, John Lapinskas, Kitty Meeks

Algorithms

Research output: Working paper › Preprint

Abstract

We study a query model of computation in which an n-vertex k-hypergraph can be accessed only via its independence oracle or via its colourful independence oracle, and each oracle query may incur a cost depending on the size of the query. In each of these models, we obtain oracle algorithms to approximately count the hypergraph's edges, and we unconditionally prove that no oracle algorithm for this problem can have significantly smaller worst-case oracle cost than our algorithms.

Original language	English
Number of pages	92
DOIs	https://doi.org/10.48550/arXiv.2211.03874
Publication status	Published - 7 Nov 2022

Keywords

cs.CC
cs.DS
Fine-grained complexity,
Approximate counting
Hypergraphs
Graph oracles

Access to Document

10.48550/arXiv.2211.03874

2211.03874v2

Cite this

@misc{d1aca994848a49ed985ca0052d51930b,

title = "Nearly optimal independence oracle algorithms for edge estimation in hypergraphs",

abstract = "We study a query model of computation in which an n-vertex k-hypergraph can be accessed only via its independence oracle or via its colourful independence oracle, and each oracle query may incur a cost depending on the size of the query. In each of these models, we obtain oracle algorithms to approximately count the hypergraph's edges, and we unconditionally prove that no oracle algorithm for this problem can have significantly smaller worst-case oracle cost than our algorithms.",

keywords = "cs.CC, cs.DS, Fine-grained complexity,, Approximate counting, Hypergraphs, Graph oracles",

author = "Holger Dell and John Lapinskas and Kitty Meeks",

year = "2022",

month = nov,

day = "7",

doi = "10.48550/arXiv.2211.03874",

language = "English",

type = "WorkingPaper",

}

TY - UNPB

T1 - Nearly optimal independence oracle algorithms for edge estimation in hypergraphs

AU - Dell, Holger

AU - Lapinskas, John

AU - Meeks, Kitty

PY - 2022/11/7

Y1 - 2022/11/7

N2 - We study a query model of computation in which an n-vertex k-hypergraph can be accessed only via its independence oracle or via its colourful independence oracle, and each oracle query may incur a cost depending on the size of the query. In each of these models, we obtain oracle algorithms to approximately count the hypergraph's edges, and we unconditionally prove that no oracle algorithm for this problem can have significantly smaller worst-case oracle cost than our algorithms.

AB - We study a query model of computation in which an n-vertex k-hypergraph can be accessed only via its independence oracle or via its colourful independence oracle, and each oracle query may incur a cost depending on the size of the query. In each of these models, we obtain oracle algorithms to approximately count the hypergraph's edges, and we unconditionally prove that no oracle algorithm for this problem can have significantly smaller worst-case oracle cost than our algorithms.

KW - cs.CC

KW - cs.DS

KW - Fine-grained complexity,

KW - Approximate counting

KW - Hypergraphs

KW - Graph oracles

U2 - 10.48550/arXiv.2211.03874

DO - 10.48550/arXiv.2211.03874

M3 - Preprint

BT - Nearly optimal independence oracle algorithms for edge estimation in hypergraphs

ER -

Nearly optimal independence oracle algorithms for edge estimation in hypergraphs

Abstract

Keywords

Access to Document

Fingerprint

Cite this