Minimizing the Stabbing Number of Matchings, Trees, and Triangulations

Title: Minimizing the Stabbing Number of Matchings, Trees, and Triangulations

Abstract: This research focuses on minimizing the stabbing number, a measure of how many line segments can be intersected by a single line, for perfect matchings, spanning trees, and triangulations. The study presents a general proof technique to show the NP-hardness of these problems. For matchings, the research also implies a non-trivial lower bound on approximability. On the positive side, the paper proposes a cut-based integer programming formulation for minimizing the stabbing number of matchings and spanning trees. From the linear programming relaxation of this formulation, the research derives polynomial-time lower bounds and conjectures an iterated rounding scheme that could potentially provide a constant-factor approximation algorithm.

Main Research Question: How can we minimize the stabbing number of perfect matchings, spanning trees, and triangulations while maintaining their structural integrity?

Methodology: The study uses mathematical programming and proof techniques to analyze the complexity and approximability of these stabbing problems. The research proposes a cut-based integer programming formulation to find structures with small stabbing number.

Results: The research shows the NP-hardness of minimizing the stabbing number of perfect matchings, spanning trees, and triangulations. For matchings, the study also presents a non-trivial lower bound on approximability. The research conjectures an iterated rounding scheme that could potentially provide a constant-factor approximation algorithm for minimizing the stabbing number of matchings and spanning trees.

Implications: This research contributes to the understanding of the computational complexity of stabbing problems and provides a mathematical programming framework for finding structures with small stabbing number. The proposed iterated rounding scheme could potentially lead to efficient algorithms for minimizing the stabbing number of matchings and spanning trees.

Link to Article: https://arxiv.org/abs/0310034v3 Authors: arXiv ID: 0310034v3