An Experimental Study of ILP Formulations for the Longest Induced Path Problem

02/17/2020
by   Markus Chimani, et al.
0

Given a graph G=(V,E), the longest induced path problem asks for a maximum cardinality node subset W⊆ V 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset