Eccentricity Shortest Path: the structural parameter landscape

XP algorithms.

• The work is classified under graph theory and parameterized complexity and exact algorithms.Source: Kernel lower bounds · p. 1
• The listed keywords include eccentricity shortest path, parameterized complexity, kernelization, and graph algorithms.Source: Kernel lower bounds · p. 2
• The listed funding is an ANRF research grant to Ashwin Jacob.Source: Kernel lower bounds · p. 2

1 Introduction

• ESP combines the requirement that a path be shortest between its own endpoints with the requirement that every vertex lie within a distance threshold of it.Extending a path can improve coverage but destroy shortestness; replacing it with a shorter route can leave vertices too far away.Source: §1 · p. 4

1.1 Previous work and structural parameterization

• Earlier work established hardness and algorithms on restricted graph classes, while leaving open whether treewidth alone suffices for FPT.The paper frames its study around FPT, XP, and kernelization with the eccentricity threshold unrestricted and structural parameters of the graph alone.Source: §1.1 · pp. 4–5

1.2 Our results

• The paper gives FPT algorithms for interval-deletion distance, cograph-deletion distance, and bandwidth, and XP algorithms for chordal-deletion distance, clique-width, and rank-width.The interval-deletion algorithm answers a question of Bhyravarapu et al. [4]; the clique-width and rank-width algorithms do not require supplied expressions or decompositions.Source: §1.2 · p. 5
• Polynomial-time solvability for every fixed treewidth follows from the clique-width XP algorithm, answering a question of Chakraborty et al. [15].The paper also records treedepth FPT and diameter XP as consequences of earlier algorithms [40, 28].Source: §1.2 · pp. 5, 7
• ESP is W[3]-hard parameterized by cutwidth, even at maximum degree five, and W[2]-hard parameterized by vertex clique-cover number.It is also NP-hard when tree-independence number is at most two, even with a decomposition whose bags are partitioned into two cliques.Source: §1.2 · p. 7
• For maximum leaf number ℓ, the paper obtains an O(ℓ^4)-bit compression and a polynomial kernel, but rules out polynomial kernels for bandwidth, feedback edge number, distance to clique, and vertex cover unless NP ⊆ coNP/poly.The vertex-cover lower bound also rules out polynomial kernels for deletion distance to proper interval graphs.Source: §1.2 · pp. 7–8

1.3 Overview of the techniques

• The algorithmic techniques use distance profiles and structural decompositions to describe how shortest paths interact with modulators or layouts.For bandwidth, the algorithm uses attainable distances rather than all values up to the potentially unbounded threshold; the clique-width XP result uses a mim-width layout.Source: §1.3 · p. 8
• Hardness constructions encode choices through distances, while the maximum-leaf kernel suppresses degree-two chains and verifies paths without expanding them.The lower-bound constructions use OR-cross-compositions and polynomial parameter transformations.Source: §1.3 · pp. 8–9

2 Preliminaries

• ESP takes a connected graph G and nonnegative integer R, and asks whether G has a shortest path P with eccG(P) ≤ R.Its optimization version seeks a shortest path of minimum eccentricity; shortest paths are geodesics, and one-vertex paths are allowed.Source: §2 · pp. 9–10

2.1 Graph parameters

• Distances to graph classes mean minimum vertex deletions that leave a graph in the class.The paper considers, among others, cographs, chordal, interval, proper interval, cluster, split, and clique graphs.Source: §2.1 · p. 10
• A tree decomposition organizes vertices into bags covering every edge, with the bags containing each vertex forming a connected subtree; treewidth is minimum maximum bag size minus one.Tree-independence number instead minimizes the maximum independence number within a bag over tree decompositions.Source: §2.1 · pp. 10–11
• The preliminaries define treedepth through the minimum height of a rooted forest whose closure contains the graph, and maximum leaf number through leaves in a spanning tree.They also define vertex cover, feedback edge number, and vertex clique-cover number as minimum-size sets or partitions with the stated structural properties.Source: §2.1 · p. 11
• Bandwidth and cutwidth measure, respectively, the maximum edge span and the maximum number of edges crossing a cut in a vertex ordering.Clique-width is defined through graph construction with labels and four operations, while rank-width and mim-width measure cut structure through rank and induced matchings.Source: §2.1 · p. 11

3 FPT algorithms

• The section treats four FPT parameterizations: distance to cographs, distance to interval graphs, bandwidth, and treedepth.Source: §3 · p. 11

3.1 Distance to cographs

• ESP is solvable in f(k)|V(G)|^O(1) time for k equal to the distance to cographs, and its optimization version is also FPT.Here k is the minimum size of a cograph modulator.Source: §3.1 · p. 12

3.1.1 A bounded-width clique-width expression

• A cograph modulator yields a bounded-width clique-width expression by refining cotree labels according to neighborhoods in the modulator.The construction builds a cotree expression for G−X, refines labels by each vertex's neighborhood in X, then adds the modulator vertices and their incident edges.Source: §3.1 · p. 12, §3.1.1 · pp. 12–13

3.1.2 A logical description of ESP

• The MSO1 formula recognizes a shortest path whose every graph vertex is within distance R, and its length is bounded using diam(G) ≤ 4t + 3.The distance predicates describe walks of at most a specified length; the formula also rules out shorter walks between the path endpoints.Source: §3.1.2 · p. 13

3.1.3 The FPT algorithm

• A maximal packing of vertex-disjoint induced P4s gives a cograph modulator X with |X| ≤ 4k, enabling the expression-and-formula method to yield an FPT algorithm.The algorithm handles R ≥ 4t + 3 immediately; otherwise the formula size is bounded by a function of t, and the optimization version tests at most 4t + 4 thresholds.Source: §3.1.3 · p. 14

3.2 Distance to interval graphs

• An FPT algorithm for interval-graph deletion distance resolves the open question posed by Bhyravarapu et al. [4].A modulator can be found in 10^k n^O(1) time, and an interval representation of the remaining graph can be computed in polynomial time.Source: §3.2 · p. 14

3.2.1 Enumerating distance profiles

• For fixed path endpoints, six labels per modulator vertex enumerate at most 6^k distance-profile candidates and include the true profile.The labels distinguish distances up to two from farther distances; vertices at distance at most two serve as anchors.Source: §3.2.1 · p. 16

3.2.2 Coverage and interval summaries

• Interval-graph endpoint orders let the algorithm retain only three boundary vertices while preserving coverage and distance counts.Coverage reduces to requiring each vertex in Uρ to be within R of a selected vertex in H; the three rightmost or leftmost representatives preserve counts up to three.Source: §3.2.2 · pp. 16, 18

3.2.3 The dynamic programming algorithm

• The dynamic program tracks selected boundary vertices, modulator degree counters, path size, and distance witnesses while testing coverage and degree constraints.It selects only eligible vertices, forces the guessed endpoints, and accepts only when all modulator distances and degree requirements are met.Source: §3.2.3 · pp. 18–19

3.2.4 Correctness and running time

• For each enumerated candidate, the dynamic program accepts exactly when an a–b geodesic of eccentricity at most R realizes its guessed modulator vertices and distances.The correctness argument establishes both completeness and soundness for this characterization.Source: §3.2.4 · p. 19
• The endpoint, cardinality, summary, and counter tests certify that G[Y] is an a–b geodesic.The summaries identify the relevant selected vertices before and after each processed vertex, while the final counters certify the exact degrees of vertices in M.Source: §3.2.4 · p. 20
• The guessed distance profile is exact, and the coverage tests ensure every vertex is within distance R of Y, so ecc_G(Y) ≤ R.Vertices outside U_ρ are covered using a profile vertex and Lemma 10; vertices in U_ρ are either selected or covered by a selected vertex of X.Source: §3.2.4 · pp. 20–21
• The algorithm runs in 13^k n^O(1) time.For each fixed candidate, the layer sweep takes 3^m 2^(k-m) n^O(1) time, and each prescribed zero set of size m has at most 5^(k-m) candidates; the endpoint-pair choices are absorbed into the polynomial factor.Source: §3.2.4 · p. 21

3.3 Bandwidth

• ESP and its optimization version run in 2O(b^2 log(b+1))n^O(1) time for bandwidth b, without a supplied bandwidth ordering.The algorithm returns a witnessing path.Source: §3.3 · p. 21, §3.3.3 · p. 26

3.3.1 Separated vertices in a rooted tree

• Every separated set in a rooted tree with at most n vertices and bandwidth b has size at most M_b, where M_b = (40bL)^b and L = 1 + floor(log2 n).The proof removes a spine to reduce bandwidth and groups the remaining components by size.Source: §3.3 · p. 21, §3.3.1 · p. 22

3.3.2 Bounding the distance spectra

• Each vertex’s distance spectrum over shortest paths with fixed endpoints is computable in O(n + m) time and has size bounded in terms of bandwidth.The algorithm bounds this spectrum using separated sets in three bandwidth-b trees.Source: §3.3.1 · p. 22, §3.3.2 · p. 23

3.3.3 The algorithm

• A tree-decomposition dynamic program tests a labeling certificate for a shortest path of eccentricity at most R, with 2^O(w)q^O(w+1)n^O(1) time for width w and maximum label-domain size q.For bandwidth b, a decomposition of width at most 2b + 1 and bounded distance spectra yield the claimed running time.Source: §3.3.3 · pp. 24–25

3.4 Treedepth

• A connected graph of treedepth d has treewidth at most d − 1 and diameter at most 2d − 2.The treewidth bound follows from bags containing each vertex and its ancestors in a treedepth decomposition.Source: §3.4 · p. 26
• ESP and a shortest path of minimum eccentricity can be found in F(td(G))n^3 time, without a supplied treedepth decomposition.The algorithm uses an earlier algorithm parameterized by treewidth and desired eccentricity, together with treedepth-based bounds on both parameters.Source: §3.4 · pp. 26–27
• The optimization algorithm tests eccentricity thresholds from 0 through the graph diameter and returns a witness at the first successful threshold.At most 2d − 1 decision calls are needed.Source: §3.4 · p. 27

4.1 Diameter

• ESP is in XP parameterized by maximum component diameter d, using r(G) ≤ diam(G) and an O(n^2r+2m)-time optimization algorithm [28].Source: §4.1 · p. 27

4.2 Distance to chordal graphs

• ESP is in XP parameterized by distance to chordal graphs, complementing W[2]-hardness for that parameter; ESP is polynomial-time solvable on chordal graphs [4, 27].Source: §4.2 · p. 28

4.2.1 Clique bags and distance profiles

• For chordal remainder H=G−S, a polynomial-size nice decomposition has bags S plus cliques, and one geodesic vertex simultaneously realizes a clique’s distances to a disjoint geodesic.For a union of at most h geodesics, a set of at most h+k vertices preserves distances from every vertex of S and the bag clique.Source: §4.2.1 · pp. 28–29

4.2.2 Certifying a geodesic

• For guessed endpoints a,b, a subset of vertices on some a-b geodesic induces that geodesic exactly when it excludes same-layer edges and satisfies prescribed oriented degree pairs.Source: §4.2.2 · p. 30

4.2.3 The dynamic programming algorithm

• Dynamic-programming states record selected bag vertices, their partial indegree/outdegree pairs, and an interior distance profile, while requiring bag vertices to remain within R of the path.Source: §4.2.3 · p. 31

Transitions

• Introduce, forget, and join transitions update degree pairs and distance profiles; joins subtract shared bag-edge counts, and forgetting a selected vertex finalizes its degree pair.Source: Transitions · pp. 31–32

4.2.4 Correctness and running time

• A geodesic of eccentricity at most R yields valid states: clique bags split it into boundedly many geodesic pieces, whose distances are captured by compact profiles.The proof also checks the partial degree and coverage conditions and verifies the leaf and introduce transitions.Source: §4.2.4 · p. 33
• The dynamic program accepts exactly when it reconstructs a geodesic whose eccentricity is at most R, and runs in n^O(k) time.Its stored distance profiles track distances to selected vertices inside and outside each decomposition bag.Source: §4.2.4 · pp. 33–35

4.3 Clique-width

• ESP is in XP parameterized by clique-width: with a supplied k-expression it runs in |τ|^O(1) + n^O(k) time, and without one in f(k)n^O(k) time.Both algorithms return a witnessing shortest path when one exists.Source: §4.3 · p. 35

4.3.1 Layouts and the model-checking theorem

• For every vertex subset A, mimG(A) ≤ ρG(A), so a rank-decomposition of width q yields a rooted layout of mim-width at most q in polynomial time.The model-checking theorem on such layouts has an exponent independent of the numerical radius, even when radii depend on the input.Source: §4.3.1 · pp. 35–36

4.3.2 A simpler certificate for a shortest path

• A connected set X is a geodesic s–t path exactly when it contains s and t, has size distG(s,t) + 1, and induces a connected graph.This certificate needs no acyclicity, degree, or explicit path predicate.Source: §4.3.2 · p. 36

4.3.3 The algorithm on a supplied mim-width layout

• Given a rooted mim-width-w layout, ESP can be solved in n^O(max{1,w}) time, returning a witnessing path; for n ≥ 2 the bound is n^O(w).The algorithm tests every ordered endpoint pair using a fixed-endpoint certificate for a geodesic path with eccentricity at most R.Source: §4.3.3 · pp. 36–37

4.3.4 From clique-width to the required layout

• A supplied clique-width k-expression yields in polynomial time a rooted layout of mim-width at most k, enabling the supplied-expression algorithm.The construction bounds each cut’s rank by k, and therefore also bounds its induced-matching number by k.Source: §4.3.4 · p. 37

4.3.5 Removing the expression and obtaining an optimal path

• Without a supplied decomposition, ESP is solvable in f(q)n^O(max{1,q}) time for rank-width q; a minimum-eccentricity shortest path is also found within the stated bounds, up to O(log n).The optimization algorithm uses binary search over the feasible radius; the mim-width model-checking bound used here is independent of the numerical radius.Source: §4.3.5 · p. 38

5.1 Clique cover number

• ESP is W[2]-hard parameterized by vertex clique-cover number, even when a vertex clique cover is supplied and its size is the parameter.Source: §5.1 · p. 38

5.1.1 Construction

• The Dominating Set reduction encodes k choices in backbone clique layers and tests domination through W's adjacencies, with pendant paths enforcing radius R.Source: §5.1.1 · pp. 38–39

5.1.2 Bounding the clique cover number

• The constructed graph has a supplied vertex clique cover of size k^2 + 2k + 3, so its minimum clique-cover number is at most that bound.The supplied cover need not be minimum.Source: §5.1.2 · p. 39

5.1.3 Correctness

• In the Dominating Set reduction, a shortest path has eccentricity at most R exactly when its selected k-tuple yields a dominating set.The shortest s–t paths are precisely the choice paths, and the distance tests in W encode whether a selected vertex dominates each source vertex.Source: §5.1.3 · pp. 39–41

5.2 Cutwidth

• ESP is W[3]-hard parameterized by cutwidth, even on connected graphs of maximum degree at most five.When a vertex cover of size k is supplied for the Binary CSP constraint graph, the constructed ordering has cutwidth at most 2k + 7.Source: §5.2 · p. 41

5.2.1 Construction

• The Binary CSP reduction uses a ladder for each variable and a test gadget for each forbidden value pair, with long test pendants checking assignments.Source: §5.2.1 · p. 42

5.2.2 Correctness

• For each assignment, the corresponding shortest path has eccentricity at most q exactly when the assignment satisfies the Binary CSP instance.A test leaf exceeds distance q precisely when its forbidden value pair is assigned; the remaining constructed vertices stay within the radius bound.Source: §5.2.2 · pp. 43–44

5.2.3 Cutwidth and completion of the proof

• The constructed ordering has cutwidth at most 2k + 7: at most 2k + 2 carrier edges, one core edge, and four test edges cross any cut.During ladder operations, at most three non-carrier edges cross; cuts during tests and between operations obey the stated overall bound.Source: §5.2.3 · p. 45
• The graph and ordering are constructible in polynomial time; when no cover is supplied, a maximal matching yields a cover X with |X| = 2|M| ≤ 2vc(F).The construction has polynomial size because T ≤ S^2 and L = 2(S + T).Source: §5.2.3 · p. 45
• Cutwidth is W[3]-hard even when the ordering is supplied, on simple connected graphs of maximum degree five.The test centers have degree five and all other vertices have degree at most three.Source: §5.2.3 · p. 45

6.1 Tree-independence number

• ESP is NP-hard on connected graphs with tree-independence number at most two, even when a tree decomposition with every bag partitioned into two cliques is supplied.This also makes ESP para-NP-hard when parameterized by tree-independence number.Source: §6.1 · p. 46, §6.1.3 · p. 48

6.1.1 Construction

• A 3-SAT reduction encodes each variable by a choice between two literal vertices along a connector chain, with length-R occurrence paths linking literals to clause vertices.The construction sets R = n + 1 and attaches length-R pendant paths at both ends of the chain.Source: §6.1.1 · p. 46

6.1.2 Bounding the tree-independence number

• Adding the clause clique to clique bags for the remaining graph yields bags covered by two cliques, so the constructed graph has tree-independence number at most two.The reduction supplies a polynomial-size tree decomposition.Source: §6.1.2 · pp. 46–47

6.1.3 Correctness

• Every shortest path between the chain endpoints chooses exactly one literal vertex per variable, and each such choice defines an assignment.The endpoint distance is 2n; paths leaving the variable-chain graph through occurrence paths are longer.Source: §6.1.3 · p. 47
• A satisfying assignment yields a shortest path of eccentricity at most R, while any qualifying shortest path encodes an assignment satisfying every clause.Internal occurrence-path vertices and clause vertices are within distance R of the path; the reverse direction uses the clause-to-path distance bound.Source: §6.1.3 · pp. 47–48

• The section proves a polynomial kernel for maximum leaf number and kernel lower bounds for distance to clique, feedback edge number, vertex cover number, and bandwidth.Source: §7 · p. 49

Cross-composition framework

• An OR-cross-composition preserves an OR of input answers while bounding the output parameter polynomially in the largest input size plus log t.Source: §7 · p. 49
• If an NP-hard language OR-cross-composes into a parameterized problem, that problem has no polynomial kernel or compression unless NP ⊆ coNP/poly and the polynomial hierarchy collapses.Source: §7 · p. 49

7.1 Maximum leaf number

• ESP has an O(ℓ^4)-bit compression into a fixed language in NP and an ordinary kernel of encoding length ℓ^O(1).Source: §7.1 · p. 49

7.1.1 A small weighted core

• Suppressing maximal degree-two chains represents G as a weighted multigraph with fewer than 4ℓ vertices, fewer than 2ℓ^2 edges, and edge lengths at most n.Enumerating candidate paths in this core gives an O(n^2 2^q)-candidate search.Source: §7.1.1 · pp. 49–50

7.1.2 A polynomial-size compression

• The compression outputs the weighted core when q > log2 n, and otherwise decides ESP in polynomial time and outputs a fixed yes- or no-instance.Both branches yield O(ℓ^4) output bits.Source: §7.1.2 · p. 51

7.1.3 The compressed language belongs to NP

• Subdivision-ESP belongs to NP despite potentially exponential expansions, using a polynomial-size certificate and verifier that avoid expanding chains.Source: §7.1.3 · pp. 51–52

7.1.4 From compression to an ordinary ESP kernel

• A polynomial-time many-one reduction from the fixed NP language turns the compression into an ordinary unweighted ESP kernel of polynomial encoding length.The output parameter is bounded by the output graph's number of vertices.Source: §7.1.4 · p. 52

7.2 Distance to clique

• ESP parameterized by distance to clique has no polynomial kernel unless NP ⊆ coNP/poly, even when a clique modulator is supplied.Source: §7.2 · p. 53, §7.2.5 · p. 56

7.2.1 Source instances and the selector formula

• The selector formula Ψ is satisfiable exactly when at least one of the input CNF-Sat formulas is satisfiable.Source: §7.2.1 · p. 53

7.2.2 Graph construction

• The graph construction uses layered assignment paths, literal tails, a clause clique, and forcing tails to encode the formula in an ESP instance.Source: §7.2.2 · pp. 53–54

7.2.3 Parameter and size bounds

• The clique modulator X has size polynomial in the largest input size plus log t, and the explicitly constructed graph has polynomial size.Source: §7.2.3 · pp. 54–55

7.2.4 Canonical paths and clause distances

• The shortest s–t paths are exactly the assignment paths, and any solution path can be trimmed to one of them without losing the eccentricity bound.Source: §7.2.4 · p. 55

7.2.5 Correctness of the cross-composition

• A constructed instance is a yes-instance exactly when some input formula is satisfiable, giving the OR-property required for the kernel lower bound.Source: §7.2.5 · p. 56

7.3 Feedback edge number

• ESP parameterized by feedback edge number has no polynomial kernel unless NP ⊆coNP/poly, even when a minimum feedback edge set is supplied.Source: §7.3 · p. 56, §7.3.5 · p. 62

7.3.5 Correctness of the cross-composition

• The construction maps a batch of equivalent Distinct 3-Sat formulas to one ESP instance that is yes exactly when at least one formula is satisfiable.Source: §7.3.1 · p. 57, §7.3.5 · pp. 61–62

7.3.2 Graph construction

• Every shortest a–b path in the selector encodes an assignment, while the test paths and hairs encode clause and input-instance checks.Source: §7.3.2 · p. 57, §7.3.4 · p. 59

7.3.3 Parameter and size bounds

• The output feedback edge number is k′ = n + 2 + 4c, counting variable gadgets, guards, test paths, and incidence paths but not pendant tails.Source: §7.3.3 · p. 59

7.3.4 Metric properties and canonical paths

• Yes-instances have a canonical shortest solution path extending an assignment path along connector prefixes, with shortestness constrained by inequalities (44).Source: §7.3.4 · p. 60

7.3.5 Correctness of the cross-composition

• A constructed ESP instance is yes exactly when some source formula is satisfiable, completing the OR-cross-composition used for the kernel lower bound.Source: §7.3.5 · pp. 61–62

7.4 Vertex cover number

• ESP parameterized by vertex cover number has no polynomial kernel unless NP ⊆coNP/poly, including when a vertex cover is supplied.Source: §7.4 · p. 62, §7.4.4 · p. 66

7.4.2 Graph construction

• The reduction builds a selection backbone with one candidate layer per budget slot, and encodes each universe element in a gadget attached to candidates for sets containing it.Source: §7.4.2 · p. 63

7.4.3 Parameter and size bounds

• The supplied vertex cover has size polynomial in the Small Universe Set Cover parameter, independent of the number of candidate sets.Source: §7.4.3 · p. 64

7.4.4 Canonical paths and correctness

• Shortest paths between the backbone endpoints are exactly selection paths, and any solution path can be reduced to one of these paths.Source: §7.4.4 · pp. 64–65
• A selection path is a solution exactly when its chosen sets cover the universe, because uncovered elements have terminals beyond distance R.Source: §7.4.4 · pp. 65–66

7.4.5 Consequences for deletion parameters

• The lower bound also holds for deletion distance to cluster, split, proper interval, or interval graphs, with or without a supplied deletion set.Source: §7.4.5 · p. 66

7.5 Bandwidth

• Unless NP ⊆coNP/poly, ESP has no polynomial kernel parameterized by bandwidth.Source: §7.5 · p. 66

7.5.1 The cross-composition construction

• The cross-composition uses formulas with at least one variable and clauses containing one to three literals, grouping well-formed formulas by their number of variables.Source: §7.5.1 · pp. 66–67
• For formulas with n variables, the construction sets A = 2n + 1, L = 2n + 2, and R = 4n + 1 for the ESP instance.Source: §7.5.1 · p. 67

Construction.

• Each formula module has upper and lower rails, a variable chain encoding literal choices, clause paths, hub links, and shared boundaries between consecutive modules.Source: Construction · p. 67

7.5.2 Canonical shortest paths and domination

• Every shortest a0–bq path has length qL, traverses rails around one unique module, and chooses one literal per variable in that module.Source: §7.5.2 · pp. 67–68
• For the selected module, all vertices are within R of the path exactly when its encoded assignment satisfies the module’s formula; nonselected modules are within R regardless.Source: §7.5.2 · p. 69

7.5.3 Correctness of the cross-composition

• The constructed ESP instance is yes exactly when at least one input formula is satisfiable.Source: §7.5.3 · p. 70

7.5.4 Bandwidth bound and completion of the proof

• The construction supplies a vertex ordering of bandwidth O(N^2), independent of the number q of formulas.Source: §7.5.4 · p. 70
• The OR-cross-composition has output parameter polynomial in N + log q, yielding the stated kernel lower bound unless NP ⊆coNP/poly.Source: §7.5.4 · p. 70