Elimination distance to bounded degree on planar graphs

Alexander Lindermayr; Alexandre Vigny; Sebastian Siebertz

arxiv: 2007.02413 · v4 · submitted 2020-07-05 · 💻 cs.DM · math.CO

Elimination distance to bounded degree on planar graphs

Alexander Lindermayr , Sebastian Siebertz , Alexandre Vigny This is my paper

Pith reviewed 2026-05-24 13:54 UTC · model grok-4.3

classification 💻 cs.DM math.CO

keywords elimination distancebounded degreeplanar graphsfixed-parameter tractabilityparameterized complexitygraph algorithms

0 comments

The pith

Elimination distance to degree-d graphs is fixed-parameter tractable on planar graphs.

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

The paper establishes that there is an algorithm deciding, for a planar graph G and parameters d and k, whether the elimination distance of G to the class of maximum-degree-d graphs is at most k. The running time is f(k,d) multiplied by a polynomial in the number of vertices. A sympathetic reader would care because the elimination distance parameter was introduced to analyze the parameterized complexity of graph isomorphism, so an FPT result on planar graphs shows this distance can be computed efficiently when the target degree and the distance value are treated as fixed parameters.

Core claim

There exists an algorithm that given a planar graph G and integers d and k decides in time f(k,d)·n^c for a computable function f and constant c whether the elimination distance of G to the class of degree d graphs is at most k.

What carries the argument

Elimination distance to the class of degree-d graphs, the minimum number of steps of vertex elimination needed to reach a graph whose maximum degree is at most d.

If this is right

The decision problem belongs to FPT when the input is restricted to planar graphs.
Small values of k and d allow the distance to be computed in time polynomial in the size of the graph.
The result applies directly to any problem whose complexity is controlled by this elimination distance on planar instances.

Where Pith is reading between the lines

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

The same algorithmic approach may transfer to other sparse graph classes that admit similar structural decompositions.
The FPT result could be used as a subroutine inside algorithms for graph isomorphism on planar graphs whose elimination distance is bounded.
It remains open whether the same tractability holds when the planarity restriction is dropped.

Load-bearing premise

The input graph must be planar.

What would settle it

A proof that the decision problem is W[1]-hard on planar graphs for some fixed d, or an explicit planar graph family where any algorithm requires time superpolynomial in n when k and d are fixed.

read the original abstract

We study the graph parameter elimination distance to bounded degree, which was introduced by Bulian and Dawar in their study of the parameterized complexity of the graph isomorphism problem. We prove that the problem is fixed-parameter tractable on planar graphs, that is, there exists an algorithm that given a planar graph $G$ and integers $d$ and $k$ decides in time $f(k,d)\cdot n^c$ for a computable function~$f$ and constant $c$ whether the elimination distance of $G$ to the class of degree $d$ graphs is at most $k$.

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.

Desk Editor's Note private letter to a colleague

Abstract claims FPT for elimination distance to degree-d graphs on planar graphs, but supplies zero proof details so the claim cannot be checked.

read the letter

The main takeaway is that this abstract asserts an FPT algorithm for deciding whether a planar graph has elimination distance at most k to the class of maximum-degree-d graphs, running in f(k,d) n^c time. That is the entire content on offer. The result is new in the narrow sense that Bulian and Dawar introduced the parameter but did not settle its complexity on planar graphs, so the claim fills a specific gap. Beyond that, the abstract does nothing else: no technique is described, no reduction is sketched, and no comparison to existing planar FPT methods appears. Because only the abstract is available, there is no way to assess whether the algorithm uses standard tools such as bounded treewidth or planar separators, or whether the exponent c is reasonable. The central claim therefore rests on an uninspectable existence statement. This makes the paper unsuitable for citation until the full version is read. It is also too thin for a reading group. A serious editor could still send the full paper to referees if the authors supply a complete proof; the question is interesting enough within parameterized complexity on planar graphs that the claim deserves verification rather than immediate rejection. Until then the work remains an unverified announcement.

Referee Report

1 major / 0 minor

Summary. The manuscript claims that the elimination distance to bounded degree problem is fixed-parameter tractable on planar graphs: there exists an algorithm that, given a planar graph G and integers d and k, decides in time f(k,d)·n^c (for computable f and constant c) whether the elimination distance of G to the class of degree-d graphs is at most k.

Significance. If the result holds, it would establish FPT membership for this parameter on planar graphs, building on the introduction of elimination distance by Bulian and Dawar in the context of graph isomorphism. This could contribute to the parameterized complexity of structural graph problems on planar inputs, but the abstract-only manuscript provides no basis for evaluating the strength or novelty of the techniques.

major comments (1)

The manuscript consists only of the abstract and contains no proof, reduction, running-time analysis, or technical argument. Consequently the central claim of an f(k,d)·n^c algorithm cannot be verified against any derivation or data in the provided text.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their comments on our submission. We address the major comment below.

read point-by-point responses

Referee: [—] The manuscript consists only of the abstract and contains no proof, reduction, running-time analysis, or technical argument. Consequently the central claim of an f(k,d)·n^c algorithm cannot be verified against any derivation or data in the provided text.

Authors: We agree that the provided manuscript consists solely of the abstract and contains no proofs or technical details. This submission is an abstract-only version. The full paper containing the complete proof that elimination distance to degree-d graphs is FPT on planar graphs (via an f(k,d)·n^c algorithm) is available on arXiv:2007.02413. We are happy to provide the full version for further review if requested by the editor. revision: no

Circularity Check

0 steps flagged

No circularity: abstract states existence result with no derivation chain

full rationale

The provided document consists solely of the abstract, which asserts the existence of an FPT algorithm for elimination distance to bounded degree on planar graphs. No equations, definitions, reductions, or technical steps are present that could reduce to self-referential inputs, fitted parameters, or self-citations. The parameter itself is attributed to prior external work (Bulian and Dawar) with no author overlap. The claim is an existence statement rather than a constructed prediction or renamed known result, making the derivation chain empty and non-circular by the given criteria.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only; the claim rests on standard definitions of elimination distance and FPT from prior literature plus the assumption that planarity supplies the necessary structural leverage. No free parameters, invented entities, or ad-hoc axioms are visible.

axioms (1)

standard math Standard definition of fixed-parameter tractability and elimination distance from Bulian and Dawar
The claim is phrased in terms of these established notions.

pith-pipeline@v0.9.0 · 5593 in / 1113 out tokens · 27270 ms · 2026-05-24T13:54:23.796129+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

there exists an algorithm that given a planar graph G and integers d and k decides in time f(k,d)·n^c ... whether the elimination distance of G to the class of degree d graphs is at most k

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.