An experimental study of ILP formulations for the longest induced path problem

DOI10.1007/978-3-030-53262-8_8MaRDI QIDQ2225052zbMATH OpenOpenAlexFDO

Authors Fritz Bökler, Markus Chimani, Mirko H. Wagner, Tilo Wiedera

Publication date 4 February 2021

Full work available at URL https://arxiv.org/abs/2002.07012

zbMATH Keywords

longest induced path, maximum cardinality node subset

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27)

Abstract: Given a graph $G=(V,E)$, the longest induced path problem asks for a maximum cardinality node subset $WsubseteqV$ such that the graph induced by $W$ is a path. It is a long established problem with applications, e.g., in network analysis. We propose novel integer linear programming (ILP) formulations for the problem and discuss efficient implementations thereof. Comparing them with known formulations from literature, we prove that they are beneficial in theory, yielding stronger relaxations. Moreover, our experiments show their practical superiority.

Recommendations

• New formulations and branch-and-cut procedures for the longest induced path problem
• Exact and approximate algorithms for the longest induced path problem
• On exact solution approaches for the longest induced path problem
• An improved algorithm for the longest induced path problem on \(k\)-chordal graphs
• The Longest Path Problem Is Polynomial on Interval Graphs

Cited in

(11)

• Exact approaches for the orderly colored longest path problem: performance comparison
• On exact solution approaches for the longest induced path problem
• Improved approaches to solve the one-to-one skewgram problem
• New formulations and branch-and-cut procedures for the longest induced path problem
• Exact and approximate algorithms for the longest induced path problem
• Extension of the Top-Down Data-Driven Strategy to ILP
• MIP formulations for induced graph optimization problems: a tutorial
• Maximum weighted induced forests and trees: new formulations and a computational comparative review
• Integer programming formulations for the \(k\)-in-a-tree problem in graphs
• Exact methods for the longest induced cycle problem
• Semidefinite programming bounds and a branch-and-bound algorithm for the chordless cycle problem

This page was built for publication: An experimental study of ILP formulations for the longest induced path problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2225052)