Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Fixed-Parameter Tractable Algorithms for Corridor Guarding Problems   Given an orthogonal connected arrangement of line-segments, Minimum Corridor
Guarding(MCG) problem asks for an optimal tree/closed walk such that, if a
guard moves through the tree/closed walk, all the line-segments are visited by
the guard. This problem is referred to as Corridor-MST/Corridor-TSP (CMST/CTSP)
for the cases when the guarding walk is a tree/closed walk, respectively. The
corresponding decision version of MCG is shown to be NP-Complete[1]. The
parameterized version of CMST/CTSP referred to as k-CMST/k-CTSP, asks for an
optimal tree/closed walk on at most k vertices, that visits all the
line-segments. Here, vertices correspond to the endpoints and intersection
points of the input line-segments. We show that k-CMST/k-CTSP is
fixed-parameter tractable (FPT) with respect to the parameter k. Next, we
propose a variant of CTSP referred to as Minimum Link CTSP(MLC), in which the
link-distance of the closed walk has to be minimized. Here, link-distance
refers to the number of links or connected line-segments with same orientation
in the walk. We prove that the decision version of MLC is NP-Complete, and show
that the parameterized version, namely b-MLC, is FPT with respect to the
parameter b, where b corresponds to the link-distance. We also consider another
related problem, the Minimum Corridor Connection (MCC). Given a rectilinear
polygon partitioned into rectilinear components or rooms, MCC asks for a
minimum length tree along the edges of the partitions, such that every room is
incident to at least one vertex of the tree. The decision version of MCC is
shown to be NP-Complete[2]. We prove the fixed parameter tractability of the
parameterized version of MCC, namely k-MCC with respect to the parameter k,
where k is the number of rooms.

0
The categories of this paper are: hep-ph
33
The categories of this paper are: plasm-ph
35
The categories of this paper are: mtrl-th
9
The categories of this paper are: nlin
14
The categories of this paper are: math-ph
32
The categories of this paper are: atom-ph
37
The categories of this paper are: supr-con
25
The categories of this paper are: patt-sol
27
The categories of this paper are: comp-gas
28
The categories of this paper are: alg-geom
26
The categories of this paper are: bayes-an
4
The categories of this paper are: cond-mat
18
The categories of this paper are: econ
19
The categories of this paper are: eess
36
The categories of this paper are: cmp-lg
2
The categories of this paper are: math