pith. sign in

arxiv: 2606.30882 · v1 · pith:22IRGDAKnew · submitted 2026-06-29 · 💻 cs.DS · cs.DM

Algorithms and complexity for geodetic sets on interval and chordal graphs

Dibyayan Chakraborty , Sandip Das , Florent Foucaud , Harmender Gahlawat , Dimitri Lajou This is my paper

Pith reviewed 2026-07-01 01:01 UTC · model grok-4.3

classification 💻 cs.DS cs.DM
keywords geodetic setchordal graphsinterval graphsfixed-parameter tractabilityNP-hardnesstree-widthclique number
0
0 comments X

The pith

Minimum Geodetic Set is fixed-parameter tractable on chordal graphs parameterized by tree-width but NP-hard on interval graphs.

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

The paper investigates the Minimum Geodetic Set problem, which seeks the smallest vertex set S such that every vertex in the graph lies on a shortest path between a pair of vertices from S. It establishes that the problem is fixed-parameter tractable on chordal graphs when parameterized by tree-width, which equals the clique number, and therefore admits polynomial-time algorithms on k-trees for any fixed k. It further proves NP-hardness on interval graphs via a custom reduction that accounts for their linear ordering, resolving an open question posed in 2012 for the case of proper interval graphs being polynomial-time solvable.

Core claim

Minimum Geodetic Set is fixed-parameter tractable for chordal graphs parameterized by tree-width and NP-hard on interval graphs.

What carries the argument

An FPT algorithm on chordal graphs that exploits the equality of tree-width and clique number, together with a reduction from an NP-hard problem that produces interval graphs while preserving their consecutive-ones ordering.

If this is right

  • Polynomial-time solvability holds for Minimum Geodetic Set on all k-trees for fixed k.
  • The FPT result applies uniformly to every chordal graph class with bounded maximum clique size.
  • No polynomial-time algorithm exists for Minimum Geodetic Set on interval graphs unless P equals NP.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The contrast between chordal and interval graphs indicates that additional structure beyond being chordal is required for polynomial-time solvability.
  • Other parameterizations, such as by solution size, might still yield tractability results on interval graphs despite the general NP-hardness.
  • The reduction method may extend to prove hardness for geodetic-type problems on other linearly ordered graph classes.

Load-bearing premise

A reduction from an NP-hard problem can be embedded into interval graphs while respecting their linear interval representation.

What would settle it

Either a polynomial-time algorithm for Minimum Geodetic Set on general interval graphs, or a family of chordal graphs with bounded clique number on which no f(clique-number) * n^O(1) algorithm solves the problem.

Figures

Figures reproduced from arXiv: 2606.30882 by Dibyayan Chakraborty, Dimitri Lajou, Florent Foucaud, Harmender Gahlawat, Sandip Das.

Figure 1
Figure 1. Figure 1: Inclusion diagram for subclasses of chordal graphs. If a class [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of Lemma 6. In both (a) and (b), any u, v-path passing through z has length at least du + dv + 2, and hence z /∈ I(u, v). In (a), y ∈ I(u, v) and x, w /∈ I(u, v) since any u, v-path that passes through any of x or y has length at least du + dv + 1. In (b), both x, w ∈ I(u, v). Definition 5. Consider a graph G, and let y be a vertex of G and X be a subset of V (G) such that G[X] is a clique. We… view at source ↗
Figure 3
Figure 3. Figure 3: Here v is a node of T such that β(v) = {x1, . . . , x6}. Further, let τ = (τ int, τ ext, τ cov, τuncov, τ bag) be a 5-tuple such that for S ⊆ β(v), τ ext[S] = 1 iff S ∈ S = {{x1, x2, x3} , {x2, x4, x6} , {x3, x4} , {x5, x6} , {x6}}. We construct Hτ v by first considering the graph G≤v and for each S ∈ S, we add a vertex in S τ v and connect it to each vertex of S. G≥v denote G − V (G<v); and G>v denote G≥v… view at source ↗
Figure 4
Figure 4. Figure 4: Overview of the reduction. (a) Roadmap of the reduction procedure for proving Theorem [PITH_FULL_IMAGE:figures/full_fig_p017_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The start gadget S . For drawing purposes, the proportions of the intervals were changed. Nevertheless, the obtained interval graph is unchanged. sq q rq · · · X Tp uTp vTp wTp T2 t T1 t2 t1 · · · X′ [PITH_FULL_IMAGE:figures/full_fig_p019_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The implication gadget IMP [¬p → q]. For drawing purposes, the proportions of the intervals were changed. Nevertheless, the obtained interval graph is unchanged. 4.4 Implication gadget of a root p In order to construct the variable gadgets and the clause gadgets, we need to define the implication gadget. Below we describe a generic procedure to construct implication gadgets of a root p which is different f… view at source ↗
Figure 7
Figure 7. Figure 7: The covering gadget COV[i]. For drawing purposes, the proportions of the intervals were changed. Nevertheless, the obtained interval graph is unchanged. S T ∈T {uT , vT , wT }. Let D = D ∪ IMP [¬p → q]. For each T ∈ T , let T = T ∪ Tnew and T = T ∪ {T1, T2}. Observe that the intersection graph of D does not contain K1,5 as induced subgraph. 4.5 Construction of covering gadgets Below we describe the three s… view at source ↗
Figure 8
Figure 8. Figure 8: The insert gadget INS [p, q]. For drawing purposes, the proportions of the intervals were changed. Nevertheless, the obtained interval graph is unchanged. 4.6 Construction of the insert gadget Let Tp and Tq be two tracks of T with roots p and q, respectively. Without loss of generality, assume that Tp < Tq. Below we describe the three steps for constructing the insert gadget INS [p, q]. See [PITH_FULL_IMA… view at source ↗
Figure 9
Figure 9. Figure 9: The AND gadget AND [p, q]. For drawing purposes, the proportions of the intervals were changed. Nevertheless, the obtained interval graph is unchanged. Let Y2 be the track just preceding Tq in T . Observe that either Y2 = Tm or Tm < Y2 < Tq. Now define γ (p, q) = h max(α (p, q)), max(uY2 )+max(uTq ) 2 i . Let Y ′ 2 be the track just following Tq in T . We define h = max(uY ′ 2 ) if Y ′ 2 exists and h = max… view at source ↗
Figure 10
Figure 10. Figure 10: The variable gadget Xi created corresponding to the variable xi . The first implication gadget contains three special intervals named xi, rxi , sxi . The second implication gadget contains three special intervals named xi, rxi , sxi . 4.9 Construction of clause gadgets We shall complete our construction of clause gadget Ci corresponding to the clause Ci = (ℓ 1 i , ℓ2 i , ℓ3 i ). First, we create the cover… view at source ↗
Figure 11
Figure 11. Figure 11: Illustration of the clause gadget Ci with literals ℓ 1 i , ℓ2 i , ℓ3 i . The names of the special intervals created at each gadget are highlighted above or below the box illustrating the respective gadgets. Lemma 21. There are 2 + 4n + 35m tracks in T and 4 + 6n + 52m point intervals in D. The total number of intervals in D is O((n + m) 2 ). Proof. Recall that the construction of the start gadget consists… view at source ↗
Figure 12
Figure 12. Figure 12: Illustration of the gadgets for the 3-SAT instance [PITH_FULL_IMAGE:figures/full_fig_p034_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Roadmap for proof of Theorem 2. 35 [PITH_FULL_IMAGE:figures/full_fig_p035_13.png] view at source ↗
read the original abstract

We study the computational complexity of finding the geodetic number of a graph on chordal graphs and interval graphs. A set $S$ of vertices of a graph $G$ is a \textit{geodetic set} if every vertex of $G$ lies in a shortest path between some pair of vertices of $S$. The \textsc{Minimum Geodetic Set (MGS)} problem is to find a geodetic set with minimum cardinality of a given graph. We show that \textsc{Minimum Geodetic Set} is fixed parameter tractable for chordal graphs when parameterized by its \emph{tree-width} (which equals its clique number). This implies a polynomial-time algorithm for $k$-trees, for fixed $k$. Then, we show that \textsc{Minimum Geodetic Set} is NP-hard on interval graphs, thereby answering a question of Ekim et al. (LATIN, 2012), who showed that \textsc{Minimum Geodetic Set} is polynomial-time solvable on proper interval graphs. As interval graphs are very constrained, to prove the latter result, we design a rather sophisticated reduction technique to work around their inherent linear structure.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript claims two main results on Minimum Geodetic Set (MGS): (1) MGS is FPT on chordal graphs parameterized by tree-width (equal to clique number), yielding a polynomial-time algorithm for fixed k on k-trees; (2) MGS is NP-hard on interval graphs via a custom reduction that respects their linear structure, answering an open question of Ekim et al. (LATIN 2012) who showed polynomial-time solvability on proper interval graphs.

Significance. If the results hold, the FPT algorithm supplies a parameterized approach for chordal graphs whose tree-width is bounded by clique number, which is useful for graphs with bounded clique size. The NP-hardness result is significant because it separates the complexity of MGS between proper interval graphs (P) and general interval graphs (NP-hard), showing that the additional flexibility in interval representations suffices for hardness. The sophisticated reduction technique, if correct, is a technical contribution in constructing interval-graph gadgets that encode branching choices without violating the Helly property or allowing smaller geodetic sets via the linear clique ordering.

major comments (1)
  1. [Reduction section] Reduction section (final paragraph of abstract and corresponding proof): The NP-hardness claim rests entirely on a custom reduction that must simultaneously produce a valid interval graph and ensure that minimum geodetic sets in the constructed instance correspond exactly to solutions of the source problem. Because interval graphs admit a linear ordering of maximal cliques, any gadget encoding non-local choices risks either violating interval representability or permitting a smaller geodetic set that exploits the ordering. The manuscript must explicitly verify (e.g., via a lemma) that no such bypass exists; this verification is load-bearing for the hardness result.
minor comments (2)
  1. The abstract states that tree-width equals clique number on chordal graphs; a brief parenthetical recalling that tree-width equals ω(G)−1 would improve precision for readers outside the area.
  2. The FPT claim for chordal graphs is independent of the interval-graph hardness; the manuscript could add a short sentence clarifying that the two results use unrelated techniques.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying a point where the presentation of the reduction can be strengthened. We address the major comment below.

read point-by-point responses

  1. Referee: [Reduction section] Reduction section (final paragraph of abstract and corresponding proof): The NP-hardness claim rests entirely on a custom reduction that must simultaneously produce a valid interval graph and ensure that minimum geodetic sets in the constructed instance correspond exactly to solutions of the source problem. Because interval graphs admit a linear ordering of maximal cliques, any gadget encoding non-local choices risks either violating interval representability or permitting a smaller geodetic set that exploits the ordering. The manuscript must explicitly verify (e.g., via a lemma) that no such bypass exists; this verification is load-bearing for the hardness result.

    Authors: We agree that an explicit, self-contained verification is desirable to rule out the possibility that a smaller geodetic set could exploit the linear ordering of maximal cliques. The existing proof already shows both directions of the reduction (a solution to the source problem yields a geodetic set of the claimed size, and every geodetic set in the constructed interval graph yields a solution to the source problem) while preserving the interval representation. To address the referee's concern directly, we will add a dedicated lemma that isolates the argument against bypasses: it will use the Helly property and the forced shortest-path structure of the gadgets to prove that no set smaller than the claimed size can cover all vertices without corresponding to a valid source solution. This lemma will be placed immediately after the construction and before the correctness proof. revision: yes

Circularity Check

0 steps flagged

No circularity: standard complexity results via independent reduction and DP

full rationale

The paper establishes FPT membership for chordal graphs (via treewidth parameterization, using the known equality of treewidth and clique number in chordal graphs) and NP-hardness on interval graphs via a custom reduction from an external NP-hard problem. No equations, parameters, or predictions appear that reduce by construction to fitted inputs or self-definitions. The cited prior work (Ekim et al.) is external and non-overlapping. The reduction is presented as a technical construction respecting interval structure, not as a renaming or self-referential step. The derivation chain is self-contained against external benchmarks and does not invoke load-bearing self-citations or ansatzes.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Results rest on the standard fact that chordal graphs have treewidth equal to clique number and on the correctness of a new reduction for interval graphs; no free parameters or invented entities are introduced.

axioms (1)
  • standard math Treewidth of chordal graphs equals their clique number
    Invoked explicitly in the abstract to justify the parameterization.

pith-pipeline@v0.9.1-grok · 5756 in / 1130 out tokens · 45099 ms · 2026-07-01T01:01:12.131059+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

72 extracted references · 6 canonical work pages

  1. [1]

    Algorithmica , volume =

    Benjamin Bergougnoux and Oscar Defrain and Fionn Mc Inerney , title =. Algorithmica , volume =

  2. [2]

    Chakraborty and S

    D. Chakraborty and S. Das and F. Foucaud and H. Gahlawat and D. Lajou and B. Roy , title =. 31st International Symposium on Algorithms and Computation (ISAAC 2020) , pages =. 2020 , volume =. doi:10.4230/LIPIcs.ISAAC.2020.7 , annote =

    work page doi:10.4230/lipics.isaac.2020.7 2020

  3. [3]

    Computing and Combinatorics: 27th International Conference, COCOON 2021, Tainan, Taiwan, October 24--26, 2021, Proceedings 27 , pages=

    On the approximation hardness of geodetic set and its variants , author=. Computing and Combinatorics: 27th International Conference, COCOON 2021, Tainan, Taiwan, October 24--26, 2021, Proceedings 27 , pages=. 2021 , organization=

    2021

  4. [4]

    Discrete Mathematics , volume=

    Well-partitioned chordal graphs , author=. Discrete Mathematics , volume=. 2022 , publisher=

    2022

  5. [5]

    Theoretical Computer Science , volume=

    Algorithms and complexity for geodetic sets on partial grids , author=. Theoretical Computer Science , volume=. 2023 , publisher=

    2023

  6. [6]

    Problems in

    Foucaud, Florent and Galby, Esther and Khazaliya, Liana and Li, Shaohua and Mc Inerney, Fionn and Sharma, Roohani and Tale, Prafullkumar , booktitle=. Problems in. 2024 , organization=

    2024

  7. [7]

    Metric Dimension and Geodetic Set Parameterized by Vertex Cover , booktitle =

    Florent Foucaud and Esther Galby and Liana Khazaliya and Shaohua Li and Fionn Mc Inerney and Roohani Sharma and Prafullkumar Tale , editor =. Metric Dimension and Geodetic Set Parameterized by Vertex Cover , booktitle =

  8. [8]

    Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number , booktitle =

    Prafullkumar Tale , editor =. Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number , booktitle =

  9. [9]

    Conference on Algorithms and Discrete Applied Mathematics , pages=

    Monitoring edge-geodetic sets in graphs: extremal graphs, bounds, complexity , author=. Conference on Algorithms and Discrete Applied Mathematics , pages=. 2024 , organization=

    2024

  10. [10]

    arXiv preprint arXiv:2405.01344 , year=

    Metric dimension and geodetic set parameterized by vertex cover , author=. arXiv preprint arXiv:2405.01344 , year=

    work page arXiv

  11. [11]

    International Workshop on Graph-Theoretic Concepts in Computer Science , pages=

    Metric dimension parameterized by treewidth in chordal graphs , author=. International Workshop on Graph-Theoretic Concepts in Computer Science , pages=. 2023 , organization=

    2023

  12. [12]

    arXiv preprint arXiv:2409.20505 , year=

    The Closed Geodetic Game: algorithms and strategies , author=. arXiv preprint arXiv:2409.20505 , year=

    work page arXiv

  13. [13]

    The Closed Geodetic Game: Algorithms and Strategies , booktitle =

    Antoine Dailly and Harmender Gahlawat and Zin Mar Myint , editor =. The Closed Geodetic Game: Algorithms and Strategies , booktitle =

  14. [14]

    Theoretical Computer Science , volume=

    Graph convexity impartial games: Complexity and winning strategies , author=. Theoretical Computer Science , volume=. 2024 , publisher=

    2024

  15. [15]

    Algorithmica , volume=

    Optimality program in segment and string graphs , author=. Algorithmica , volume=. 2019 , publisher=

    2019

  16. [16]

    Journal of Combinatorial Theory, Series B , volume=

    Face covers and the genus problem for apex graphs , author=. Journal of Combinatorial Theory, Series B , volume=. 2001 , publisher=

    2001

  17. [17]

    Discrete mathematics , volume=

    Unit disk graphs , author=. Discrete mathematics , volume=

  18. [18]

    Journal of Combinatorial Theory, Series B , volume=

    Interval representations of planar graphs , author=. Journal of Combinatorial Theory, Series B , volume=

  19. [19]

    Gomes, G. C. M. and Lima, C. V. G. C. and Santos, V. F. dos , JOURNAL =. 2019 , MONTH = May, KEYWORDS =

    2019

  20. [20]

    Foucaud and G

    F. Foucaud and G. B. Mertzios and R. Naserasr and A. Parreau and P. Valicov , title =. Algorithmica , volume =

  21. [21]

    Proceedings 38th Annual Symposium on Foundations of Computer Science , pages=

    Hamiltonian cycles in solid grid graphs , author=. Proceedings 38th Annual Symposium on Foundations of Computer Science , pages=. 1997 , organization=

    1997

  22. [22]

    Discrete Applied Mathematics , volume=

    A linear-time algorithm for the longest path problem in rectangular grid graphs , author=. Discrete Applied Mathematics , volume=. 2012 , publisher=

    2012

  23. [23]

    European Symposium on Algorithms , pages=

    An O(n^4) Time Algorithm to Compute the Bisection Width of Solid Grid Graphs , author=. European Symposium on Algorithms , pages=. 2011 , organization=

    2011

  24. [24]

    Dourado and Fábio Protti and Rudini M

    Júlio Araújo and Mitre C. Dourado and Fábio Protti and Rudini M. Sampaio , title =. 2025 , publisher =. doi:10.1007/978-3-031-84128-6 , pages =

    work page doi:10.1007/978-3-031-84128-6 2025

  25. [25]

    2013 , author =

    Geodesic Convexity in Graphs , publisher =. 2013 , author =

    2013

  26. [26]

    , title =

    Farber, Martin and Jamison, Robert E. , title =. SIAM Journal on Algebraic Discrete Methods , volume =

  27. [27]

    2014 , organization=

    Analytical approach to parallel repetition , author=. 2014 , organization=

    2014

  28. [28]

    Journal of computer and system sciences , volume=

    Approximation algorithms for combinatorial problems , author=. Journal of computer and system sciences , volume=. 1974 , publisher=

    1974

  29. [29]

    Hardness and Approximation for the Geodetic Set Problem in Some Graph Classes

    D. Chakraborty and F. Foucaud and H. Gahlawat and S. K. Ghosh and B. Roy , title="Hardness and Approximation for the Geodetic Set Problem in Some Graph Classes", booktitle="Proceedings of the 6th International Conference on Algorithms and Discrete Applied Mathematics (. 2020

    2020

  30. [30]

    Kellerhals and T

    L. Kellerhals and T. Koana , title =. Proceedings of the 15th International Symposium on Parameterized and Exact Computation (. 2020 , url =. doi:10.4230/LIPIcs.IPEC.2020.20 , timestamp =

    work page doi:10.4230/lipics.ipec.2020.20 2020

  31. [31]

    Leon Kellerhals and Tomohiro Koana , title =. J. Graph Algorithms Appl. , volume =

  32. [32]

    1994 , author =

    Treewidth, Computations and Approximations , publisher =. 1994 , author =

    1994

  33. [33]

    and Golovach, P

    Belmonte, R. and Golovach, P. A. and Heggernes, P. and van't Hof, P. and Kamiński, M. and Paulusma, D. , pages =. Detecting Fixed Patterns in Chordal Graphs in Polynomial Time , publisher =. 2014 , journal =

    2014

  34. [34]

    Valiant, L. G. , journal=. Universality considerations in. 1981 , publisher=

    1981

  35. [35]

    Theoretical Computer Science , volume=

    Induced subgraph isomorphism on proper interval and bipartite permutation graphs , author=. Theoretical Computer Science , volume=. 2015 , publisher=

    2015

  36. [36]

    RAIRO-Operations Research , volume=

    Block decomposition approach to compute a minimum geodetic set , author=. RAIRO-Operations Research , volume=. 2014 , publisher=

    2014

  37. [37]

    Information and Computation , volume=

    Approximation hardness of dominating set problems in bounded degree graphs , author=. Information and Computation , volume=. 2008 , publisher=

    2008

  38. [38]

    SIAM Journal on Applied Mathematics , volume=

    Edge dominating sets in graphs , author=. SIAM Journal on Applied Mathematics , volume=. 1980 , publisher=

    1980

  39. [39]

    2002 , publisher=

    Computers and intractability , author=. 2002 , publisher=

    2002

  40. [40]

    Mathematical and Computer Modelling , volume=

    The geodetic number of a graph , author=. Mathematical and Computer Modelling , volume=. 1993 , publisher=

    1993

  41. [41]

    A. L. Douthat and Man C. Kong. Computing geodetic bases of chordal and split graph. Journal of Combinatorial Mathematics and Combinatorial Computing. 1996

    1996

  42. [42]

    Optimizing Cross-Line Dispatching for Minimum Electric Bus Fleet , year=

    Wang, Chonghuan and Song, Yiwen and Fan, Guiyun and Jin, Haiming and Su, Lu and Zhang, Fan and Wang, Xinbing , journal=. Optimizing Cross-Line Dispatching for Minimum Electric Bus Fleet , year=

  43. [43]

    International journal of computer mathematics , volume=

    Computational complexity of geodetic set , author=. International journal of computer mathematics , volume=. 2002 , publisher=

    2002

  44. [44]

    Discrete Mathematics , volume=

    Some remarks on the geodetic number of a graph , author=. Discrete Mathematics , volume=. 2010 , publisher=

    2010

  45. [45]

    2008 , publisher=

    On the complexity of the geodetic and convexity numbers of a graph , author=. 2008 , publisher=

    2008

  46. [46]

    SIAM Journal on Algebraic Discrete Methods , volume=

    Convexity in graphs and hypergraphs , author=. SIAM Journal on Algebraic Discrete Methods , volume=. 1986 , publisher=

    1986

  47. [47]

    2012 , organization=

    Computing minimum geodetic sets of proper interval graphs , author=. 2012 , organization=

    2012

  48. [48]

    Theoretical Computer Science , volume=

    Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs , author=. Theoretical Computer Science , volume=. 2018 , publisher=

    2018

  49. [49]

    Information Processing Letters , volume=

    On the hardness of finding the geodetic number of a subcubic graph , author=. Information Processing Letters , volume=. 2018 , publisher=

    2018

  50. [50]

    SIAM Journal on Discrete Mathematics , volume=

    Reconfigurations in graphs and grids , author=. SIAM Journal on Discrete Mathematics , volume=. 2008 , publisher=

    2008

  51. [51]

    SIAM Journal on Computing , volume=

    Hamilton paths in grid graphs , author=. SIAM Journal on Computing , volume=. 1982 , publisher=

    1982

  52. [52]

    Polynomial Time Algorithms for Computing a Minimum Hull Set in Distance-Hereditary and Chordal Graphs , journal =

    Kant\'. Polynomial Time Algorithms for Computing a Minimum Hull Set in Distance-Hereditary and Chordal Graphs , journal =

  53. [53]

    Ahn and L

    J. Ahn and L. Jaffke and O. Kwon and P. T. Lima , title =. Discrete Mathematics , volume =. 2022 , issn =

    2022

  54. [54]

    2010 , organization=

    A 7/6-approximation algorithm for the max-min connected bipartition problem on grid graphs , author=. 2010 , organization=

    2010

  55. [55]

    2015 , organization=

    On approximating node-disjoint paths in grids , author=. 2015 , organization=

    2015

  56. [56]

    Discrete Applied Mathematics , volume=

    An approximation algorithm for the longest cycle problem in solid grid graphs , author=. Discrete Applied Mathematics , volume=. 2016 , publisher=

    2016

  57. [57]

    Theoretical Computer Science , volume=

    Approximating the longest paths in grid graphs , author=. Theoretical Computer Science , volume=. 2011 , publisher=

    2011

  58. [58]

    Quaestiones Mathematicae , volume=

    Geodetic games for graphs , author=. Quaestiones Mathematicae , volume=. 1985 , publisher=

    1985

  59. [59]

    Quaestiones Mathematicae , volume=

    Geodetic achievement and avoidance games for graphs , author=. Quaestiones Mathematicae , volume=. 2003 , publisher=

    2003

  60. [60]

    Networks , volume=

    A new characterization of tree medians with applications to distributed sorting , author=. Networks , volume=. 1994 , publisher=

    1994

  61. [61]

    Discrete Mathematics , volume=

    Another characterization of the centroid of a tree , author=. Discrete Mathematics , volume=. 1978 , publisher=

    1978

  62. [62]

    Discrete Mathematics , volume=

    On the Steiner, geodetic and hull numbers of graphs , author=. Discrete Mathematics , volume=. 2005 , publisher=

    2005

  63. [63]

    Carlos V. G. C. Lima and Vin. On the computational complexity of the strong geodetic recognition problem , journal =

  64. [64]

    arXiv preprint arXiv:2208.01796 , year=

    On the Computational Complexity of the Strong Geodetic Recognition Problem , author=. arXiv preprint arXiv:2208.01796 , year=

    work page arXiv

  65. [65]

    33rd International Symposium on Algorithms and Computation

    Chakraborty, Dibyayan and Dailly, Antoine and Das, Sandip and Foucaud, Florent and Gahlawat, Harmender and Ghosh, Subir Kumar , title =. 33rd International Symposium on Algorithms and Computation

  66. [66]

    Algorithmica , volume=

    On the approximability of the minimum rainbow subgraph problem and other related problems , author=. Algorithmica , volume=. 2017 , publisher=

    2017

  67. [67]

    Information Processing Letters , volume=

    Unit-length embedding of binary trees on a square grid , author=. Information Processing Letters , volume=. 1989 , publisher=

    1989

  68. [68]

    , author=

    The structure of claw-free graphs. , author=. Surveys in combinatorics , volume=

  69. [69]

    , author=

    Structure and properties of maximal outerplanar graphs. , author=

  70. [70]

    Graphs and Combinatorics , volume=

    Robust algorithms for the stable set problem , author=. Graphs and Combinatorics , volume=. 2003 , publisher=

    2003

  71. [71]

    Discrete applied mathematics , volume=

    Maximum cut on line and total graphs , author=. Discrete applied mathematics , volume=. 1999 , publisher=

    1999

  72. [72]

    The intersection graphs of subtrees in trees are exactly the chordal graphs

    Fǎnicǎ Gavril. The intersection graphs of subtrees in trees are exactly the chordal graphs. Journal of Combinatorial Theory, Series B. 1974

    1974