Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Dense Graph Partitioning on sparse and dense graphs   We consider the problem of partitioning a graph into a non-fixed number of
non-overlapping subgraphs of maximum density. The density of a partition is the
sum of the densities of the subgraphs, where the density of a subgraph is its
average degree, that is, the ratio of its number of edges and its number of
vertices. This problem, called Dense Graph Partition, is known to be NP-hard on
general graphs and polynomial-time solvable on trees, and polynomial-time
2-approximable. In this paper we study the restriction of Dense Graph Partition
to particular sparse and dense graph classes. In particular, we prove that it
is NP-hard on dense bipartite graphs as well as on cubic graphs. On dense
graphs on $n$ vertices, it is polynomial-time solvable on graphs with minimum
degree $n-3$ and NP-hard on $(n-4)$-regular graphs. We prove that it is
polynomial-time $4/3$-approximable on cubic graphs and admits an efficient
polynomial-time approximation scheme on graphs of minimum degree $n-t$ for any
constant $t\geq 4$.

11
The categories of this paper are: hep-lat
3
The categories of this paper are: physics
22
The categories of this paper are: chao-dyn
13
The categories of this paper are: quant-ph
25
The categories of this paper are: patt-sol
18
The categories of this paper are: econ
23
The categories of this paper are: solv-int
6
The categories of this paper are: astro-ph
29
The categories of this paper are: funct-an
5
The categories of this paper are: gr-qc
16
The categories of this paper are: stat
10
The categories of this paper are: q-bio
7
The categories of this paper are: hep-th
21
The categories of this paper are: adap-org
31
The categories of this paper are: ao-sci
8
The categories of this paper are: hep-ex