no. 2
Exact and approximate algorithms for the longest induced path problem
RAIRO. Operations Research, Tome 55 (2021) no. 2, pp. 333-353

The longest induced path problem consists in finding a maximum subset of vertices of a graph such that it induces a simple path. We propose a new exact enumerative algorithm that solves problems with up to 138 vertices and 493 edges and a heuristic for larger problems. Detailed computational experiments compare the results obtained by the new algorithms with other approaches in the literature and investigate the characteristics of the optimal solutions.

DOI : 10.1051/ro/2021004
Classification : 05C30, 05C38, 05C85, 68W25, 90C27, 90C35
Keywords: Longest induced path problem, exact algorithm, backtracking, heuristics 
@article{RO_2021__55_2_333_0,
     author = {Marzo, Rusl\'an G. and Ribeiro, Celso C.},
     title = {Exact and approximate algorithms for the longest induced path problem},
     journal = {RAIRO. Operations Research},
     pages = {333--353},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     number = {2},
     doi = {10.1051/ro/2021004},
     mrnumber = {4234141},
     zbl = {1468.05060},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2021004/}
}
TY  - JOUR
AU  - Marzo, Ruslán G.
AU  - Ribeiro, Celso C.
TI  - Exact and approximate algorithms for the longest induced path problem
JO  - RAIRO. Operations Research
PY  - 2021
SP  - 333
EP  - 353
VL  - 55
IS  - 2
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2021004/
DO  - 10.1051/ro/2021004
LA  - en
ID  - RO_2021__55_2_333_0
ER  - 
%0 Journal Article
%A Marzo, Ruslán G.
%A Ribeiro, Celso C.
%T Exact and approximate algorithms for the longest induced path problem
%J RAIRO. Operations Research
%D 2021
%P 333-353
%V 55
%N 2
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2021004/
%R 10.1051/ro/2021004
%G en
%F RO_2021__55_2_333_0
Marzo, Ruslán G.; Ribeiro, Celso C. Exact and approximate algorithms for the longest induced path problem. RAIRO. Operations Research, Tome 55 (2021) no. 2, pp. 333-353. doi: 10.1051/ro/2021004

[1] R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network flows. Elsevier (1988). | MR | Zbl | DOI

[2] P. Alles and S. Poljak, Long induced paths and cycles in Kneser graphs. Graphs Comb. 5 (1989) 303–306. | MR | Zbl | DOI

[3] A.-L. Barabási and R. Albert, Emergence of scaling in random networks. Science 286 (1999) 509–512. | MR | Zbl | DOI

[4] B. Bergougnoux and M. M. Kanté, A meta-algorithm for solving connectivity and acyclicity constraints on locally checkable properties parameterized by graph width measures. Preprint arXiv:1805.11275 (2018).

[5] F. Bökler, M. Chimani, M. H. Wagner and T. Wiedera, An experimental study of ILP formulations for the longest induced path problem. In Combinatorial Optimization, edited by M. Baïou, B. Gendron, O. Günlük and A. R. Mahjoub. In Vol. 12176 of Lecture Notes in Computer Science. Springer, Cham (2020). | MR | Zbl | DOI

[6] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman and Co., New York (1979). | Zbl

[7] F. Gavril, Algorithms for maximum weight induced paths. Inf. Process. Lett. 81 (2002) 203–208. | MR | Zbl | DOI

[8] T. Ishizeki, Y. Otachi and K. Yamazaki, An improved algorithm for the longest induced path problem on k -chordal graphs. Discrete Appl. Math. 156 (2008) 3057–3059. | MR | Zbl | DOI

[9] L. Jaffke, O.-J. Kwon and J. Telle, Polynomial-time algorithms for the Longest Induced Path and Induced Disjoint Paths problems on graphs of bounded mim-width. In: Vol. 89 of Leibniz International Proceedings in Informatics (2018) 1–21. | MR | Zbl

[10] L. Jaffke, O.-J. Kwon and J. A. Telle, Mim-Width I. Induced path problems. Discrete Appl. Math. 278 (2020) 153–168. | MR | Zbl | DOI

[11] W. H. Kautz, Unit-Distance Error-Checking Codes. IRE Trans. Electron. Comput. 7 (1958) 179–180. | DOI

[12] D. Kratsch, H. Müller and I. Todinca, Feedback vertex set and longest induced path on AT-free graphs. In: International Workshop on Graph-Theoretic Concepts in Computer Science. Springer (2003) 309–321. | MR | Zbl

[13] D. Matsypura, A. Veremyev, O. A. Prokopyev and E. L. Pasiliao, On exact solution approaches for the longest induced path problem. Eur. J. Oper. Res. 278 (2019) 546–562. | MR | Zbl | DOI

[14] Moviegalaxies, Social networks in movies. Available from: https://moviegalaxies.com/ (2020).

[15] NetworkX developers, NetworkX documentation. Available from: http://networkx.github.io/(2020).

[16] M. E. Newman, The structure and function of complex networks. SIAM Rev. 45 (2003) 167–256. | MR | Zbl | DOI

[17] PassMark, PassMark Software – CPU Benchmarks. Intel Core i5-4460S vs. Intel Xeon E5-1650 v2 vs. Intel Xeon Gold 6134. Available from: https://www.cpubenchmark.net/compare/Intel-i5-4460S-vs-Intel-Xeon-E5-1650-v2-vs-Intel-Xeon-Gold-6134/2232vs2066vs3008 (2020).

[18] K. Pearson, Notes on regression and inheritance in the case of two parents. Proc. R. Soc. London 58 (1895) 240–242. | DOI

[19] L. O. Prokhorenkova and E. Samosvat, Global clustering coefficient in scale-free networks. In: International Workshop on Algorithms and Models for the Web-Graph. Springer (2014) 47–58. | MR | Zbl | DOI

[20] D. J. Watts and S. H. Strogatz, Collective dynamics of ``small-world’’ networks. Nature 393 (1998) 440–442. | Zbl | DOI

Cité par Sources :