Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Exact Algorithms for Maximum Independent Set   We show that the maximum independent set problem (MIS) on an $n$-vertex graph
can be solved in $1.1996^nn^{O(1)}$ time and polynomial space, which even is
faster than Robson's $1.2109^{n}n^{O(1)}$-time exponential-space algorithm
published in 1986. We also obtain improved algorithms for MIS in graphs with
maximum degree 6 and 7, which run in time of $1.1893^nn^{O(1)}$ and
$1.1970^nn^{O(1)}$, respectively. Our algorithms are obtained by using fast
algorithms for MIS in low-degree graphs in a hierarchical way and making a
careful analyses on the structure of bounded-degree graphs.

6
The categories of this paper are: astro-ph
32
The categories of this paper are: atom-ph
34
The categories of this paper are: chem-ph
3
The categories of this paper are: physics
27
The categories of this paper are: comp-gas
15
The categories of this paper are: nucl-ex
4
The categories of this paper are: cond-mat
20
The categories of this paper are: acc-phys
25
The categories of this paper are: patt-sol
36
The categories of this paper are: cmp-lg
21
The categories of this paper are: adap-org
8
The categories of this paper are: hep-ex
11
The categories of this paper are: hep-lat
30
The categories of this paper are: q-alg
17
The categories of this paper are: q-fin
2
The categories of this paper are: math