Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Linear-Time FPT Algorithms via Network Flow   In the area of parameterized complexity, to cope with NP-Hard problems, we
introduce a parameter k besides the input size n, and we aim to design
algorithms (called FPT algorithms) that run in O(f(k)n^d) time for some
function f(k) and constant d. Though FPT algorithms have been successfully
designed for many problems, typically they are not sufficiently fast because of
huge f(k) and d. In this paper, we give FPT algorithms with small f(k) and d
for many important problems including Odd Cycle Transversal and Almost 2-SAT.
More specifically, we can choose f(k) as a single exponential (4^k) and d as
one, that is, linear in the input size. To the best of our knowledge, our
algorithms achieve linear time complexity for the first time for these
problems. To obtain our algorithms for these problems, we consider a large
class of integer programs, called BIP2. Then we show that, in linear time, we
can reduce BIP2 to Vertex Cover Above LP preserving the parameter k, and we can
compute an optimal LP solution for Vertex Cover Above LP using network flow.
Then, we perform an exhaustive search by fixing half-integral values in the
optimal LP solution for Vertex Cover Above LP. A bottleneck here is that we
need to recompute an LP optimal solution after branching. To address this
issue, we exploit network flow to update the optimal LP solution in linear
time.

25
The categories of this paper are: patt-sol
36
The categories of this paper are: cmp-lg
15
The categories of this paper are: nucl-ex
31
The categories of this paper are: ao-sci
17
The categories of this paper are: q-fin
33
The categories of this paper are: plasm-ph
4
The categories of this paper are: cond-mat
26
The categories of this paper are: bayes-an
23
The categories of this paper are: solv-int
2
The categories of this paper are: math
21
The categories of this paper are: adap-org
32
The categories of this paper are: atom-ph
5
The categories of this paper are: gr-qc
7
The categories of this paper are: hep-th
28
The categories of this paper are: alg-geom
3
The categories of this paper are: physics