Fedor V. Fomin
Department of Informatics, University of Bergen, Norway [email protected]
Petr A. Golovach
Department of Informatics, University of Bergen, Norway [email protected]
Daniel Lokshtanov
Department of Computer Science, University of California Santa Barbara, USA [email protected]
Fahad Panolan
Department of Computer Science and Engineering, IIT Hyderabad, India [email protected]
Saket Saurabh
The Institute of Mathematical Sciences, HBNI, Chennai, India [email protected]
Meirav Zehavi
Ben-Gurion University, Beersheba, Israel [email protected]
Abstract
An undirected graphGisd-degenerateif every subgraph ofGhas a vertex of degree at mostd. By the classical theorem of Erdős and Gallai from 1959, every graph of degeneracyd >1 contains a cycle of length at leastd+ 1. The proof of Erdős and Gallai is constructive and can be turned into a polynomial time algorithm constructing a cycle of length at leastd+ 1. But can we decide in polynomial time whether a graph contains a cycle of length at leastd+ 2? An easy reduction fromHamiltonian Cycleprovides a negative answer to this question: Deciding whether a graph has a cycle of length at leastd+ 2 is NP-complete. Surprisingly, the complexity of the problem changes drastically when the input graph is 2-connected. In this case we prove that deciding whether Gcontains a cycle of length at leastd+k can be done in time 2O(k)|V(G)|O(1). In other words, deciding whether a 2-connectedn-vertexGcontains a cycle of length at leastd+ logncan be done in polynomial time. Similar algorithmic results hold for long paths in graphs. We observe that deciding whether a graph has a path of length at leastd+ 1 is NP-complete. However, we prove that if graphGis connected, then deciding whetherGcontains a path of length at leastd+k can be done in time 2O(k)nO(1). We complement these results by showing that the choice of degeneracy as the “above guarantee parameterization” is optimal in the following sense: For anyε >0 it is NP-complete to decide whether a connected (2-connected) graph of degeneracydhas a path (cycle) of length at least (1 +ε)d.
2012 ACM Subject Classification Mathematics of computing → Graph algorithms; Theory of computation→Parameterized complexity and exact algorithms
Keywords and phrases Longest path, longest cycle, fixed-parameter tractability, above guarantee parameterization
Digital Object Identifier 10.4230/LIPIcs.ESA.2019.47
Related Version The full version of the paper is available athttps://arxiv.org/abs/1902.02526.
Funding The research leading to these results has received funding from the Research Council of Norway via the projects “CLASSIS” and “MULTIVAL” and from the European Research Council (ERC) via grant LOPPRE, reference 819416.
© Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi;
Acknowledgements We thank Nikolay Karpov for communicating to us the question of finding a path above the degeneracy bound and Proposition 15.
1 Introduction
The classical theorem of Erdős and Gallai [11] says that
ITheorem 1(Erdős and Gallai [11]). Every graph withn vertices and more than(n−1)`/2 edges (`≥2) contains a cycle of length at least`+ 1.
Recall that a graphGisd-degenerate if every subgraphH ofGhas a vertex of degree at mostd, that is, the minimum degreeδ(H)≤d. Respectively, thedegeneracy of graphG, is dg(G) = max{δ(H)|H is a subgraph ofG}.Since a graph of degeneracydhas a subgraph H with at least d· |V(H)|/2 edges, by Theorem 1, it contains a cycle of length at least d+ 1. Let us note that the degeneracy of a graph can be computed in polynomial time, see e.g. [28], and thus by Theorem 1, deciding whether a graph has a cycle of length at least d+ 1 can be done in polynomial time. In this paper we revisit this classical result from the algorithmic perspective.
We define the following problem.
Input: A graphGand a positive integerk.
Task: Decide whetherGcontains a cycle of length at least dg(G) +k.
Longest Cycle Above Degeneracy
Let us first sketch whyLongest Cycle Above Degeneracyis NP-complete fork= 2 even for connected graphs. We can reduceHamiltonian CycletoLongest Cycle Above Degeneracywith k= 2 as follows. For a connected non-complete graphGonnvertices, we construct connected graphH fromGand a complete graphKn−1 onn−1 vertices as follows. We identify one vertex ofGwith one vertex ofKn−1. Thus the obtained graphH has|V(G)|+n−2 vertices and is connected; its degeneracy is n−2. ThenH has a cycle with dg(H) + 2 =nvertices if and only ifGhas a Hamiltonian cycle.
Interestingly, when the input graph is 2-connected, the problem becomes fixed-parameter tractable being parameterized by k. Let us recall that a connected graph G is (vertex) 2-connected if for every v ∈ V(G), G−v is connected. Our first main result is the following theorem.
ITheorem 2. On2-connected graphs Longest Cycle Above Degeneracyis solvable in time2O(k)·nO(1).
Similar results can be obtained for paths. Of course, if a graph contains a cycle of length d+ 1, it also contains a simple path ond+ 1 vertices. Thus for every graph Gof degeneracy d, deciding whetherGcontains a path on dg(G) + 1 vertices can be done in polynomial time.
Again, it is easy to show that it is NP-complete to decide whetherGcontains a path with d+ 2 vertices by a reduction fromHamiltonian Path. The reduction is very similar to the one we sketched forLongest Cycle Above Degeneracy. The only difference that this time graphH consists of a disjoint union ofGandKn−1. The degeneracy ofH isd=n−2, andH has a path withd+ 2 =nvertices if and only ifGcontains a Hamiltonian path. Note that graphH used in the reduction is not connected. However, when the input graphGis connected, the complexity of the problem changes drastically. We define
Input: A graphGand a positive integerk.
Task: Decide whetherGcontains a path with at least dg(G) +kvertices.
Longest Path Above Degeneracy
The second main contribution of our paper is the following theorem.
ITheorem 3. On connected graphs Longest Path Above Degeneracyis solvable in time2O(k)·nO(1).
Let us remark that Theorem 2 does not imply Theorem 3, because Theorem 2 holds only for 2-connected graphs.
We also show that the parameterization lower bound dg(G) that is used in Theorems 2 and 3 is tight in some sense. We prove that for any 0< ε <1, it is NP-complete to decide whether a connected graphG contains a path with at least (1 +ε)dg(G) vertices and it is NP-complete to decide whether a 2-connected graph G contains a cycle with at least (1 +ε)dg(G) vertices.
Related work. Hamiltonian PathandHamiltonian Cycleproblems are among the oldest and most fundamental problems in Graph Theory. In parameterized complexity the following generalizations of these problems,Longest Path andLongest Cycle, were heavily studied. TheLongest Pathproblem is to decide, given ann-vertex (di)graph G and an integerk, whetherGcontains a path of length at leastk. Similarly, theLongest Cycle problem is to decide whether G contains a cycle of length at least k. There is a plethora of results about parameterized complexity (we refer to the book of Cygan at al. [9] for the introduction to the field) of Longest Pathand Longest Cycle(see, e.g., [4, 5, 7, 6, 12, 14, 22, 23, 24, 32]) since the early work of Monien [29]. The fastest known randomized algorithm forLongest Path on undirected graph is due to Björklund et al. [4]
and runs in time 1.657k·nO(1). On the other hand very recently, Tsur gave the fastest known deterministic algorithm for the problem running in time 2.554k ·nO(1) [31]. Respectively forLongest Cycle, the current fastest randomized algorithm running in time 4k·nO(1) was given by Zehavi in [33] and the best deterministic algorithm constructed by Fomin et al.
in [13] runs in time 4.884k·nO(1).
Our theorems about Longest Path Above Degeneracy and Longest Cycle Above Degeneracy fit into an interesting trend in parameterized complexity called
“above guarantee” parameterization. The general idea of this paradigm is that the natural parameterization of, say, a maximization problem by the solution size is not satisfactory if there is a lower bound for the solution size that is sufficiently large. For example, there always exists a satisfying assignment that satisfies half of the clauses or there is always a max-cut containing at least half the edges. Thus nontrivial solutions occur only for the values of the parameter that are above the lower bound. This indicates that for such cases, it is more natural to parameterize the problem by the difference of the solution size and the bound.
The first paper about above guarantee parameterization was due to Mahajan and Raman [26]
who applied this approach to theMax Sat andMax Cutproblem. This approach was successfully applied to various problems, see e.g. [1, 8, 16, 17, 18, 19, 20, 25, 27].
ForLongest Path, the only successful above guarantee parameterization known prior to our work was parameterization above shortest path. More precisely, lets, tbe vertices of an undirected graphG. Clearly, the length of any (s, t)-path inGis lower bounded by the shortest distance,d(s, t), between these vertices. Based on this observation, Bezáková et al.
in [3] introduced theLongest Detour problem that asks, given a graphG, two vertices
s, t, and a positive integerk, whetherGhas an (s, t)-path with at leastd(s, t) +kvertices.
They proved that for undirected graphs, this problem can be solved in time 2O(k)·nO(1). On the other hand, the parameterized complexity of Longest Detouron directed graphs is still open. For the variant of the problem where the question is whetherGhas an (s, t)-path withexactly d(s, t) +k vertices, a randomized algorithm with running time 2.746k·nO(1) and a deterministic algorithm with running time 6.745k·nO(1) were obtained [3]. These algorithms work for both undirected and directed graphs. Parameterization above degeneracy is “orthogonal” to the parameterization above the shortest distance. There are classes of graphs, like planar graphs, that have constant degeneracy and arbitrarily large diameter. On the other hand, there are classes of graphs, like complete graphs, of constant diameter and unbounded degeneracy.
Our approach. Our algorithmic results are based on classical theorems of Dirac [10], and Erdős and Gallai [11] on the existence of “long cycle” and “long paths” and can be seen as non-trivial algorithmic extensions of these classical theorems. Letδ(G) be the minimum vertex degree of graphG.
ITheorem 4 (Dirac [10]). Everyn-vertex 2-connected graphGwith minimum vertex degree δ(G)≥2, contains a cycle with at leastmin{2δ(G), n} vertices.
ITheorem 5(Erdős and Gallai [11]). Every connectedn-vertex graphGcontains a path with at leastmin{2δ(G) + 1, n} vertices.
Theorem 4 is used to prove Theorem 2 and Theorem 5 is used to prove Theorem 3.
We give a high-level overview of the ideas used to prove Theorem 2. The ideas behind the proof of Theorem 3 are similar. LetGbe a 2-connected graph of degeneracyd. Ifd=O(k), we can solveLongest Cycle Above Degeneracyin time 2O(k)·nO(1) by making use of one of the algorithms forLongest Cycle. Assume from now thatd≥c·kfor some constant c, which will be specified in the proof. Then we find ad-coreH ofG(a connected subgraph ofGwith the minimum vertex degree at leastd). This can be done in linear time by one of the known algorithms, see e.g. [28]. If the size ofH is sufficiently large, say|V(H)| ≥d+k, we use Theorem 4 to conclude that H contains a cycle with at least|V(H)| ≥d+kvertices.
The most interesting case occurs when|V(H)|< d+k. Suppose thatGhas a cycle of length at leastd+k. It is possible to prove that there is also a cycle of length at leastd+k that hits the coreH. We do not know how many times and in which vertices ofH this cycle enters and leavesH, but we can guess these terminal points. The interesting property of the coreH is that, loosely speaking, for any “small” set of terminal points, insideH the cycle can be rerouted in such a way that it will contain all vertices ofH.
A bit more formally, we prove the following structural result. We define a system of segments inGwith respect toV(H), which is a family of internally vertex-disjoint paths {P1, . . . , Pr}inG(see Figure 1). Moreover, for every 1≤i≤r, every pathPi has at least 3 vertices, its endpoints are in V(H) and all internal vertices ofPi are in V(G)\V(H). Also the union of all the segments is a forest with every connected component being a path.
We prove thatGcontains a cycle of length at leastk+dif and only if
either there is a path of length at leastk+d− |V(H)|with endpoints inV(H) and all internal vertices outsideH, or
there is a system of segments with respect toV(H) such that the total number of vertices outsideH used by the paths of the system, is within the interval [k+d− |V(H)|,2·(k+ d− |V(H)|)].
H
P1 Pr
Figure 1 Reducing Longest Cycle Above Degeneracy to finding a system of segments P1, . . . , Pr; complementing the segments into a cycle is shown by dashed lines.
The proof of this structural result is built on Lemma 8, which describes the possibility of routing in graphs of large minimal degree. The crucial property is that we can complement any system of segments of bounded size by segments inside the coreH to obtain a cycle that contains all the vertices ofH as is shown in Figure 1.
Since|V(H)|> d, the problem of finding a cycle of length at leastk+dinGboils down to one of the following tasks. Either find a path of lengthc0·kwith all internal vertices outside H, or find a system of segments with respect toV(H) such that the total number of vertices used by the paths of the system isc00·k, herec0andc00are the constants to be specified in the proof. In the first case, we can use one of the known algorithms to find in time 2O(k)·nO(1) such a long path. In the second case, we can use color-coding to solve the problem.
Organization of the paper. In Section 2 we give basic definitions and state some known fundamental results. Sections 3–4 contain the proof of Theorems 3 and 2. In Section 3 we state structural results that we need for the proofs and in Section 4 we complete the proofs.
In Section 5, we give the complexity lower bounds for our algorithmic results. We conclude the paper in Section 6 by stating some open problems.
2 Preliminaries
We consider only finite undirected graphs. For a graphG, we useV(G) andE(G) to denote its vertex set and edge set, respectively. Throughout the paper we use n = |V(G)| and m=|E(G)|. For a graph Gand a subsetU ⊆V(G) of vertices, we write G[U] to denote the subgraph ofGinduced byU. We writeG−U to denote the graph G[V(G)\U]; for a single-element setU ={u}, we writeG−u. For a vertex v, we denote byNG(v) the(open) neighborhood ofv, i.e., the set of vertices that are adjacent to v inG. For a setU ⊆V(G), NG(U) = (S
v∈UNG(v))\U. Thedegree of a vertexv isdG(v) =|NG(v)|. Theminimum degreeofGisδ(G) = min{dG(v)|v∈V(G)}. Ad-coreofGis an inclusion maximal induced connected subgraph H withδ(H) ≥d. Every graph of degeneracy at leastd contains a d-core and that can be found in linear time (see [28]). A vertexuof a connected graphG with at least two vertices is acut vertex ifG−uis disconnected. A connected graphGis 2-connected if it has no cut vertices. An inclusion maximal induced 2-connected subgraph ofGis called abiconnected component orblock. LetB be the set of blocks of a connected graphGand letC be the set of cut vertices. Consider the bipartite graphBlock(G) with the vertex setB ∪C, where (B, C) is the bipartition, such thatB∈ Bandc∈Care adjacent if and only ifc∈V(B). The block graph of a connected graph is always a tree (see [21]).
A path in a graph is a self-avoiding walk. Thus no vertex appears in a path more than once. A cycle is a closed self-avoiding walk . For a path P with end-verticess andt, we say that the vertices ofV(P)\ {s, t}are internal. We say thatGis a linear forest if each component ofGis a path. Thecontraction of an edgexy is the operation that removes the
vertices xandy together with the incident edges and replaces them by a vertex uxy that is adjacent to the vertices ofNG({x, y}) of the original graph. IfH is obtained from Gby contracting some edges, thenH is a contractionofG.
We summarize below some known algorithmic results which will be used as subroutines by our algorithm.
IProposition 6. Longest Pathand Longest Cycle are solvable in time2O(k)·nO(1). We also need the result about the variant of Longest Pathwith fixed end-vertices. In the (s, t)-Longest Path, we are given two verticess andt of a graph Gand a positive integerk. The task is to decide, whetherGhas an (s, t)-path with at leastk vertices. Using the results of Bezáková et al. [2], we immediately obtain the following.
IProposition 7. (s, t)-Longest Pathis solvable in time2O(k)·nO(1).
3 Segments and rerouting
In this section we define systems of segments and prove structural results about them. These combinatorial results are crucial for our algorithms forLongest Path Above Degeneracy andLongest Cycle Above Degeneracy.
The following rerouting lemma is crucial for our algorithms.
I Lemma 8. Let G be an n-vertex graph and k be a positive integer such that δ(G) ≥ max{5k−3, n−k}. Let {s1, t1}, . . . ,{sr, tr}, r≤k, be a collection of pairs of vertices of Gsuch that (i)si, ti ∈ {s/ j, tj} for all i6=j,i, j ∈ {1, . . . , r}, and (ii) there is at least one indexi∈ {1, . . . , r} such thatsi6=ti. Then there is a family of pairwise vertex-disjoint paths P={P1, . . . , Pr} inGsuch that each Pi is an(si, ti)-path andSr
i=1V(Pi) =V(G), that is, the paths cover all vertices ofG.
Proof. We prove the lemma in two steps. First we show that there exists a familyP0 of pairwise vertex-disjoint paths connecting all pairs{si, ti}. Then we show that if the paths of P0 do not cover all vertices of G, it is possible to enlarge a path such that the new family of paths covers more vertices.
We start by constructing a family of vertex-disjoint pathsP0 ={P1, . . . , Pr}inGsuch that each Pi ∈ P0 is an (si, ti)-path. We prove that we can construct paths in such a way that eachPi has at most 3 vertices. LetT =Sr
i=1{si, ti} andS =V(G)\T. Notice that|S| ≥ n−2k ≥δ(G) + 1−2k≥3k−2.We consecutively construct paths of P0 for i∈ {1, . . . , r}. Ifsi=ti, then we have a trivial (si, ti)-path. Ifsi andti are adjacent, then edgesiti forms an (si, ti)-path with 2 vertices. Assume thatsi6=ti andsiti∈/E(G). The already constructed paths contain at mostr−1≤k−1 vertices ofS in total. Hence, there is a setS0 ⊆Sof at least 2k−1 vertices that are not contained in any of already constructed paths. Sinceδ(G)≥n−k, each vertex of G has at mostk−1 non-neighbors in G. By the pigeonhole principle, there isv∈S0 such thatsiv, tiv∈E(G). Then we can construct the pathPi=sivti.
We proved that there is a familyP0 ={P1, . . . , Pr} of vertex-disjoint (si, ti)-paths in G. Among all such families, let us select a familyP ={P1, . . . , Pr}covering the maximum number of vertices ofV(G). If Sr
i=1V(Pi) =V(G), then the lemma holds. Assume that
|Sr
i=1V(Pi)| <|V(G)|. Suppose |Sr
i=1V(Pi)| ≤3k−1. Since si 6= ti for some i, there is an edgeuv in one of the paths. Sincen≥δ(G) + 1≥5k−2, there are at least 2k−1 vertices uncovered by paths ofP. Sinceδ(G)≥n−k, each vertex ofGhas at mostk−1
non-neighbors inG. Thus there isw∈V(G)\(Sr
i=1V(Pi)) adjacent to bothuandv. But then we can extend the path containinguvby replacinguvby the path uwv. The paths of the new family cover more vertices than the paths ofP, which contradicts the choice ofP.
Suppose |Sr
i=1V(Pi)| ≥3k. Because the paths of P are vertex-disjoint, the union of edges of paths fromP contains ak-matching. That is, there arek edgesu1v1, . . . , ukvk of G such that for everyi ∈ {1, . . . , k}, vertices ui, vi are consecutive in some path from P andui 6=uj, ui 6=vj for all non-equali, j ∈ {1, . . . , k}. Letw∈V(G)\(Sr
i=1V(Pi)). We again use the observation thatwhas at most k−1 non-neighbors inGand, therefore, there isj ∈ {1, . . . , k} such thatujw, vjw∈E(G). Then we extend the path containingujvj by replacing edgeujvj by the pathujwvj, contradicting the choice ofP. We conclude that the
paths ofP cover all vertices ofG. J
Let G be a graph and let T ⊂ V(G) be a set of terminals. We need the following definitions.
IDefinition 9 (Terminal segments). We say that a pathP inGis aone-terminalT-segment if it has at least two vertices, exactly one end-vertex of P is in T and other vertices are not inT. Respectively,P is a two-terminalT-segmentif it has at least three vertices, both end-vertices ofP are inT and internal vertices ofP are not inT.
For every cycle C hittingH, removing the vertices ofH from C turns it into a set of two-terminalT-segments forT =V(H). So here is the definition.
IDefinition 10(System ofT-segments). We say that a set{P1, . . . , Pr} of paths inG is a system ofT-segmentsif it satisfies the following conditions.
(i) For eachi∈ {1, . . . , r},Pi is a two-terminalT-segment, (ii) P1, . . . , Pr are pairwise internally vertex-disjoint, and (iii) the union of P1, . . . , Pr is a linear forest.
Let us remark that we do not require that the end-vertices of the paths {P1, . . . , Pr} cover all vertices ofT. System of segments will be used for solvingLongest Cycle Above Degeneracy.
ForLongest Path Above Degeneracywe need to modify the definition of a system ofT-segments to include the possibility that path can start or end inH.
IDefinition 11(Extended system ofT-segments). We say that a set {P1, . . . , Pr} of paths inG is an extended system ofT-segmentsif the following holds.
(i) At least one and at most two paths are one-terminalT-segments and the others are two-terminalT-segments.
(ii) P1, . . . , Pr are pairwise internally vertex-disjoint and the end-vertices of each one- terminal segment that is inV(G)\T is pairwise distinct with the other vertices of the paths.
(iii) The union ofP1, . . . , Pr is a linear forest and if{P1, . . . , Pr}contains two one-terminal segments, then the vertices of these segments are in distinct components of the forest.
The following lemma will be extremely useful for the algorithm solvingLongest Path Above Degeneracy. Informally, it shows that if a connected graphGis of large degeneracy but has a small coreH, then deciding whetherGhas a path of lengthk+dcan be reduced to checking whetherGhas an extended system ofT-segments with terminal setT =V(H) such that the total number of vertices used by the system isO(k).
ILemma 12. Letd, k∈N. LetGbe a connected graph with ad-coreH such thatd≥5k−3 and d >|V(H)| −k. Then Ghas a path on d+k vertices if and only ifG has an extended system ofT-segments{P1, . . . , Pr}with terminal set T =V(H) such that the total number of vertices contained in the paths of the system in V(G)\V(H)isp=d+k− |V(H)|.
Proof. We putT =V(H). Suppose first thatG has an extended system{P1, . . . , Pr} of T-segments and that the total number of vertices of the paths in the system outside T is p=d+k− |T|. Letsiandti be the end-vertices ofPi fori∈ {1, . . . , r}and assume without loss of generality that for 1≤i < j≤r, the vertices ofPi andPj are pairwise distinct with the possible exceptionti=sj wheni=j−1. We also assume without loss of generality that P1 is a one-terminal segment andt1∈T and if {P1, . . . , Pr}has two one-terminal segments, then the second such segment isPrandsr∈T. Note that because|V(H)|> d, we have that p=d+k− |V(H)|< k.
Suppose that{P1, . . . , Pr}contains one one-terminal segmentP1. Letsr+1be an arbitrary vertex ofT\(Sr
i=1V(Pi)). Notice that such a vertex exists, because|T∩(Sr
i=1V(Pi))| ≤ 2p−1 < 2k−1 and |T| ≥ d+ 1 ≥ 5k−3. Consider the collection of pairs of vertices {t1, s2},{t2, s3}, . . . ,{tr, sr+1}. Notice that vertices from distinct pairs are distinct and tr6=sr+1. By Lemma 8, there are vertex-disjoint pathsP10, . . . , Pr0 inH that coverT such that Pi0 is a (ti, si+1)-path for i ∈ {1, . . . , r}. By concatenating P1, P10, P2, . . . , Pr, Pr0 we obtain a path inGwith|T|+p=d+k vertices.
Assume now that{P1, . . . , Pr} contains two one-terminal segmentsP1andPr. Consider the collection of pairs of vertices{t1, s2}, . . . ,{tr−1, sr}. Notice that vertices from distinct pairs are distinct and there isi∈ {2, . . . , r}such thatti−16=si by the condition (iii) of the definition of an extended system of segments. By Lemma 8, there are vertex-disjoint paths P10, . . . , Pr−10 inH that coverT such thatPi0 is a (ti, si+1)-path for i∈ {1, . . . , r−1}. By concatenatingP1, P10, . . . , Pr−10 , Pr we obtain a path inGwith|T|+p=d+kvertices.
To show the implication in the opposite direction, let us assume thatGhas an (x, y)-path P withd+k vertices. We distinguish several cases.
Case 1: V(P)∩T =∅. Consider a shortest path P0 with one end-vertex s∈V(P) and the second end-vertext ∈T. Notice that such a path exists, becauseG is connected.
Denote byPxandPy the (s, x) and (s, y)-subpaths ofP respectively. Becaused≥5k−3,
|V(Px)| ≥kor|V(Py)| ≥k. Assume that|V(Px)| ≥k. Then the concatenation ofP0 and Px is a path with at least k+ 1 vertices and it contains a subpath P00 with the end-vertextwithp+ 1 vertices. We have that{P0}is an extended system of T-segments andP00haspvertices outsideT.
Case 2: V(P)∩T 6=∅andE(P)∩E(H) =∅. Let S =V(P)∩T. SinceH is an in- duced subgraph ofGandE(P)∩E(H) =∅,|V(P)\S| ≥(d+k)/2−1≥3k−5/2>
3p−5/2≥2p−2. Then for everyt∈S, either the (t, x)-subpath Pxof P contains at leastpvertices outsideT or the (t, y)-subpathPy ofP contains at leastpvertices outside T. Assume without loss of generality that Px contains at least p vertices outside T. Consider the minimal subpathP0 ofPxending att such that|V(P0)\T|=p. Then the start vertexsofP0 is not inT. Let{t1, . . . , tr}=V(P0)∩T and assume that t1, . . . , tr are ordered in the same order as they occur inP0 starting froms. In particular,tr=t.
Let t0 =s. Consider the paths P1, . . . , Pr where Pi is the (ti−1, ti)-subpath ofP0 for i∈ {1, . . . , r}. Sincek > p,r≤k. We obtain that{P1, . . . , Pr} is an extended system of T-segments withpvertices outsideT.
Case 3: E(P)∩E(H)6=∅. Then there are distincts, t∈T∩V(P) such that the (s, t)- subpath ofP lies inH. SinceP has at leastpvertices outsideT, there ares0, t0∈V(P)\T such that the (s0, t0)-subpathP0 ofP is a subpath with exactlypvertices outsideT with s, t∈V(P0). LetP1, . . . , Prbe the family of inclusion maximal subpaths ofP0 containing
the vertices of V(P0)\T such that the internal vertices of eachPiare outsideT. Observe that since s6=t, the union of these paths is a linear forest with at least two components.
We conclude that the set{P1, . . . , Pr}is a required extended system ofT-segments. J The next lemma will be used for solving Longest Cycle Above Degeneracy. I Lemma 13. Let d, k ∈ N. Let G be a 2-connected graph with a d-core H such that d≥5k−3 andd >|V(H)| −k. Then Ghas a cycle with at leastd+k vertices if and only if one of the following holds (where p=d+k− |V(H)|).
(i) There are distinct s, t ∈ V(H) and an (s, t)-path P in G with all internal vertices outsideV(H)such that P has at least pinternal vertices.
(ii) Ghas a system of T-segments {P1, . . . , Pr} with terminal setT =V(H)and the total number of vertices of the paths outsideV(H)is at leastpand at most 2p−2.
Proof. We putT =V(H). First, we show that if (i) or (ii) holds, thenGhas a cycle with at least d+kvertices. Suppose that there are distinct s, t∈T and an (s, t)-path P inG with all internal vertices outsideT such thatP has at least pinternal vertices. By Lemma 8, H has a Hamiltonian (s, t)-pathP0. By taking the union ofP andP0 we obtain a cycle with at least|T|+p=d+kvertices.
Now assume thatGhas a system ofT-segments{P1, . . . , Pr} and the total number of vertices of the paths outside T is at least p. Letsi andti be the end-vertices of Pi for i∈ {1, . . . , r}and assume without loss of generality that for 1≤i < j≤r, the vertices ofPi andPj are pairwise distinct with the possible exceptionti=sj wheni=j−1. Consider the collection of pairs of vertices{t1, s2}, . . . ,{tr−1, sr},{tr, s1}. Notice that vertices from distinct pairs are distinct andtr6=s1. By Lemma 8, there are vertex-disjoint pathsP10, . . . , Pr0 inH that coverT such thatPi0 is a (ti, si+1)-path for i∈ {1, . . . , r−1}andPr0 is a (tr, s1)- path. By taking the union ofP1, . . . , Pr andP10, . . . , Pr0 we obtain a cycle inGwith at least
|T|+p=d+kvertices.
To show the implication in the other direction, assume thatGhas a cycleCwith at least d+kvertices.
Case 1: V(C)∩T =∅. SinceGis a 2-connected graph, there are pairwise distinct vertices s, t ∈ T and x, y ∈ V(C) and vertex-disjoint (s, x) and (y, t)-paths P1 and P2 such that the internal vertices of the paths are outside T∪V(C). The cycleC contains an (x, y)-pathP with at least (d+k)/2 + 1≥pvertices. The concatenation ofP1,P andP2
is an (s, t)-path inGwith at leastpinternal verices and the internal vertices are outside T. Hence, (i) holds.
Case 2: |V(C)∩T|= 1. LetV(C)∩T ={s}for some vertexs. SinceGis 2-connected, there is a shortest (x, t)-path P inG−s such thatx∈V(C) andt ∈T. The cycle C contains an (s, x)-pathP0 with at least (d+k)/2 + 1≥pvertices. The concatenation of P0 andP is an (s, t)-path inGwith at leastpinternal vertices and the internal vertices of the path are outside T. Therefore, (i) is fulfilled.
Case 3: |V(C)∩T| ≥2. Since |V(C)| ≥ d and |T| < d, we have that V(C)\T 6= ∅.
Then we can find pairs of distinct vertices{s1, t1}. . . ,{s`, t`} ofT ∩V(C) and segments P1, . . . , P` of C such that (a) Pi is an (si, ti)-path fori ∈ {1, . . . , `} with at least one internal vertex and the internal vertices ofPi are outsideT, (b) for 1≤i < j≤`, the vertices of Pi andPj are distinct with the possible exception ti =sj ifi =j−1 and, possibly,t`=s1, and (c)S`
i=1V(Pi)\T =V(C)\T. If there isi∈ {1, . . . , `}such that Pi has at leastpinternal vertices, then (i) is fulfilled.
Now assume that eachPihas at mostp−1 internal vertices; notice thatp≥2 in this case.
We select an inclusion minimal set of indicesI⊆ {1, . . . , `} such that|S
i∈IV(Pi)\T| ≥p.
Notice that because each path has at mostp−1 internal vertices, |S
i∈IV(Pi)\T| ≤2p−2.
LetI={i1, . . . , ir}andi1< . . . < ir. By the choice ofPi1, . . . , Pir, the union ofPi1, . . . , Pir
is either the cycle C or a linear forest. Suppose that the union of the paths is C. Then I = {1, . . . , `}, ` ≤p and|V(P)∩T| =`. Note that because |V(H)|> d, we have that p=d+k− |V(H)|< k. We obtain thatC has at most (2p−2) +p≤3p−2<3k−2< d+k vertices (the last inequality follows from the fact thatd≥5k−3); a contradiction. Hence, the union of the paths is a linear forest. Therefore,{Pi1, . . . , Pir}is a system ofT-segments with terminal set T =V(H) and the total number of vertices of the paths outside T is at
leastpand at most 2p−2, that is, (ii) is fulfilled. J
We have established the fact that the existence of a long (path) cycle is equivalent to the existence of an (extended) system ofT-segments for some terminal setT with at most p≤kvertices from outsideT. Towards designing algorithms forLongest Path Above DegeneracyandLongest Cycle Above Degeneracy, we define two auxiliary problems which can be solved using well known color-coding technique.
Input: A graphG,T ⊂V(G) and a positive integerspandr.
Task: Decide whether Ghas a system of segments{P1, . . . , Pr}w.r.t. T such that the total number of internal vertices of the paths isp.
Segments with Terminal Set
Input: A graphG,T ⊂V(G) and a positive integerspandr.
Task: Decide whetherGhas an extended system of segments{P1, . . . , Pr}w.r.t.
T such that the total number of vertices of the paths outsideT isp.
Extended Segments with Terminal Set
ILemma 14 (?). 1 Segments with Terminal Set and Extended Segments with Terminal Setare solvable in time 2O(p)·nO(1).
4 Putting all together: Final proofs
Proof of Theorem 3. LetGbe a connected graph of degeneracy at least dand letkbe a positive integer. Ifd≤5k−4, then we check the existence of a path withd+k≤6k−4 vertices using Proposition 6 in time 2O(k)·nO(1). Assume from now thatd≥5k−3. Then we find ad-coreH ofG. This can be done in linear time using the results of Matula and Beck [28]. If|V(H)| ≥d+k, then by Theorem 5, H, and hence G, contains a path with min{2d+ 1,|V(H)|} ≥d+k vertices. Assume that|V(H)|< d+k. By Lemma 12,Ghas a path withd+kvertices if and only ifGhas pathsP1, . . . , Pr such that{P1, . . . , Pr} is an extended system ofT-segments forT =V(H) and the total number of vertices of the paths outsideT isp=d+k− |T|. Since the number of vertices in every graph is more than its minimum degree, we have that|T|> d, and thusp < k. For eachr∈ {1, . . . , p}, we verify if such a system exists in time 2O(k)·nO(1) by making use of Lemma 14. Thus the total running time of the algorithm is 2O(k)·nO(1).
1 Proofs of results marked with (?) are omitted in this extended abstract.
Proof of Theorem 2. Let Gbe a 2-connected graph of degeneracy at leastdand letk∈N. Ifd≤5k−4, then we check the existence of a cycle with at least d+k≤6k−4 vertices using Proposition 6 in time 2O(k)·nO(1). Assume from now on thatd≥5k−3. Then we find ad-coreH ofGin linear time using the results of Matula and Beck [28].
We claim that if|V(H)| ≥d+k, thenHcontains a cycle with at leastd+kvertices. IfH is 2-connected, then this follows from Theorem 4. Assume thatH is not a 2-connected graph.
By the definition of a d-core,H is connected. Observe that|V(H)| ≥d+ 1≥5k−2≥3.
Hence, H has at least two blocks and at least one cut vertex. Consider the block graph Block(H) ofH. Recall that the vertices ofBlock(H) are the blocks and the cut vertices ofH and a cut vertexcis adjacent to a blockBif and only ifc∈V(B). Recall also thatBlock(H) is a tree. We select an arbitrary blockR of H and declare it to be theroot of Block(H).
Let S =V(G)\V(H). Observe that S 6=∅, becauseG is 2-connected and H is not. Let F1, . . . , F` be the components ofG[S]. We contract the edges of each component and denote the obtained vertices byu1, . . . , u`. Denote byG0 the obtained graph. It is straightforward to verify that G0 has no cut vertices, that is, G0 is 2-connected. For each i∈ {1, . . . , `}, considerui. This vertex has at least 2 neighbors in V(H). We select a vertexvi ∈NG0(ui) that is not a cut vertex of H or, if all the neighbors ofui are cut vertices, we selectvi be a cut vertex at maximum distance fromR inBlock(H). Then we contractuivi. Observe that by the choice of eachvi, the graphG00obtained fromG0 by contractingu1v1, . . . , u`v`is 2-connected. We have thatG00is a 2-connected graph of minimum degree at leastdwith at leastd+k vertices. By Theorem 4,G00has a cycle with at least min{2d,|V(G00)|} ≥d+k vertices. BecauseG00 is a contraction ofG, we conclude thatGcontains a cycle with at least d+kvertices as well.
From now we can assume that |V(H)|< d+k. By Lemma 13,Ghas a cycle withd+k vertices if and only if one of the following holds forp=d+k− |T|where T =V(H).
(i) There are distincts, t∈T and an (s, t)-pathP inGwith all internal vertices outside T such thatP has at leastpinternal vertices.
(ii) G has a system of T-segments {P1, . . . , Pr} and the total number of vertices of the paths outside T is at least pand at most 2p−2.
Notice thatp≤k(becaused− |T| ≤0). We verify whether (i) holds using Proposition 7.
To do it, we consider all possible choices of distincts, t. Then we construct the auxiliary graph Gst from G by the deletion of the vertices of T \ {s, t} and the edges of E(H).
Then we check whetherGst has an (s, t)-path of length at leastp+ 1 in time 2O(k)·nO(1) applying Proposition 7.
Assume that (i) is not fulfilled. Then it remains to check (ii). For everyr∈ {1, . . . , p}, we verify the existence of a system ofT-segments{P1, . . . , Pr} in time 2O(k)·nO(1) using Lemma 14. We return the answeryes if we get the answer yes for at least one instance of Segments with Terminal Setand we returnno otherwise.
5 Hardness for Longest Path and Cycle above Degeneracy
In this section we complement Theorems 3 and 2 by some hardness observations.
I Proposition 15 (?). 2 Longest Path Above Degeneracy is NP-complete even if k = 2 and Longest Cycle Above Degeneracy is NP-complete even for connected graphs and k= 2.
Recall that a graph Ghas a path with at least dg(G) + 1 vertices and if dg(G) ≥2, thenGhas a cycle with at least dg(G) + 1 vertices. Moreover, such a path or cycle can be constructed in polynomial (linear) time. Hence, Proposition 15 gives tight complexity bounds. Nevertheless, the construction used to show hardness forLongest Path Above Degeneracyuses a disconnected graph, and the graph constructed to show hardness for Longest Cycle Above Degeneracyhas a cut vertex. Hence, it is natural to consider Longest Path Above Degeneracyfor connected graphs andLongest Cycle Above Degeneracyfor 2-connected graphs. We show in Theorems 3 and 2 that these problems are FPT when parameterized byk in these cases. Here, we observe that the lower bound dg(G) that is used for the parameterization is tight in the following sense.
IProposition 16. For any0< ε <1, it isNP-complete to decide whether a connected graph Gcontains a path with at least(1 +ε)dg(G)vertices and it isNP-complete to decide whether a2-connected graphG contains a cycle with at least(1 +ε)dg(G)vertices.
Proof. Let 0< ε <1.
First, we consider the problem about a path with (1 +ε)dg(G) vertices. We reduce Hamiltonian Paththat is well-known to be NP-complete (see [15]). LetGbe a graph withn≥2 vertices. We construct the graphG0 as follows.
Construct a copy ofG.
Letp= 2dnεeand constructppairwise adjacent verticesu1, . . . , up. For eachv∈V(G), construct an edge vu1.
Letq=d(1 +ε)(p−1)−(n+p)e. Construct vertices w1, . . . , wq and edgesu1w1, wqu2
andwi−1wi fori∈ {2, . . . , q}.
Notice thatq = d(1 +ε)(p−1)−(n+p)e =d2εdnεe −n−1−εe ≥ dn−1−εe ≥ 1 as n≥2. Observe also that Gis connected. We claim thatGhas a Hamiltonian path if and only ifG0 has a path with at least (1 +ε)dg(G0) vertices. Notice that dg(G0) =p−1 and
|V(G0)|=n+p+q=d(1 +ε)dg(G0)e. Therefore, we have to show thatGhas a Hamiltonian path if and only ifG0has a Hamiltonian path. Suppose thatGhas a Hamiltonian pathPwith an end-vertexv. Consider the pathQ=vu1w1. . . wqu2u3. . . up. Clearly, the concatenation ofP andQis a Hamiltonian path inG0. Suppose thatG0 has a Hamiltonian path P. Since u1 is a cut vertex ofG0, we obtain thatP has a subpath that is a Hamiltonian path inG.
Consider now the problem about a cycle with at least (1 +ε)dg(G) vertices. We again reduceHamiltonian Path and the reduction is almost the same. LetGbe a graph with n≥2 vertices. We construct the graphG0 as follows.
Construct a copy ofG.
Letp= 2dnεeand constructppairwise adjacent verticesu1, . . . , up. For eachv∈V(G), construct edgesvu1 andvu2.
Letq=d(1 +ε)(p−1)−(n+p)e. Construct vertices w1, . . . , wq and edgesu2w1, wqu3
andwi−1wi fori∈ {2, . . . , q}.
As before, we have thatq≥1. Notice additionally thatp≥3, i.e., the vertexu3 exists. It is straightforward to see thatG0 is 2-connected. We claim thatGhas a Hamiltonian path if and only ifG0 has a cycle with at least (1 +ε)dg(G0) vertices. We have that dg(G0) =p−1 and
|V(G0)|=d(1 +ε)dg(G0)e. Hence, we have to show thatGhas a Hamiltonian path if and only ifG0 has a Hamiltonian cycle. Suppose that Ghas a Hamiltonian pathP with end-vertices xandy. Consider the pathQ=xu2w1. . . wqu3u4. . . upy. Clearly,P andQtogether form a Hamiltonian cycle inG0. Suppose thatG0 has a Hamiltonian cycleC. Since{u1, u2}is a cut set ofG0, we obtain thatC contains a path that is a Hamiltonian path ofG. J
6 Conclusion
We considered the lower bound dg(G) + 1 for the number of vertices in a longest path or cycle in a graphG. It would be interesting to consider the lower bounds given in Theorems 4 and 5. More precisely, what can be said about the parameterized complexity of the variants of Long Path (Cycle) where given a (2-connected) graphGand k∈N, the task is to check whetherGhas a path (cycle) with at least 2δ(G) +kvertices? Are these problems FPT when parameterized byk? It can be observed that the bound 2δ(G) is “tight”. That is, for any 0< ε <1, it is NP-complete to decide whether a connected (2-connected)Ghas a path (cycle) with at least (2 +ε)δ(G) vertices. See also [30] for related hardness results.
References
1 Noga Alon, Gregory Gutin, Eun Jung Kim, Stefan Szeider, and Anders Yeo. Solving MAX-r- SAT Above a Tight Lower Bound. InProceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 511–517. SIAM, 2010.
2 Ivona Bezáková, Radu Curticapean, Holger Dell, and Fedor V. Fomin. Finding Detours is Fixed- parameter Tractable.CoRR, abs/1607.07737, 2016. URL:http://arxiv.org/abs/1607.07737, arXiv:1607.07737.
3 Ivona Bezáková, Radu Curticapean, Holger Dell, and Fedor V. Fomin. Finding Detours is Fixed-Parameter Tractable. In44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, volume 80 ofLIPIcs, pages 54:1–54:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017.
4 Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Narrow sieves for parameterized paths and packings. CoRR, abs/1007.1161, 2010. URL:http://arxiv.org/
abs/1007.1161.
5 Hans L. Bodlaender. On Linear Time Minor Tests with Depth-First Search. J. Algorithms, 14(1):1–23, 1993. doi:10.1006/jagm.1993.1001.
6 Jianer Chen, Joachim Kneis, Songjian Lu, Daniel Mölle, Stefan Richter, Peter Rossmanith, Sing-Hoi Sze, and Fenghui Zhang. Randomized divide-and-conquer: improved path, matching, and packing algorithms. SIAM J. Comput., 38(6):2526–2547, 2009. doi:10.1137/080716475.
7 Jianer Chen, Songjian Lu, Sing-Hoi Sze, and Fenghui Zhang. Improved algorithms for path, matching, and packing problems. InProceedings of the18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 298–307. SIAM, 2007.
8 Robert Crowston, Mark Jones, Gabriele Muciaccia, Geevarghese Philip, Ashutosh Rai, and Saket Saurabh. Polynomial Kernels for lambda-extendible Properties Parameterized Above the Poljak-Turzik Bound. InIARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 24 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 43–54, Dagstuhl, Germany, 2013. Schloss Dagstuhl–Leibniz- Zentrum fuer Informatik.
9 Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015.
10 G. A. Dirac. Some theorems on abstract graphs. Proc. London Math. Soc. (3), 2:69–81, 1952.
11 P. Erdős and T. Gallai. On maximal paths and circuits of graphs. Acta Math. Acad. Sci.
Hungar, 10:337–356 (unbound insert), 1959.
12 Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms. J. ACM, 63(4):29:1–29:60, 2016. doi:10.1145/2886094.
13 Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Long directed (s,t)-path: FPT algorithm. Inf. Process. Lett., 140:8–12, 2018. doi:10.1016/j.ipl.
2018.04.018.
14 Harold N. Gabow and Shuxin Nie. Finding a long directed cycle. ACM Transactions on Algorithms, 4(1), 2008. doi:10.1145/1328911.1328918.
15 M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
16 Shivam Garg and Geevarghese Philip. Raising The Bar For Vertex Cover: Fixed-parameter Tractability Above a Higher Guarantee. InProceedings of the Twenty-Seventh Annual ACM- SIAM Symposium on Discrete Algorithms (SODA), pages 1152–1166. SIAM, 2016. doi:
10.1137/1.9781611974331.ch80.
17 Gregory Gutin, Eun Jung Kim, Michael Lampis, and Valia Mitsou. Vertex Cover Problem Parameterized Above and Below Tight Bounds.Theory of Computing Systems, 48(2):402–410, 2011. doi:10.1007/s00224-010-9262-y.
18 Gregory Gutin, Leo van Iersel, Matthias Mnich, and Anders Yeo. Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables. J. Computer and System Sciences, 78(1):151–163, 2012. doi:10.1016/j.
jcss.2011.01.004.
19 Gregory Z. Gutin and Viresh Patel. Parameterized Traveling Salesman Problem: Beating the Average. SIAM J. Discrete Math., 30(1):220–238, 2016.
20 Gregory Z. Gutin, Arash Rafiey, Stefan Szeider, and Anders Yeo. The Linear Arrangement Problem Parameterized Above Guaranteed Value. Theory Comput. Syst., 41(3):521–538, 2007.
doi:10.1007/s00224-007-1330-6.
21 Frank Harary. A characterization of block-graphs. Canad. Math. Bull., 6:1–6, 1963.
22 Falk Hüffner, Sebastian Wernicke, and Thomas Zichner. Algorithm Engineering for Color- Coding with Applications to Signaling Pathway Detection. Algorithmica, 52(2):114–132, 2008.
doi:10.1007/s00453-007-9008-7.
23 Joachim Kneis, Daniel Mölle, Stefan Richter, and Peter Rossmanith. Divide-and-Color. In Proceedings of the 34th International Workshop Graph-Theoretic Concepts in Computer Science (WG), volume 4271 ofLecture Notes in Computer Science, pages 58–67. Springer, 2008.
24 Ioannis Koutis. Faster Algebraic Algorithms for Path and Packing Problems. InProceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP), volume 5125 ofLecture Notes in Comput. Sci., pages 575–586. Springer, 2008.
25 Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. Faster Parameterized Algorithms Using Linear Programming. ACM Trans. Al- gorithms, 11(2):15:1–15:31, 2014. doi:10.1145/2566616.
26 Meena Mahajan and Venkatesh Raman. Parameterizing above Guaranteed Values: MaxSat and MaxCut.J. Algorithms, 31(2):335–354, 1999.
27 Meena Mahajan, Venkatesh Raman, and Somnath Sikdar. Parameterizing above or below guaranteed values.J. Computer and System Sciences, 75(2):137–153, 2009. doi:10.1016/j.
jcss.2008.08.004.
28 David W. Matula and Leland L. Beck. Smallest-Last Ordering and clustering and Graph Coloring Algorithms. J. ACM, 30(3):417–427, 1983. doi:10.1145/2402.322385.
29 B. Monien. How to find long paths efficiently. InAnalysis and design of algorithms for combinatorial problems (Udine, 1982), volume 109 of North-Holland Math. Stud., pages 239–254. North-Holland, Amsterdam, 1985. doi:10.1016/S0304-0208(08)73110-4.
30 Ingo Schiermeyer. Problems remaining NP-complete for sparse or dense graphs.Discussiones Mathematicae Graph Theory, 15(1):33–41, 1995. doi:10.7151/dmgt.1004.
31 Dekel Tsur. Faster deterministic parameterized algorithm for k-Path. CoRR, abs/1808.04185, 2018. arXiv:1808.04185.
32 Ryan Williams. Finding Paths of LengthkinO∗(2k) Time.Inf. Process. Lett., 109(6):315–318, 2009.
33 Meirav Zehavi. A randomized algorithm for long directed cycle.Inf. Process. Lett., 116(6):419–
422, 2016. doi:10.1016/j.ipl.2016.02.005.
