Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Polynomial Fixed-Parameter Algorithms: A Case Study for Longest Path on
  Interval Graphs   We study the design of fixed-parameter algorithms for problems already known
to be solvable in polynomial time. The main motivation is to get more efficient
algorithms for problems with unattractive polynomial running times. Here, we
focus on a fundamental graph problem: Longest Path, that is, given an
undirected graph, find a maximum-length path in $G$. Longest Path is NP-hard in
general but known to be solvable in $O(n^{4})$ time on $n$-vertex interval
graphs. We show how to solve Longest Path on Interval Graphs, parameterized by
vertex deletion number $k$ to proper interval graphs, in $O(k^{9}n)$ time.
Notably, Longest Path is trivially solvable in linear time on proper interval
graphs, and the parameter value $k$ can be approximated up to a factor of 4 in
linear time. From a more general perspective, we believe that using
parameterized complexity analysis may enable a refined understanding of
efficiency aspects for polynomial-time solvable problems similarly to what
classical parameterized complexity analysis does for NP-hard problems.

21
The categories of this paper are: adap-org
8
The categories of this paper are: hep-ex
20
The categories of this paper are: acc-phys
34
The categories of this paper are: chem-ph
22
The categories of this paper are: chao-dyn
4
The categories of this paper are: cond-mat
12
The categories of this paper are: nucl-th
5
The categories of this paper are: gr-qc
9
The categories of this paper are: nlin
35
The categories of this paper are: mtrl-th
14
The categories of this paper are: math-ph
31
The categories of this paper are: ao-sci
17
The categories of this paper are: q-fin
23
The categories of this paper are: solv-int
25
The categories of this paper are: patt-sol
26
The categories of this paper are: bayes-an