Independent Set Queries: Difference between revisions
Jump to navigation
Jump to search
(Created page with "{{DISPLAYTITLE:Independent Set Queries (Independent Set Queries)}} == Description == For a graph $G=(V,E)$ and a given subset of vertices $S\subseteq G$, answer the query of the form "is $S$ an independent set?" == Parameters == <pre>n: number of vertices m: number of edges</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions FROM Problem == {| class="wikitable sortable" style="text-align:center;" width=...") |
No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| Line 6: | Line 6: | ||
== Parameters == | == Parameters == | ||
$n$: number of vertices | |||
m: number of edges | |||
$m$: number of edges | |||
== Table of Algorithms == | == Table of Algorithms == | ||
Latest revision as of 08:27, 10 April 2023
Description
For a graph $G=(V,E)$ and a given subset of vertices $S\subseteq G$, answer the query of the form "is $S$ an independent set?"
Parameters
$n$: number of vertices
$m$: number of edges
Table of Algorithms
Currently no algorithms in our database for the given problem.
Reductions FROM Problem
| Problem | Implication | Year | Citation | Reduction |
|---|---|---|---|---|
| Triangle Detection | if: to-time: $O(n^{2} / \log^c n)$ to answer all subsequent batches of $\log n$ independent set queries from a graph that takes $O(n^k)$ time to preprocess for some $c,k > {0}$ then: from-time: $O(n^{3} / \log^{c+1} n)$ |
2018 | https://dl-acm-org.ezproxy.canberra.edu.au/doi/pdf/10.1145/3186893, Theorem 6.5 | link |
| BMM | if: to-time: $O(n^{2} / \log^c n)$ to answer all subsequent batches of $\log n$ independent set queries from a graph that takes $O(n^k)$ time to preprocess for some $c,k > {0}$ then: from-time: $O(n^{3} / \log^{c+1} n)$ |
2018 | https://dl-acm-org.ezproxy.canberra.edu.au/doi/pdf/10.1145/3186893, Theorem 6.5 | link |