On exact solution approaches for the longest induced path problem

Dmytro Matsypura, Alexander Veremyev, Oleg A. Prokopyev and Eduardo L. Pasiliao

European Journal of Operational Research, 2019, vol. 278, issue 2, 546-562

Abstract: The graph diameter, which is defined as the length of the longest shortest path in a graph, is often used to quantify graph communication properties. In particular, the graph diameter provides an intuitive measure of the worst-case pairwise distance. However, in many practical settings, where vertices can either fail or be overloaded or can be destroyed by an adversary and thus cannot be used in any communication or transportation path, it is natural to consider other possible measures of the worst-case distance. One such measure is the longest induced path. The longest induced path problem is defined as the problem of finding a subset of vertices of the largest cardinality such that the induced subgraph is a simple path. In contrast to the polynomially computable graph diameter, this problem is NP-hard. In this paper, we focus on exact solution approaches for the problem based on linear integer programming (IP) techniques. We first propose three conceptually different linear IP models and study their basic properties. To improve the performance of the standard IP solvers, we propose an exact iterative algorithm that solves a sequence of smaller IPs to obtain an optimal solution for the original problem. In addition, we develop a heuristic capable of finding induced paths in large networks. Finally, we conduct an extensive computational study to evaluate the performance of the proposed solution methods.

Keywords: Networks; Longest induced path problem; Maximum subgraph identification problem; Integer programming; Randomized heuristic (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719303315
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:278:y:2019:i:2:p:546-562

DOI: 10.1016/j.ejor.2019.04.011

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().