Article

Finding paths and cycles of superpolylogarithmic length

Author:

Harold N. GabowAuthors Info & Claims

STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing

Pages 407 - 416

https://doi.org/10.1145/1007352.1007418

Published: 13 June 2004 Publication History

Get Access

Abstract

Let l be the number of edges in a longest cycle containing a given vertex v in an undirected graph. We show how to find a cycle through v of length (Ω(√ log l, log log l)) in polynomial time. This implies the same bound for the longest cycle, longest vw-path and longest path. The previous best bound for longest path is length Ω((log l )²/, log log l) due to Björklund and Husfeldt. Our approach, which builds on Björklund and Husfeldt's, uses cycles to enlarge cycles. This self-reducibility allows the approximation method to be iterated.

References

[1]

N. Alon, R. Yuster and U. Zwick, Color-coding, J. ACM 42 (1995), pp. 844--856.

Digital Library

Google Scholar

[2]

H. L. Bodlaender, Minor tests with depth-first search, J. Algorithms, 14 (1993), pp. 1--23.

Digital Library

Google Scholar

[3]

A. Björklund and T. Husfeldt, Finding a path of superlogarithmic length, SIAM J. Comput. 32, 6 (2003), pp. 1395--1402.

Digital Library

Google Scholar

[4]

A. Björklund, T. Husfeldt and S. Khanna, Approximating longest directed path, Electronic Colloq. on Comp. Complexity, Rept. No. 32, 2003.

Google Scholar

[5]

T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 2nd Ed., McGraw-Hill, NY, 2001.

Digital Library

Google Scholar

[6]

M. R. Fellows and M. A. Langston, Nonconstructive tools for proving polynomial-time decidability, J. ACM 35 (1988), pp. 727--739.

Digital Library

Google Scholar

[7]

H. N. Gabow and S. Nie, Finding a long directed cycle, Proc. 15th Annual ACM-SIAM Symp. Disc. Alg., 2004, pp. 49--58.

Digital Library

Google Scholar

[8]

J. E. Hopcroft and R. E. Tarjan, Dividing a graph into triconnected components, SIAM J. Comput. 2,3 (1973), pp. 135--158.

Crossref

Google Scholar

[9]

D. Karger, R. Motwani and G. D. S. Ramkumar, On approximating the longest path in a graph, Algorithmica 18 (1997), pp. 82--98.

Digital Library

Google Scholar

[10]

A. S. LaPaugh and R. L. Rivest, The subgraph homeomorphism problem, J. Comput. Sys. Sci. 20 (1980), pp. 133--149.

Crossref

Google Scholar

[11]

B. Monien, How to find long paths efficiently, Annals Disc. Math., 25 (1985), pp. 239--254.

Google Scholar

[12]

N. Robertson and P. D. Seymour, Graph Minors. XIII: The disjoint paths problem, J. Comb. Th. B 63 (1995), pp. 65--110.

Digital Library

Google Scholar

[13]

R. E. Tarjan, Depth-first search and linear graph algorithms, SIAM J. Comput., 1 (1972), pp. 146--160.

Digital Library

Google Scholar

[14]

D. B. West, Introduction to Graph Theory, 2nd Ed., Prentice Hall (2001).

Google Scholar

Cited By

View all

Ioannidou KNikolopoulos S(2010)The longest path problem is polynomial on cocomparability graphsProceedings of the 36th international conference on Graph-theoretic concepts in computer science10.5555/1939238.1939245(27-38)Online publication date: 28-Jun-2010
https://dl.acm.org/doi/10.5555/1939238.1939245
Feder TMotwani R(2010)Finding large cycles in Hamiltonian graphsDiscrete Applied Mathematics10.5555/1752263.1752539158:8(882-893)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.5555/1752263.1752539
Portugal DAntunes CRocha R(2010)A study of genetic algorithms for approximating the longest path in generic graphs2010 IEEE International Conference on Systems, Man and Cybernetics10.1109/ICSMC.2010.5641920(2539-2544)Online publication date: Oct-2010
https://doi.org/10.1109/ICSMC.2010.5641920
Show More Cited By

Index Terms

Finding paths and cycles of superpolylogarithmic length
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Finding Paths and Cycles of Superpolylogarithmic Length

Let ℓ be the number of edges in a longest cycle containing a given vertex 𝓋 in an undirected graph. We show how to find a cycle through 𝓋 of length exp(Ω(√ log ℓ/log log ℓ)) in polynomial time. This implies the same bound for the longest cycle, ...
Long rainbow paths and rainbow cycles in edge colored graphs A survey

Graph coloring problem and problem on the existence of paths and cycles have always been popular topics in graph theory. The problem on the existence of rainbow paths and rainbow cycles in edge colored graphs, as an integration of them, was well studied ...
Finding a Path of Superlogarithmic Length

We consider the problem of finding a long, simple path in an undirected graph. We present a polynomial-time algorithm that finds a path of length $\Omega\bigl((\log L/\log\log L)^2\bigr)$, where L denotes the length of the longest simple path in the ...

Comments

Information & Contributors

Information

Published In

STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing

June 2004

660 pages

ISBN:1581138520

DOI:10.1145/1007352

Program Chair:
László Babai
University of Chicago, Chicago, IL

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

STOC04

Sponsor:

STOC04: Symposium of Theory of Computing 2004

June 13 - 16, 2004

IL, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
293
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ioannidou KNikolopoulos S(2010)The longest path problem is polynomial on cocomparability graphsProceedings of the 36th international conference on Graph-theoretic concepts in computer science10.5555/1939238.1939245(27-38)Online publication date: 28-Jun-2010
https://dl.acm.org/doi/10.5555/1939238.1939245
Feder TMotwani R(2010)Finding large cycles in Hamiltonian graphsDiscrete Applied Mathematics10.5555/1752263.1752539158:8(882-893)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.5555/1752263.1752539
Portugal DAntunes CRocha R(2010)A study of genetic algorithms for approximating the longest path in generic graphs2010 IEEE International Conference on Systems, Man and Cybernetics10.1109/ICSMC.2010.5641920(2539-2544)Online publication date: Oct-2010
https://doi.org/10.1109/ICSMC.2010.5641920
Feder TMotwani R(2010)Finding large cycles in Hamiltonian graphsDiscrete Applied Mathematics10.1016/j.dam.2009.12.006158:8(882-893)Online publication date: Apr-2010
https://doi.org/10.1016/j.dam.2009.12.006
Arkin EFekete SIslam KMeijer HMitchell JNúòez-Rodríguez YPolishchuk VRappaport DXiao H(2009)Not being (super)thin or solid is hardComputational Geometry: Theory and Applications10.1016/j.comgeo.2008.11.00442:6-7(582-605)Online publication date: 1-Aug-2009
https://dl.acm.org/doi/10.1016/j.comgeo.2008.11.004
Hüffner FWernicke SZichner T(2008)Algorithm Engineering for Color-Coding with Applications to Signaling Pathway DetectionAlgorithmica10.5555/3118777.311917952:2(114-132)Online publication date: 1-Oct-2008
https://dl.acm.org/doi/10.5555/3118777.3119179
Kawarabayashi K(2008)An improved algorithm for finding cycles through elementsProceedings of the 13th international conference on Integer programming and combinatorial optimization10.5555/1788814.1788849(374-384)Online publication date: 26-May-2008
https://dl.acm.org/doi/10.5555/1788814.1788849
Kawarabayashi KReed BTeng S(2008)A nearly linear time algorithm for the half integral disjoint paths packingProceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/1347082.1347131(446-454)Online publication date: 20-Jan-2008
https://dl.acm.org/doi/10.5555/1347082.1347131
Takahara YTeramoto SUehara R(2008)Longest Path Problems on Ptolemaic GraphsIEICE - Transactions on Information and Systems10.1093/ietisy/e91-d.2.170E91-D:2(170-177)Online publication date: 1-Feb-2008
https://dl.acm.org/doi/10.1093/ietisy/e91-d.2.170
Kawarabayashi K(2008)An Improved Algorithm for Finding Cycles Through ElementsInteger Programming and Combinatorial Optimization10.1007/978-3-540-68891-4_26(374-384)Online publication date: 2008
https://doi.org/10.1007/978-3-540-68891-4_26
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Finding Paths and Cycles of Superpolylogarithmic Length

Long rainbow paths and rainbow cycles in edge colored graphs A survey

Finding a Path of Superlogarithmic Length