The airplane refueling problem is NP-complete and is solvable in polynomial time

Jinchuan Cui, Xiaoya LiarXiv 2023 · OpenReview

TL;DR

This paper tackles the Airplane Refueling Problem (ARP), a complex optimization challenge. While ARP is proven to be NP-complete, the authors demonstrate that for large-scale instances, a specific sequential search algorithm can solve it in polynomial time, bridging the gap between theoretical hardness and practical solvability.

What Problem Does This Paper Address?

The Airplane Refueling Problem (ARP) is a fascinating combinatorial optimization problem where a fleet of airplanes aims to reach a target. Airplanes can refuel each other mid-flight and then be dropped out. The objective is to maximize the flight distance of the last remaining airplane. This problem is known to be NP-complete, meaning that finding an optimal solution is computationally very difficult for large numbers of airplanes. The challenge lies in the combinatorial explosion of possible refueling and drop-out strategies. This paper addresses the apparent paradox: how can an NP-complete problem be solved efficiently?

Methods

The core of the paper's contribution lies in analyzing the complexity of a previously proposed "sequential search algorithm" for ARP. This algorithm enumerates "sequential feasible solutions." The authors build upon prior work that established ARP as NP-complete and introduced this algorithm. The key insight is that while the number of sequential feasible solutions ($Q_n$) can grow exponentially with the number of airplanes ($n$) in general, there's an "inflection point" ($2m$) where this growth rate dramatically changes. For $n$ larger than this inflection point, $Q_n$ becomes bounded by a polynomial in $n$, specifically $n^m$ for some constant $m$. This transition from exponential to polynomial complexity for large instances is the central methodological finding.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bridging the NP-complete/Polynomial Gap: The most significant insight is demonstrating that a problem proven to be NP-complete can, in fact, be solved in polynomial time for sufficiently large problem instances. This challenges the common intuition that NP-complete problems are intractable for all but small inputs.
  • The "Inflection Point": The concept of an "inflection point" ($2m$) is crucial. It marks a threshold in the problem size ($n$) beyond which the complexity of the sequential search algorithm shifts from exponential to polynomial. This suggests that the structure of large-scale ARP instances allows for more efficient solution strategies.
  • Complexity Transition: The paper highlights that the growth rate of the number of sequential feasible solutions slows down significantly for larger $n$, making the problem tractable. This is visualized in Figure 2, showing distinct phases of complexity.

Key Results

The paper's main result, presented as Theorem 2, states that for large-scale ARP instances (specifically, when $n > 2m$ for a certain index $m$), the number of sequential feasible solutions $Q_n$ is bounded by $n^m$. This implies that the sequential search algorithm, which enumerates these solutions, runs in polynomial time for these large instances. Consequently, the Airplane Refueling Problem is shown to be solvable in polynomial time for large-scale inputs, despite its NP-complete nature.

Limitations and Future Work

The paper acknowledges that for small instances of ARP, the sequential search algorithm still exhibits exponential time complexity. The "inflection point" $2m$ is dependent on the specific instance parameters. Future work could focus on more precisely characterizing this inflection point or developing alternative algorithms that achieve polynomial time complexity even for smaller instances. The paper also implicitly relies on the existence of a "sequential feasible solution" that is optimal, which is a strong assumption that might warrant further investigation.

Summary updated

Abstract

The airplane refueling problem is a nonlinear combinatorial optimization problem, and its equivalent problem the $n$-vehicle exploration problem is proved to be NP-complete (arXiv:2304.03965v1, The $n$-vehicle exploration problem is NP-complete). In Article (arXiv:2210.11634v2, A polynomial-time algorithm to solve the aircraft refueling problem: the sequential search algorithm), we designed the sequential search algorithm for solving large scale of airplane refueling instances, and we proved that the computational complexity increases to polynomial time with increasing number of airplanes. Thus the airplane refueling problem, as an NP-complete problem, is solvable in polynomial time when its input scale is sufficiently large.
BibTeX
@misc{cui2023airplane,
  author = {Jinchuan Cui and Xiaoya Li},
  title = {{The airplane refueling problem is NP-complete and is solvable in polynomial time}},
  year = {2023},
  eprint = {2305.12478},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2305.12478},
}
Figure