Hitting Geodesic Intervals in Structurally Restricted Graphs

Hayato Takaike; Tatsuya Gima; Yasuaki Kobayashi; Yota Otachi; Yuto Okada

REVIEW 1 major objections 4 minor 29 references

Hitting Geodesic Intervals in Structurally Restricted Graphs

T0 review · 1 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

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

Pith's one-line read Hitting geodesic intervals is NP-hard on near-path graphs, yet fixed-parameter tractable when k joins structural parameters.

desk verdict Has a real, repairable gap in the modular-width proof; the rest is solid and worth serious referee time. read the letter →

arxiv 2509.01413 v1 pith:ESM6UZ27 submitted 2025-09-01 cs.DS

Tatsuya Gima , Yasuaki Kobayashi , Yuto Okada , Yota Otachi , Hayato Takaike This is my paper

classification cs.DS MSC 05C8568Q2768Q1768R10

keywords HittingGeodesicIntervalsTerminalmonitoringsetintervalStructuralgraphparametersParameterizedcomplexityNP-completenessFixed-parametertractabilityVertexintegrityandmodular-width

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

This paper maps the difficulty of Hitting Geodesic Intervals, a problem where given a graph, a list of terminal pairs, and a budget k, one asks whether k vertices can meet every shortest path connecting each pair. It shows the problem is NP-complete even on graphs that differ from a disjoint union of 5-vertex paths by a single added vertex, and even on graphs of bandwidth 4 with maximum degree 5. It then proves fixed-parameter tractable algorithms—running time polynomial in the graph but exponential only in the chosen parameter—for the weighted version combined with k plus vertex integrity, for k plus modular-width, and for the parameter given by the minimum vertex multiway cut of the terminal set. These positive results are matched by two W[2]-completeness results (the parameterized analogue of NP-completeness) showing that nearby parameters remain intractable. The result is a fairly complete picture of where the structure of a graph makes hitting geodesic intervals easy or hard.

What carries the argument

The central object is the geodesic interval I_G[u,v], the set of all vertices lying on at least one shortest path between terminals u and v; the problem asks for a minimum hitting set of these intervals. Hardness is carried by a 3-Coloring gadget: each vertex of the 3-Coloring instance becomes a short path or triangle, the three colors are encoded by which end-vertices the hitting set selects, and edges become terminal pairs whose geodesic intervals force different color choices. For fixed-parameter tractability, the paper uses two mechanisms. One is a small separator Z whose removal leaves components with few terminals; after guessing how the solution behaves on pairs inside Z, remaining in

What would settle it

Run an exhaustive search over small graphs with a module partition and terminal families to test the key proof claim: after the two branching phases, every nonempty residual family inside one module has a hitting set of size 1. A single instance where two disjoint residual intervals remain in one module, with no vertex of an adjacent module lying in both, would show the substitution step used to justify that claim does not hold as written.

Watch

Extended reading notes

Core claim

At the center of the paper is a complexity classification. The authors reduce 3-Coloring to Hitting Geodesic Intervals on graphs one vertex away from a disjoint union of 5-vertex paths, one vertex away from a path, and one vertex away from a disjoint union of triangles, with the triangle gadget rewired to bandwidth 4 and maximum degree 5. In these gadgets, colors become choices of which side of a short path the hitting set selects, and edges become terminal pairs whose geodesics force different choices. On the algorithmic side, a separator-based algorithm for the weighted problem guesses how the solution interacts with pairs inside a small separator, compresses the remaining intervals, and a

Load-bearing premise

The modular-width algorithm's correctness rests on the claim that, after the branching phases, each leftover family of intervals inside one module (a set of vertices with identical outside neighbours) can always be hit by one vertex from a neighbouring module; if that substitution fails, the algorithm could reject a valid solution.

Editorial extensions

If this is right

The NP-completeness on graphs a single vertex away from a disjoint union of 5-vertex paths rules out fixed-parameter algorithms for many structural parameters when k is not part of the parameter, under standard complexity assumptions.
Weighted Hitting Geodesic Intervals becomes fixed-parameter tractable when parameterized by k plus vertex integrity, covering and extending the earlier vertex-cover-number result.
The same separator-based algorithm gives fixed-parameter tractability parameterized by the minimum vertex multiway-cut size of the terminal set, a parameter that is not explicitly plus k but still upper-bounds k.
The W[2]-completeness for the minimum vertex multicut size of the terminal pairs shows that the multiway-cut tractability is tight: replacing multiway cut by the weaker multicut changes the answer.
Even when every pair inside a single vertex set Q is a demand, the problem remains W[2]-complete parameterized by k, so restricting the terminal structure to all pairs of Q does not bypass parameterized intractability.

Reading between the lines

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

Beyond the paper, the separator-based algorithm suggests a practical route for real networks: if terminals are clustered so that a small cutset separates them, the weighted problem can be solved even on graphs with large treewidth by first guessing the cutset and then applying the sunflower reduction.
Beyond the paper, the open question of finding the separator Z uniformly may be attackable by a bounded-depth search on the terminal set rather than the graph-minor argument; if such an algorithm exists, the 'plus k' results would become fully constructive.
Beyond the paper, the hardness results imply that monitoring or facility-location applications on near-path or low-bandwidth networks cannot rely on the network's simple shape alone; the budget k or a terminal-separation parameter must be small for tractability.

Share X Bluesky LinkedIn Reddit HN

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

Quick take: this is a worthwhile paper with one real hole. The NP-hardness constructions and the W[2]-completeness results look correct and genuinely sharpen the boundary. The separator-based FPT framework in Theorem 4.2 is the best part: the T-equivalence compression plus sunflower argument is careful, and I did not find a gap there. The modular-width algorithm, however, has a proof bug as written.

The issue is the size-1 claim for residual families inside a module. After the first branching, each set J(u,v) has been updated by deleting every module outside M_S. So if u and v lie in M_i, an adjacent module M_j not in M_S has already been removed from J(u,v). The proof then builds S'_i = (S_i \ {v_i}) ∪ {v_j} and says v_j hits all J(u,v) ∈ I_i because dist(u,v)=2. But v_j is not in those updated sets. The substitution therefore does not hit the residual family, and the contradiction to maximality of |M_S| does not follow.

I suspect the theorem is true and the argument can be repaired: take S_i = S ∩ M_i rather than an arbitrary minimum hitting set, note that for any surviving J ∈ I_i all adjacent modules are outside M_S, and argue directly on the original geodesic intervals. That would give the needed contradiction when |S ∩ M_i| ≥ 2. But the paper does not say this, and the current proof is not valid. Since Theorem 4.1 is a headline positive result, this needs a real revision.

Smaller things: Theorem 3.3 has a dangling “deferred to the appendix” marker with no appendix in the arXiv text, and Corollary 3.2’s path-connection step is terse, though I think it is okay. The citation and bootstrapping are otherwise clean; the reductions start from 3-Coloring and Hitting Set, and the reuse of Aravind and Saxena is appropriate.

Bottom line: for anyone working on HGI or structural parameterizations of hitting problems, this is worth a serious read once the modular-width proof is repaired. I would send it to a careful referee now, with the expectation of major revision focused on Section 4.1.

Referee Report

1 major / 4 minor

Summary. The paper studies Hitting Geodesic Intervals (HGI) and its weighted variant WHGI. It proves NP-completeness on graphs of vertex-deletion distance 1 to disjoint unions of 5-vertex paths, to paths, and to disjoint unions of triangles, as well as on graphs of bandwidth 4 and maximum degree 5. It then gives fixed-parameter algorithms for HGI parameterized by k plus modular-width and for WHGI parameterized by k plus vertex integrity and by the minimum vertex multiway-cut size of the terminal vertices. It also proves W[2]-completeness for the parameterization by the minimum vertex multicut size of the terminal pairs and for the variant Hitting Pairwise Geodesic Intervals parameterized by k. The NP-hardness and W[2]-hardness reductions are carefully structured, but the proof of the modular-width FPT result contains a gap that needs to be repaired.

Significance. If the results are correct, they considerably sharpen the known complexity border for HGI. The negative results answer open questions of Aravind and Saxena and rule out FPT algorithms for many structural parameters when k is not part of the parameter. The positive results generalize earlier FPT results for neighborhood diversity and vertex cover number, and the W[2]-hardness results help delineate the parameter hierarchy between multiway cut and multicut parameters. The paper is commendably explicit about which parameters remain open. The main caveat is that the proof of Theorem 4.1, one of the headline positive results, is not valid as written; the rest of the paper appears technically sound.

major comments (1)

[Section 4.1] The proof that each nonempty residual family I_i admits a hitting set of size 1 is not established. After the first branching update, for a residual pair {u,v} with u,v in the same module M_i and {u,v} not an edge, the update rule deletes every module not in M_S from J(u,v). In particular, if M_j is an adjacent module not in M_S, then a vertex v_j in M_j is removed from J(u,v). The proof then claims that 'v_j∈M_j hits all J(u,v)∈I_i since dist_G(u,v)=2'; this is false for the reduced family I_i, because v_j is no longer an element of those updated sets. Consequently, the replacement S'_i=(S_i\{v_i})∪{v_j} is not shown to intersect the residual family, and the resulting set R is not shown to interrupt the original terminal pairs. The contradiction to the maximality of |M_S| is therefore unsupported. A correct argument would need to show directly that v_j lies in the original geodesic inte

minor comments (4)

[Section 3.3 (Theorem 3.3)] The text says 'The proofs of the claims marked with (⋆) are deferred to the appendix,' but no (⋆) markers appear in the proof and no appendix is included in the submitted manuscript. Please remove the sentence or add the promised material.
[Section 4.2 (Theorem 4.2)] In the bound on |I'|, the term |IY| is bounded by p^2, but there are only p(p−1)/2 pairs in (Z choose 2). The error is harmless, but the bound should be corrected.
[Section 4.2 (Theorem 4.2, terminal-in-Z modification)] When a terminal z in Z is replaced by a new leaf z', the argument says 'any path to z' must go through z.' This covers vertices on paths to z', but not the possibility that a solution chooses the endpoint z' itself. The authors should explicitly note that z' is dominated by z, so an optimal solution can be assumed not to contain z'; otherwise the reduction between the original and modified instances is not fully justified.
[Section 5 (Theorem 5.1)] The backward direction replaces a selected F_i by a neighbor u_j in F_i. This requires every set in the Hitting Set instance to be nonempty. Hitting Set remains hard with nonempty sets, but the assumption should be stated, or the empty-set case handled separately.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation found; the reductions and algorithms rest on external standard problems and known results, and the only notable flaw (the size-1 claim in Theorem 4.1) is a proof gap, not a circularity.

full rationale

All hardness results start from external standard problems: Theorem 3.1 and Theorem 3.3 reduce from 3-Coloring, and Theorems 5.1 and 5.2 reduce from Hitting Set. No step assumes the target result or a renamed version of it. The positive algorithms in Section 4 are self-contained branching/enumeration arguments using standard tools (Damaschke's enumeration, sunflower lemma, known FPT algorithms for vertex multiway cut and vertex multicut), and they do not fit parameters to data and then rename the fit as a prediction. The paper does not rely on self-citations by the current authors as load-bearing evidence; the cited prior work [2] by Aravind and Saxena is external and used only as a baseline. The suspicious point in Theorem 4.1's proof—the claim that every nonempty I_i has a hitting set of size 1—is not circular. The paper itself states that after the update, adjacent modules do not belong to M_S and hence J(u,v) is contained in M_i, yet it later says that a vertex v_j in an adjacent module M_j hits all J(u,v) in I_i; because the update deleted M_j from those residual sets, v_j is not an element of J(u,v). This is a gap in the correctness proof, but it is not an equivalence-by-construction, a fitted-input-called-prediction, or a self-citation chain. Therefore the circularity score is 0.

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

This is a parameterized complexity theory paper. It uses no fitted numerical parameters and introduces no new entities. All assumptions are standard background results in complexity theory and graph algorithms, each cited. The central claims stand on the correctness of the reductions and algorithms, not on any empirical or fitted input.

assumptions (7)

standard math Hitting Set is W[2]-complete parameterized by solution size
Used as the source problem in Theorems 5.1 and 5.2 (cited [8]).
standard math 3-Coloring is NP-complete
Used as the source problem in Theorems 3.1 and 3.3 (cited [17]).
standard math Sunflower lemma and d-Hitting Set kernelization algorithm
Used to bound the size of I_T in Theorem 4.2 (cited [14, 15]).
standard math Vertex Multiway Cut and Vertex Multicut are FPT parameterized by solution size
Used to obtain the separator Z in Corollaries 4.4, 4.5 and to establish the parameter in Theorem 5.1 (cited [4, 6, 22, 23]).
standard math Modular decomposition can be computed in linear time
Used in Theorem 4.1 to obtain the first-level module partition (cited [24]).
standard math Vertex integrity can be computed in O(ι^(ι+1) n) time
Used in Corollary 4.4 to find the vertex-integrity set (cited [13]).
standard math Edge-colored graph minor theorem
Used in the concluding remark for a nonuniform FPT algorithm (cited [12]).

how reviews work

0 comments

Cite this review

Pith. "Pith review of Hitting Geodesic Intervals in Structurally Restricted Graphs." pith.science (2026). https://pith.science/paper/ESM6UZ27

@misc{pith2026250901413,
  author       = {Pith},
  title        = {Pith review of: Hitting Geodesic Intervals in Structurally Restricted Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ESM6UZ27}},
  note         = {Machine review of arXiv:2509.01413}
}

abstract

Given a graph $G = (V,E)$, a set $T$ of vertex pairs, and an integer $k$, Hitting Geodesic Intervals asks whether there is a set $S \subseteq V$ of size at most $k$ such that for each terminal pair $\{u,v\} \in T$, the set $S$ intersects at least one shortest $u$-$v$ path. Aravind and Saxena [WALCOM 2024] introduced this problem and showed several parameterized complexity results. In this paper, we extend the known results in both negative and positive directions and present sharp complexity contrasts with respect to structural graph parameters. We first show that the problem is NP-complete even on graphs obtained by adding a single vertex to a disjoint union of 5-vertex paths. By modifying the proof of this result, we also show the NP-completeness on graphs obtained from a path by adding one vertex and on graphs obtained from a disjoint union of triangles by adding one universal vertex. Furthermore, we show the NP-completeness on graphs of bandwidth 4 and maximum degree 5 by replacing the universal vertex in the last case with a long path. Under standard complexity assumptions, these negative results rule out fixed-parameter algorithms for most of the structural parameters studied in the literature (if the solution size $k$ is not part of the parameter). We next present fixed-parameter algorithms parameterized by $k$ plus modular-width and by $k$ plus vertex integrity. The algorithm for the latter case does indeed solve a more general setting that includes the parameterization by the minimum vertex multiway-cut size of the terminal vertices. We show that this is tight in the sense that the problem parameterized by the minimum vertex multicut size of the terminal pairs is W[2]-complete. We then modify the proof of this intractability result and show that the problem is W[2]-complete parameterized by $k$ even in the setting where $T = \binom{Q}{2}$ for some $Q \subseteq V$.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

29 extracted references · 15 canonical work pages

[2]

N. R. Aravind and Roopam Saxena. The parameterized complexity of terminal monitoring set. In WALCOM 2024 , volume 14549 of Lecture Notes in Computer Science , pages 76--90, 2024. https://doi.org/10.1007/978-981-97-0566-5_7 doi:10.1007/978-981-97-0566-5_7

work page doi:10.1007/978-981-97-0566-5_7 2024
[1]

Agarwal, Sariel Har - Peled, Rahul Raychaudhury, and Stavros Sintos

Pankaj K. Agarwal, Sariel Har - Peled, Rahul Raychaudhury, and Stavros Sintos. Fast approximation algorithms for piercing boxes by points. In SODA 2024 , pages 4892--4908, 2024. https://doi.org/10.1137/1.9781611977912.174 doi:10.1137/1.9781611977912.174

work page doi:10.1137/1.9781611977912.174 2024
[3]

Computational complexity of geodetic set

Mustafa Atici. Computational complexity of geodetic set. Int. J. Comput. Math. , 79(5):587--591, 2002. https://doi.org/10.1080/00207160210954 doi:10.1080/00207160210954

work page doi:10.1080/00207160210954 2002
[4]

Multicut is FPT

Nicolas Bousquet, Jean Daligault, and St \' e phan Thomass \' e . Multicut is FPT . SIAM J. Comput. , 47(1):166--207, 2018. https://doi.org/10.1137/140961808 doi:10.1137/140961808

doi:10.1137/140961808 2018
[5]

Geodetic sets in graphs

Bo s tjan Bre s ar, Matja z Kov s e, and Aleksandra Tepeh. Geodetic sets in graphs. In Structural Analysis of Complex Networks , pages 197--218. Birkh \"a user, 2011. https://doi.org/10.1007/978-0-8176-4789-6_8 doi:10.1007/978-0-8176-4789-6_8

work page doi:10.1007/978-0-8176-4789-6_8 2011
[6]

An improved parameterized algorithm for the minimum node multiway cut problem

Jianer Chen, Yang Liu, and Songjian Lu. An improved parameterized algorithm for the minimum node multiway cut problem. Algorithmica , 55(1):1--13, 2009. https://doi.org/10.1007/S00453-007-9130-6 doi:10.1007/S00453-007-9130-6

doi:10.1007/s00453-007-9130-6 2009
[7]

Cormen, Charles E

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms . MIT Press, 4th edition, 2022

work page 2022
[8]

Fomin, ukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Micha Pilipczuk, and Saket Saurabh

Marek Cygan, Fedor V. Fomin, ukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Micha Pilipczuk, and Saket Saurabh. Parameterized Algorithms . Springer, 2015. https://doi.org/10.1007/978-3-319-21275-3 doi:10.1007/978-3-319-21275-3

doi:10.1007/978-3-319-21275-3 2015

Show all 29 references

[9]

Parameterized enumeration, transversals, and imperfect phylogeny reconstruction

Peter Damaschke. Parameterized enumeration, transversals, and imperfect phylogeny reconstruction. Theor. Comput. Sci. , 351(3):337--350, 2006. https://doi.org/10.1016/J.TCS.2005.10.004 doi:10.1016/J.TCS.2005.10.004

2006 doi
[10]

Douthat and Man C

Aaron L. Douthat and Man C. Kong. Computing geodetic bases of chordal and split graphs. J. Comb. Math. Comb. Comput. , 22:67--77, 1996

1996
[11]

Downey and Michael R

Rodney G. Downey and Michael R. Fellows. Parameterized Complexity . Springer, 1999. https://doi.org/10.1007/978-1-4612-0515-9 doi:10.1007/978-1-4612-0515-9

1999 doi
[12]

Downey and Michael R

Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity . Springer, 2013. https://doi.org/10.1007/978-1-4471-5559-1 doi:10.1007/978-1-4471-5559-1

2013 doi
[13]

Dregi, and Pim van 't Hof

P l Gr n s Drange, Markus S. Dregi, and Pim van 't Hof. On the computational complexity of vertex integrity and component order connectivity. Algorithmica , 76(4):1181--1202, 2016. https://doi.org/10.1007/s00453-016-0127-x doi:10.1007/s00453-016-0127-x

2016 doi
[14]

Intersection theorems for systems of sets

Paul Erd o s and Richard Rado. Intersection theorems for systems of sets. J. London Math. Soc. , 35(1):85--90, 1960. https://doi.org/10.1112/jlms/s1-35.1.85 doi:10.1112/jlms/s1-35.1.85

1960 doi
[15]

Parameterized Complexity Theory

J \" o rg Flum and Martin Grohe. Parameterized Complexity Theory . Springer, 2006. https://doi.org/10.1007/3-540-29953-X doi:10.1007/3-540-29953-X

2006 doi
[16]

Fowler, Mike Paterson, and Steven L

Robert J. Fowler, Mike Paterson, and Steven L. Tanimoto. Optimal packing and covering in the plane are NP -complete. Inf. Process. Lett. , 12(3):133--137, 1981. https://doi.org/10.1016/0020-0190(81)90111-3 doi:10.1016/0020-0190(81)90111-3

1981 doi
[17]

Garey and David S

Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP -Completeness . W. H. Freeman, 1979

1979
[18]

The geodetic number of a graph

Frank Harary, Emmanuel Loukakis, and Constantine Tsouros. The geodetic number of a graph. Math. Comput. Model. , 17(11):89--95, 1993. https://doi.org/10.1016/0895-7177(93)90259-2 doi:10.1016/0895-7177(93)90259-2

1993 doi
[19]

Bart M. P. Jansen. On structural parameterizations of hitting set: Hitting paths in graphs using 2- SAT . J. Graph Algorithms Appl. , 21(2):219--243, 2017. https://doi.org/10.7155/JGAA.00413 doi:10.7155/JGAA.00413

2017 doi
[20]

Bart M. P. Jansen and C \' e line M. F. Swennenhuis. Steiner tree parameterized by multiway cut and even less. In ESA 2024 , volume 308 of LIPIcs , pages 76:1--76:16, 2024. https://doi.org/10.4230/LIPICS.ESA.2024.76 doi:10.4230/LIPICS.ESA.2024.76

2024 doi
[21]

Parameterized complexity of geodetic set

Leon Kellerhals and Tomohiro Koana. Parameterized complexity of geodetic set. J. Graph Algorithms Appl. , 26(4):401--419, 2022. https://doi.org/10.7155/JGAA.00601 doi:10.7155/JGAA.00601

2022 doi
[22]

Parameterized graph separation problems

D \' a niel Marx. Parameterized graph separation problems. Theor. Comput. Sci. , 351(3):394--406, 2006. https://doi.org/10.1016/J.TCS.2005.10.007 doi:10.1016/J.TCS.2005.10.007

2006 doi
[23]

Fixed-parameter tractability of multicut parameterized by the size of the cutset

D \' a niel Marx and Igor Razgon. Fixed-parameter tractability of multicut parameterized by the size of the cutset. SIAM J. Comput. , 43(2):355--388, 2014. https://doi.org/10.1137/110855247 doi:10.1137/110855247

2014 doi
[24]

McConnell and Jeremy P

Ross M. McConnell and Jeremy P. Spinrad. Modular decomposition and transitive orientation. Discrete Mathematics , 201(1-3):189--241, 1999. https://doi.org/10.1016/S0012-365X(98)00319-7 doi:10.1016/S0012-365X(98)00319-7

1999 doi
[25]

Invitation to Fixed-Parameter Algorithms

Rolf Niedermeier. Invitation to Fixed-Parameter Algorithms . Oxford University Press, 2006. https://doi.org/10.1093/ACPROF:OSO/9780198566076.001.0001 doi:10.1093/ACPROF:OSO/9780198566076.001.0001

2006
[26]

o der. Comparing graph parameters. Bachelor thesis, Technische Universit\

Johannes C. B. Schr \"o der. Comparing graph parameters. Bachelor thesis, Technische Universit\"at Berlin, 2019. URL: https://fpt.akt.tu-berlin.de/publications/theses/BA-Schr\

2019
[27]

The graph parameter hierarchy, 2019

Manuel Sorge and Mathias Weller. The graph parameter hierarchy, 2019. URL: https://manyu.pro/assets/parameter-hierarchy.pdf

2019
[28]

Geodetic set on graphs of constant pathwidth and feedback vertex set number

Prafullkumar Tale. Geodetic set on graphs of constant pathwidth and feedback vertex set number. CoRR , abs/2504.17862, 2025. http://arxiv.org/abs/2504.17862 arXiv:2504.17862

2025 arXiv
[29]

Expanding the graph parameter hierarchy

Duc Long Tran. Expanding the graph parameter hierarchy. Bachelor thesis, Technische Universit\"at Berlin, 2022. URL: https://fpt.akt.tu-berlin.de/publications/theses/BA-Duc-Long-Tran.pdf

2022

Pith tools

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

[1] [2]

N. R. Aravind and Roopam Saxena. The parameterized complexity of terminal monitoring set. In WALCOM 2024 , volume 14549 of Lecture Notes in Computer Science , pages 76--90, 2024. https://doi.org/10.1007/978-981-97-0566-5_7 doi:10.1007/978-981-97-0566-5_7

work page doi:10.1007/978-981-97-0566-5_7 2024

[2] [1]

Agarwal, Sariel Har - Peled, Rahul Raychaudhury, and Stavros Sintos

Pankaj K. Agarwal, Sariel Har - Peled, Rahul Raychaudhury, and Stavros Sintos. Fast approximation algorithms for piercing boxes by points. In SODA 2024 , pages 4892--4908, 2024. https://doi.org/10.1137/1.9781611977912.174 doi:10.1137/1.9781611977912.174

work page doi:10.1137/1.9781611977912.174 2024

[3] [3]

Computational complexity of geodetic set

Mustafa Atici. Computational complexity of geodetic set. Int. J. Comput. Math. , 79(5):587--591, 2002. https://doi.org/10.1080/00207160210954 doi:10.1080/00207160210954

work page doi:10.1080/00207160210954 2002

[4] [4]

Multicut is FPT

Nicolas Bousquet, Jean Daligault, and St \' e phan Thomass \' e . Multicut is FPT . SIAM J. Comput. , 47(1):166--207, 2018. https://doi.org/10.1137/140961808 doi:10.1137/140961808

doi:10.1137/140961808 2018

[5] [5]

Geodetic sets in graphs

Bo s tjan Bre s ar, Matja z Kov s e, and Aleksandra Tepeh. Geodetic sets in graphs. In Structural Analysis of Complex Networks , pages 197--218. Birkh \"a user, 2011. https://doi.org/10.1007/978-0-8176-4789-6_8 doi:10.1007/978-0-8176-4789-6_8

work page doi:10.1007/978-0-8176-4789-6_8 2011

[6] [6]

An improved parameterized algorithm for the minimum node multiway cut problem

Jianer Chen, Yang Liu, and Songjian Lu. An improved parameterized algorithm for the minimum node multiway cut problem. Algorithmica , 55(1):1--13, 2009. https://doi.org/10.1007/S00453-007-9130-6 doi:10.1007/S00453-007-9130-6

doi:10.1007/s00453-007-9130-6 2009

[7] [7]

Cormen, Charles E

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms . MIT Press, 4th edition, 2022

work page 2022

[8] [8]

Fomin, ukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Micha Pilipczuk, and Saket Saurabh

Marek Cygan, Fedor V. Fomin, ukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Micha Pilipczuk, and Saket Saurabh. Parameterized Algorithms . Springer, 2015. https://doi.org/10.1007/978-3-319-21275-3 doi:10.1007/978-3-319-21275-3

doi:10.1007/978-3-319-21275-3 2015