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

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/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/doi/pdf/10.1145/3186893, Theorem 6.5	link