Collision-Free Routing Problem with Restricted L-Path
Sasanka Roy
Indian Statistical Institute, Kolkata

We consider a variant of collision-free routing problem CRP. In this problem, we are given set $C$ of $n$ vehicles which are moving in a plane along a predefined directed rectilinear path. Our objective (CRP) is to find the maximum number of vehicles that can move without collision. CRP is shown to be NP-Hard. It was also shown that the approximation of this problem is as hard as Maximum Independent Set problem (MIS) even if the paths between a pair of vehicles intersects at most once. So we study the constrained version CCRP of CRP in which each vehicle is allowed to move in a directed L-Shaped Path. We prove CCRP is NP-Hard by a reduction from MIS in L-graphs, which was proved to be NP-Hard even for unit L-graph. Simultaneously, we show that any CCRP can be partitioned into collection L of L-graphs such that CCR Preduces to a problem of finding MIS in L-graph for each partition in L. Thus we show that any algorithm, thatcan produce a $\beta$-approximation for L-graph, would produce a $\beta$-approximation for CCRP. We show that unit L-graphs intersected by an axis-parallel line is Co-comparable. For this problem, we propose an algorithm for finding MIS that runs in $O(n^2)$ time and uses $O(n)$ space. As a corollary, we get a 2-approximation algorithm for finding MIS of unit L-graph that runs in $O(n^2)$ time and uses $O(n)$ space.