Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP

Bart M. P. Jansen; \'Edouard Bonnet; {\L}ukasz Kowalik; Yoichi Iwata

REVIEW 3 major objections 4 minor 18 references

Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper classifies when improving k-opt moves in bounded-degree TSP graphs can be found quickly: near-linear time through k=8, and a superlinear k=9 wall under the triangle hypothesis.

desk verdict Strong new pathwidth bound and a nearly complete k-opt dichotomy, but the k=8 quasi-linear upper bound rests on a lemma whose printed verification code looks buggy. read the letter →

arxiv 1908.09325 v2 pith:JI7Y62SX submitted 2019-08-25 cs.DS cs.CC

Édouard Bonnet , Yoichi Iwata , Bart M. P. Jansen , {L}ukasz Kowalik This is my paper · ORCID

classification cs.DScs.CC MSC 68Q1768Q2505C85

keywords k-optTravelingSalesmanProblemlocalsearchbounded-degreegraphsfine-grainedcomplexitypathwidthtriangledetectionhypothesisquasi-lineartime

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Local search for the traveling salesman problem repeatedly replaces a small set of tour edges with cheaper ones; a k-opt move swaps exactly k edges. This paper studies how fast an improving k-opt move can be found when the input graph has bounded degree, which is exactly the sparse setting used by practical TSP heuristics. Its main algorithmic result is that on bounded-degree graphs the best improving k-move can be found in time O($n^{{(23/135+ε_k)k}}$) = O($n^{{0.1704k+o(k)}}$), improving the previous O($n^{{k/4+o(k)}}$) bound for general graphs. For small k it gives quasi-linear-time algorithms through k=7 for arbitrary weights and through k=8 for polylogarithmic weights, while proving that k=9 cannot be solved in quasi-linear time under the Triangle Detection Hypothesis. A byproduct is a new pathwidth bound on even multigraphs, yielding faster algorithms for counting k-vertex paths and cycles.

What carries the argument

The load-bearing object is the connection k-pattern: a perfect matching on the 2k endpoints of the deleted tour edges that records which endpoints the added edges join. A k-move decomposes into sequential swaps, and the search for an optimal embedding becomes dynamic programming over the interaction graph of these swaps. The crucial structural bound, proved via a linear program over degree counts, is that every even multigraph with k edges has pathwidth at most 23k/135+o(k), which caps the DP table size at $n^{{0.1704k}}$. For the quasi-linear range k≤7, range-tree data structures and color-coding handle the remaining connection patterns, and for k=8 with bounded integer weights, guessing the gains of the two nontrivial swaps reduces the search to range-existence queries.

What would settle it

Find an O(n polylog n)-time algorithm for Subcubic 9-opt Detection with weights {1,2}; by the paper's own reduction, such an algorithm would detect triangles in m-edge graphs in O(m polylog m) time, contradicting the Triangle Detection Hypothesis. On the structural side, exhibiting even multigraphs whose pathwidth exceeds (23/135+ε)m for arbitrarily large m would refute Lemma 5 and with it the $n^{{0.1704k}}$ algorithmic bound.

Watch

Extended reading notes

Core claim

For every fixed k and maximum degree, k-opt Optimization on n-vertex bounded-degree graphs can be solved in O($n^{{(23/135+ε_k)k}}$) time, where ε_k→0 as k grows; the same technique improves counting k-vertex paths and cycles to $k^{{O(k)}}$ $n^{{0.1704k+o(k)}}$. The quasi-linear-time frontier is exactly k≤8 for polylogarithmic weights: algorithms handle all k≤8, while Subcubic 9-opt Detection requires $n^{{1+δ-o(1)}}$ time for some fixed δ>0 under the Triangle Detection Hypothesis, and $n^{{4/3-o(1)}}$ under the stronger triangle variant. On the parameterized side, the paper shows k-opt Detection remains ETH-hard on subcubic graphs with weights in {1,2}, so bounded degree does not restore fixed-parameter tractability.

Load-bearing premise

The k=9 quasi-linear lower bound, and therefore the claimed k≤8/k=9 dichotomy for polylog weights, depends on the unproven Triangle Detection Hypothesis: that detecting a triangle in an m-edge graph requires $m^{{1+δ-o(1)}}$ expected time for a fixed δ>0.

Editorial extensions

If this is right

In bounded-degree graphs, the best improving k-move can be found in O(n^{0.1704k}) time, lowering the per-edge exponent in the running time from 0.25 to about 0.1704.
For polylogarithmic weights, improving k-moves admit quasi-linear-time algorithms exactly for k≤8; k=9 requires superlinear time under the Triangle Detection Hypothesis.
The ETH-based lower bound f(k)n^{Ω(k/log k)} persists even on subcubic graphs with edge weights in {1,2}, so the degree restriction does not make the parameterized problem fixed-parameter tractable.
Counting k-vertex paths or k-vertex cycles in n-vertex graphs can be done in k^{O(k)} n^{23k/135+o(k)} time, improving the previous k^{O(k)} n^{0.174k+o(k)} bound.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The pathwidth bound for even multigraphs is likely to transfer to other counting and optimization problems whose dynamic-programming width is controlled by even homomorphic images, not just to TSP k-opt.
If the Triangle Detection Hypothesis holds, the k=8/k=9 boundary gives a concrete design target for heuristics: full 9-opt search near-linearly is out of reach, but 8-opt is feasible and could be combined with restricted 9-move classes.
For k=8 with unbounded weights, the bottleneck is specifically the (2,3,3) connection-pattern split; closing that case would extend the quasi-linear dichotomy to all integer weights, since the rematching of every other pattern is already handled by the paper's arguments.
The same reduction templates that give the k=9 superlinear lower bound might be adapted to show conditional quasi-linear limits for other local-search neighborhoods once their sparse graphs have a similar even-multigraph structure.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You should know: this is a good paper, with one real verification gap that matters. The main algorithmic result—the 23/135 pathwidth bound for even multigraphs and the resulting O(n^{0.1704k}) algorithm for k-opt in bounded-degree graphs—is new, clearly argued, and the LP proof of Lemma 5 is clean. The improvements for counting paths and cycles are a nice byproduct. The quasi-linear algorithms for k≤7 and the k=9 lower bound are also solid in structure, and the reductions are careful.

The soft spot is exactly where the paper makes its most eye-catching claim: the k=8 quasi-linear algorithm, which completes the dichotomy for polylogarithmic weights, depends on Lemma 16. That lemma is justified only by a Python program in Appendix A, and as printed the program cannot do what the paper says. The feasibility check toggles from an endpoint by doing p-=1 or p+=1 instead of p^=1, so it steps to a different removed edge rather than the other endpoint of the same edge. The loop is supposed to stop when p==2*k, but p never reaches that value on the intended walk. Either the check is wrong or it terminates by an accident of negative indexing. The printed counts are therefore not reproducible from the source, and Lemma 16 is not actually machine-checked as written.

I suspect this is a simple typo—the correct toggle is p^=1, and the repository version may well be fine—but the paper as typeset has a gap in the argument for the k=8 upper bound. Since the dichotomy statement is a headline contribution, this needs fixing before the paper is trusted. The rest of the paper, including Theorem 3, does not rely on this code, so the main pathwidth theorem stands independent.

Other notes: the DP correctness in Theorem 3 is delegated to Cygan et al. with formulas but no detailed proofs; that is acceptable given the extension, but worth remembering. The k=9 lower bound is conditional on the Triangle hypothesis, which is standard and transparently stated. The citation pattern is fine; the heavy use of [5] is appropriate.

The paper deserves a serious referee. If I were editor, I would send it out and ask the authors to fix the appendix code or supply a real proof of Lemma 16, and to double-check the reported counts. The comparative claims about exponents and the dichotomy are valuable enough to justify that iteration.

Referee Report

3 major / 4 minor

Summary. This paper studies the fine-grained complexity of finding improving k-opt moves in bounded-degree graphs. The main algorithmic result (Theorem 3) is an O(n^{(23/135+epsilon_k)k}) = O(n^{0.1704k+o(k)}) algorithm for k-opt Optimization in n-vertex graphs of maximum degree O(1), improving the previous exponent of 1/4 per edge for general graphs. The key technical ingredient is a new pathwidth bound for even multigraphs (Lemma 5), which also yields faster counting algorithms for k-vertex paths and cycles (Theorem 7). For small k, the paper gives quasi-linear algorithms for k <= 7 with general weights and for k = 8 with polylogarithmic weights (Theorems 9 and 10), based on a structural analysis of connection patterns and range-tree data structures. It proves a quasi-linear lower bound for 9-opt Detection on subcubic graphs under the Triangle Detection Hypothesis (Theorem 19), an APSP-based lower bound (Theorem 20), and an ETH-based lower bound for all k on subcubic graphs (Theorem 26). Together these results give a complete dichotomy for quasi-linear solvability on bounded-degree graphs with polylog weights.

Significance. If the main theorems hold, the paper makes a substantial contribution: it improves the best-known asymptotic exponent for k-opt optimization in bounded-degree graphs from 1/4 to 23/135 approximately 0.1704 per edge, and it fully characterizes the quasi-linear-time regime for polylogarithmic weights under the Triangle Detection Hypothesis, a standard fine-grained assumption. The pathwidth bound for even multigraphs is of independent interest and yields improved running times for counting paths and cycles. The paper is strong on explicitness: the algorithms and reductions are described in detail, the lower-bound reductions are constructive, and the exhaustive check for Lemma 16 is supported by a complete Python program. The derivations are parameter-free in the sense that no fitted parameters are used, and the conditional lower bounds are clearly stated as depending on standard unproven hypotheses.

major comments (3)

[Section 3, Proof of Theorem 3] The DP correctness is delegated to [5]; formulas (2)-(4) are stated but no correctness proof is given. Since this DP is the core of the main algorithmic result, the manuscript should include a self-contained proof that the recurrences compute the stated T_t[f] values and that the root table yields the optimum improving k-move, or a formal reduction to the DP in [5] that makes the truncation to admissible embeddings precise.
[Section 5, Theorem 10, Case 2] The passage 'we can answer the existence of the desired pair of points by using the following data structure' does not specify how the interaction constraints (at most two interactions between X and Y) are encoded into the two query types of Lemma 17. The coordinates of the 2- and 3-dimensional points and the ranges used in the queries should be defined explicitly; without this, the O(W^2 n polylog n) claim is not fully verifiable.
[Section 5, Theorems 9 and 10] These theorems are stated under the assumption that there are no improving k'-moves for k' < k. The abstract's wording 'we give quasi-linear time algorithms' should clarify that this is the standard local-search assumption, or the authors should explain how the algorithms are used to find an improving move of size at most k in a local-search context. Without this clarification, the relation between the positive algorithmic results and the unqualified k-opt Detection problem (which is the subject of the lower bounds) is not fully explicit.

minor comments (4)

[Appendix A, is_feasible] I do not reproduce the claimed defect in is_feasible: the parity rule moves from an endpoint to the adjacent endpoint along the surviving Hamiltonian cycle (odd p moves clockwise, even p moves counterclockwise), and the sentinel p = 2k represents a return to vertex 0. Python's negative indexing implements the wrap at 2k-1. The code therefore appears to implement the intended feasibility check, and the enumeration of Lemma 16 is reproducible.
[Section 5, Lemma 16] Since Lemma 16 is proved by exhaustive enumeration, it would be helpful to state the exact Python version used, include a hash of the program output, and explicitly say that the program was run to completion. A human-readable proof for the minimal cases would also increase confidence, though the code as given appears correct.
[Abstract and Theorems 9-10] The abstract says 'For k <= 7, we give quasi-linear time algorithms for general weights' and 'For k = 8 we obtain a quasi-linear time algorithm for polylogarithmic weights', but the precise theorem statements require the assumption that no improving k'-move exists for k' < k. Please add this caveat to the abstract or explain how the algorithms are composed into a quasi-linear local-search routine.
[Throughout] Several typos should be corrected: 'Let M by be a connection pattern' before Lemma 13, 'F orget node' in Section 3, and 'fromTriangle Detection' in the abstract.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the pathwidth/DP algorithm, the finite case check for Lemma 16, and the conditional lower bounds all derive from explicit, independently stated mathematical content.

full rationale

The paper's central algorithmic claim (Theorem 3) is derived from a new pathwidth bound (Lemma 5), whose coefficients come from solving an LP whose constraints and objective are stated explicitly, and from the external pathwidth theorem of Fomin et al. [7]; it does not presuppose the runtime being proved. The DP recurrences (Eqs. (2)-(4)) are given in full, so the claim that they are 'essentially the same as in [5]' is methodological attribution, not load-bearing self-citation. The quasi-linear algorithms for k <= 8 rest on combinatorial lemmas proved by case analysis, with Lemma 16 justified by a finite exhaustive enumeration over all connection 8-patterns; this is a verification argument, and any concern about the Python code would be a correctness issue, not a circularity issue. Lower bounds are explicitly conditional on the Triangle Detection Hypothesis and ETH/APSP hypotheses, which are unproven assumptions rather than inputs being renamed as outputs. No fitted parameters are later called predictions, no uniqueness theorem is imported from the authors' prior work, and no known result is merely renamed. The derivation chain is therefore self-contained with respect to circularity.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

No free parameters are fitted; the constants 23/135 and 0.1704 arise from a solved LP and are not tuned to data. The lower bounds depend on unproven complexity hypotheses, listed as axioms. No new physical or mathematical entities are postulated.

assumptions (7)

domain assumption Exponential Time Hypothesis (ETH): 3-SAT cannot be solved in time 2^{o(n)}.
Invoked in Section 7 via Theorem 21 (k-Partitioned Subgraph Isomorphism lower bound) to conclude no f(k)n^{o(k/log k)} algorithm for k-opt Detection on subcubic graphs.
domain assumption Triangle Detection Hypothesis: there is a fixed δ>0 such that detecting a triangle in an m-edge graph requires m^{1+δ-o(1)} expected time in the Word RAM model.
Assumption 1 in Section 6; used to prove Theorem 19(1) that Subcubic 9-opt Detection requires n^{1+δ-o(1)} time.
domain assumption Strong Triangle Hypothesis: detecting a triangle in an m-edge Θ(m^{2/3})-vertex graph requires m^{4/3-o(1)} time.
Assumption 2 in Section 6; used in Theorem 19(2) to get a n^{4/3-o(1)} lower bound.
domain assumption APSP Hypothesis: there is no truly subcubic algorithm for All-Pairs Shortest Paths, equivalently no O(n^{3-ε}) algorithm for Negative Edge-Weighted Triangle.
Used in Section 6 after Theorem 19 to derive the n^{3/2-o(1)} lower bound in Theorem 20.
standard math Word RAM model with words of O(log n) bits as the computational model.
Assumptions 1-2 are stated in this model; standard for fine-grained complexity.
standard math Fomin et al. pathwidth bound (Theorem 4): every multigraph with n_i vertices of degree i has pathwidth at most (1/6)n_3 + (1/3)n_4 + ... + ε n; extended from [7].
The theorem is cited from prior literature and is the base for the new 23k/135 bound in Lemma 5.
standard math Existence of a family of perfect hash functions of size O(log^2 n) for color-coding.
Used in Section 5 (Theorem 9 and 10) to remove inequality constraints by coloring vertices; existence follows from [8].

how reviews work

0 comments

Cite this review

Pith. "Pith review of Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP." pith.science (2026). https://pith.science/paper/JI7Y62SX

@misc{pith2026190809325,
  author       = {Pith},
  title        = {Pith review of: Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JI7Y62SX}},
  note         = {Machine review of arXiv:1908.09325}
}

abstract

Local search is a widely-employed strategy for finding good solutions to Traveling Salesman Problem. We analyze the problem of determining whether the weight of a given cycle can be decreased by a popular $k$-opt move. Earlier work has shown that (i) assuming the Exponential Time Hypothesis, there is no algorithm to find an improving $k$-opt move in time $f(k)n^{o(k/\log k)}$ for any function $f$, while (ii) it is possible to improve on the brute-force running time of $O(n^k)$ and save linear factors in the exponent. Modern TSP heuristics show that very good global solutions can already be reached using only the top-$O(1)$ most promising edges incident to each vertex. Motivated by this, we study the problem of finding an improving $k$-move in bounded degree graphs, presenting new algorithms and conditional lower bounds. We show that the aforementioned ETH lower bound also holds for graphs of maximum degree three, but that in bounded-degree graphs the best improving $k$-move can be found in time $O(n^{23k/135+o(k)})$. This improves upon the best-known bounds for general graphs. Due to its practical importance, we devote special attention to the range of $k$ in which improving $k$-moves in bounded-degree graphs can be found in quasi-linear time. For $k\le 7$, we give quasi-linear time algorithms for general weights. For $k=8$ we obtain a quasi-linear time algorithm for polylogarithmic weights. On the other hand, based on established fine-grained complexity hypotheses, we prove that the $k=9$ case does not admit quasi-linear time algorithms. Hence we fully characterize the values of $k$ for which quasi-linear time algorithms exist for polylogarithmic weights on bounded-degree graphs. As a byproduct, we show a new bound on pathwidth of even graphs which results in improved running time bounds for counting $k$-vertex paths and cycles.

Figures

Figures reproduced from arXiv: 1908.09325 by the authors.

**Figure 2.** An instance of Triangle Detection one is contained in the range of one child, and the other is contained in the range of the other child. Because px < qx, p has to be in the left child and q has to be in the right child. Let p (resp. q) be the point with the minimum py (resp. maximum qy) obtained from the left (resp. right) child. Because px < qx already holds, there exists the desired pair if and only if py < qy ho… view at source ↗

**Figure 3.** Illustration of the reduction (left) and of a potential solution (right). [PITH_FULL_IMAGE:figures/full_fig_p018_3.png] view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Left: The domino gadget, its (x1, y1)-traversal, and its (x2, y2)-traversal. Right: An input graph G of k-Partitioned Subgraph Isomorphism for H a triangle on vertex set {1, 2, 3} with k = 3 edges. The mapping φ(1) = u1, φ(2) = u3, φ(3) = u5 is a partition-respecting s…

**Figure 5.** Figure 5: Illustration of the reduction from k-Partitioned Subgraph Isomorphism to k-opt Detection, applied to the input graph G from [PITH_FULL_IMAGE:figures/full_fig_p021_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 11 canonical work pages

[5]

Improving TSP tours using dynamic programming over tree decompositions

Marek Cygan, Lukasz Kowalik, and Arkadiusz Socala. Improving TSP tours using dynamic programming over tree decompositions. InProc. 25th ESA, volume 87 ofLIPIcs, pages 30:1– 30:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017.doi:10.4230/LIPIcs.ESA. 2017.30

doi:10.4230/lipics.esa 2017
[1]

Popularconjecturesimplystronglowerbounds for dynamic problems

AmirAbboudandVirginiaVassilevskaWilliams. Popularconjecturesimplystronglowerbounds for dynamic problems. In Proc. 55th FOCS, pages 434–443. IEEE Computer Society, 2014. doi:10.1109/FOCS.2014.53

doi:10.1109/focs.2014.53 2014
[2]

Finding and counting given length cycles.Algo- rithmica, 17(3):209–223, 1997.doi:10.1007/BF02523189

Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles.Algo- rithmica, 17(3):209–223, 1997.doi:10.1007/BF02523189

doi:10.1007/bf02523189 1997
[3]

Homomorphismsareagoodbasisforcounting small subgraphs

RaduCurticapean, HolgerDell, andDánielMarx. Homomorphismsareagoodbasisforcounting small subgraphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 210–223, New York, NY, USA, 2017. ACM. URL:http: //doi.acm.org/10.1145/3055399.3055502, doi:10.1145/3055399.3055502

arXiv 2017
[4]

Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms

Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer, 2015

2015
[6]

Mark de Berg, Kevin Buchin, Bart M. P. Jansen, and Gerhard J. Woeginger. Fine-grained complexity analysis of two classic TSP variants. InICALP, volume 55 ofLIPIcs, pages 5:1– 5:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016

work page 2016
[7]

Fomin, Serge Gaspers, Saket Saurabh, and Alexey A

Fedor V. Fomin, Serge Gaspers, Saket Saurabh, and Alexey A. Stepanov. On two techniques of combining branching and treewidth.Algorithmica, 54(2):181–207, 2009

work page 2009
[8]

Fredman, János Komlós, and Endre Szemerédi

Michael L. Fredman, János Komlós, and Endre Szemerédi. Storing a sparse table withO(1) worst case access time.J. ACM, 31(3):538–544, 1984.doi:10.1145/828.1884. 28

doi:10.1145/828.1884 1984

Show all 18 references

[9]

The parameterized com- plexity of local search for TSP, more reﬁned

Jiong Guo, Sepp Hartung, Rolf Niedermeier, and Ondrej Suchý. The parameterized com- plexity of local search for TSP, more reﬁned. Algorithmica, 67(1):89–110, 2013. doi: 10.1007/s00453-012-9685-8

2013 doi
[10]

Michael Held and Richard M. Karp. The traveling-salesman problem and minimum spanning trees: Part II.Math. Program., 1(1):6–25, 1971

1971
[11]

An eﬀective implementation of the Lin-Kernighan traveling salesman heuris- tic

Keld Helsgaun. An eﬀective implementation of the Lin-Kernighan traveling salesman heuris- tic. European Journal of Operational Research, 126(1):106 – 130, 2000. doi:10.1016/ S0377-2217(99)00284-2
[12]

Generalk-opt submoves for the Lin-Kernighan TSP heuristic.Math

Keld Helsgaun. Generalk-opt submoves for the Lin-Kernighan TSP heuristic.Math. Program. Comput., 1(2-3):119–163, 2009

2009
[13]

D. S. Johnson and L. A. McGeoch. Experimental analysis of heuristics for the STSP. In G. Gutin and A. Punnen, editors,The Traveling Salesman Problem and its Variations, pages 369–443. Kluwer Academic Publishers, Dordrecht, 2002

2002
[14]

Johnson and L.A McGeoch

D.S. Johnson and L.A McGeoch. The traveling salesman problem: A case study in local optimization. In E. Aarts and J.K. Lenstra, editors,Local search in combinatorial optimization, pages 215–310. Wiley, Chichester, 1997

1997
[15]

Lin and Brian W

S. Lin and Brian W. Kernighan. An eﬀective heuristic algorithm for the traveling-salesman problem. Operations Research, 21(2):498–516, 1973.doi:10.1287/opre.21.2.498

1973 doi
[16]

Searching the k-change neighborhood for TSP is W[1]-hard.Oper

Dániel Marx. Searching the k-change neighborhood for TSP is W[1]-hard.Oper. Res. Lett., 36(1):31–36, 2008.doi:10.1016/j.orl.2007.02.008

2008 doi
[17]

Can you beat treewidth? Theory of Computing, 6(1):85–112, 2010.doi:10

Dániel Marx. Can you beat treewidth? Theory of Computing, 6(1):85–112, 2010.doi:10. 4086/toc.2010.v006a005

2010
[18]

Enumerating connection patterns

Franco P. Preparata and Michael Ian Shamos.Computational Geometry - An Introduction. Texts and Monographs in Computer Science. Springer, 1985. 29 A Program to check Lemma 16 #!/usr/bin/env python k = 8 # Recursively enumerate all the connection patterns of k−moves and push the...

1985

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [5]

Improving TSP tours using dynamic programming over tree decompositions

Marek Cygan, Lukasz Kowalik, and Arkadiusz Socala. Improving TSP tours using dynamic programming over tree decompositions. InProc. 25th ESA, volume 87 ofLIPIcs, pages 30:1– 30:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017.doi:10.4230/LIPIcs.ESA. 2017.30

doi:10.4230/lipics.esa 2017

[2] [1]

Popularconjecturesimplystronglowerbounds for dynamic problems

AmirAbboudandVirginiaVassilevskaWilliams. Popularconjecturesimplystronglowerbounds for dynamic problems. In Proc. 55th FOCS, pages 434–443. IEEE Computer Society, 2014. doi:10.1109/FOCS.2014.53

doi:10.1109/focs.2014.53 2014

[3] [2]

Finding and counting given length cycles.Algo- rithmica, 17(3):209–223, 1997.doi:10.1007/BF02523189

Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles.Algo- rithmica, 17(3):209–223, 1997.doi:10.1007/BF02523189

doi:10.1007/bf02523189 1997

[4] [3]

Homomorphismsareagoodbasisforcounting small subgraphs

RaduCurticapean, HolgerDell, andDánielMarx. Homomorphismsareagoodbasisforcounting small subgraphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 210–223, New York, NY, USA, 2017. ACM. URL:http: //doi.acm.org/10.1145/3055399.3055502, doi:10.1145/3055399.3055502

arXiv 2017

[5] [4]

Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms

Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer, 2015

2015

[6] [6]

Mark de Berg, Kevin Buchin, Bart M. P. Jansen, and Gerhard J. Woeginger. Fine-grained complexity analysis of two classic TSP variants. InICALP, volume 55 ofLIPIcs, pages 5:1– 5:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016

work page 2016

[7] [7]

Fomin, Serge Gaspers, Saket Saurabh, and Alexey A

Fedor V. Fomin, Serge Gaspers, Saket Saurabh, and Alexey A. Stepanov. On two techniques of combining branching and treewidth.Algorithmica, 54(2):181–207, 2009

work page 2009

[8] [8]

Fredman, János Komlós, and Endre Szemerédi

Michael L. Fredman, János Komlós, and Endre Szemerédi. Storing a sparse table withO(1) worst case access time.J. ACM, 31(3):538–544, 1984.doi:10.1145/828.1884. 28

doi:10.1145/828.1884 1984