pith. sign in

arxiv: 1906.10523 · v1 · pith:DMBVFBK2new · submitted 2019-06-22 · 💻 cs.DS

l-path vertex cover is easier than l-hitting set for small l

Dekel Tsur This is my paper

Pith reviewed 2026-05-25 17:44 UTC · model grok-4.3

classification 💻 cs.DS
keywords parameterized algorithmsvertex coverpath vertex coverbranching algorithmsmeasure and conquerFPTgraph deletion problems
0
0 comments X

The pith

Parameterized algorithms solve l-path vertex cover for l=5,6,7 in O*(3.945^k), O*(4.947^k), and O*(5.951^k) time.

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

The paper develops algorithms that decide whether deleting at most k vertices from an undirected graph can eliminate every path on l vertices. For the concrete cases l equals 5, 6 and 7 the algorithms run in the stated single-exponential times. These bounds are obtained by branching on local configurations of paths and analyzing the resulting recurrences. A sympathetic reader would care because the same problem viewed as an l-hitting set instance would ordinarily require a larger base; the improvement shows that the path structure can be exploited directly.

Core claim

In the l-path vertex cover problem the input is an undirected graph G and an integer k. The goal is to decide whether there is a set of vertices S of size at most k such that G-S does not contain a path with l vertices. In this paper we give parameterized algorithms for l-path vertex cover for l = 5,6,7, whose time complexities are O^*(3.945^k), O^*(4.947^k), and O^*(5.951^k), respectively.

What carries the argument

Branching algorithms whose search-tree size is bounded by measure-and-conquer recurrences that produce the bases 3.945, 4.947 and 5.951 for l=5,6,7.

If this is right

  • For l=5 the problem belongs to FPT with base strictly below 4.
  • The same holds for l=6 with base below 5 and for l=7 with base below 6.
  • The path-specific branching rules yield strictly better running times than would follow from treating the input paths as an arbitrary collection of sets to hit.
  • The algorithms remain polynomial in the input size once k is fixed.

Where Pith is reading between the lines

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

  • The gap between the new bases and the bases known for general l-hitting set widens as l grows from 3 to 7, suggesting the advantage is structural rather than accidental.
  • Similar branching rules might be adapted to forbid other small patterns such as cycles or stars of bounded size.
  • If the same technique scales, one could hope for a base that grows slower than l for larger fixed l.

Load-bearing premise

The measure-and-conquer recurrences correctly upper-bound the size of the search tree by the stated exponential bases.

What would settle it

A concrete graph family together with a k-value on which any correct algorithm for the problem requires more than 3.945^k steps when l=5 (or the analogous higher bases for l=6 or 7).

Figures

Figures reproduced from arXiv: 1906.10523 by Dekel Tsur.

Figure 1
Figure 1. Figure 1: Figure (a) shows a recursion tree TA(G, k). In this example, the call A(G, k) makes three recursive calls: A(G1, k − 1), A(G2, k − 1), and A(G3, k − 2). Figure (b) shows the tree TA(G, k) after contracting the edge between the root and its leftmost child. The top recursion tree T 2 A(G, k) is shown in Figure (c). of algorithm A can be bounded by bounding the number of leaves in TA(G, k). The number of leav… view at source ↗
Figure 2
Figure 2. Figure 2: The worst top recursion tree for l = 4. The branching vector of every internal node is (1, 2, 2, 2, 2). Edges whose labels are not shown have label 2. the paragraphs above, the branching vector of x is (1, c1, . . . , ct), where (c1, . . . , ct) are the weighted depths of the leaves of the top recursion tree T 3 Falg(G0 , k0 ). The top recursion tree that gives the worst branching number is the tree in whi… view at source ↗
read the original abstract

In the $l$-path vertex cover problem the input is an undirected graph $G$ and an integer $k$. The goal is to decide whether there is a set of vertices $S$ of size at most $k$ such that $G-S$ does not contain a path with $l$ vertices. In this paper we give parameterized algorithms for $l$-path vertex cover for $l = 5,6,7$, whose time complexities are $O^*(3.945^k)$, $O^*(4.947^k)$, and $O^*(5.951^k)$, respectively.

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

3 major / 2 minor

Summary. The paper presents parameterized algorithms for the l-path vertex cover problem (decide if there is a vertex set S of size <=k such that G-S has no path on l vertices) for l=5,6,7. It claims running times O^*(3.945^k), O^*(4.947^k), and O^*(5.951^k) respectively, obtained via branching or measure-and-conquer on local path/vertex configurations, and positions these as improvements over the corresponding l-hitting-set bounds.

Significance. If the case analysis and recurrence solutions are correct, the results demonstrate that l-PVC admits strictly better FPT running times than l-HS for these small constant l values, providing concrete evidence that the two problems diverge in parameterized complexity even for modest l. The explicit numerical bases and the algorithmic construction constitute the main contribution.

major comments (3)
  1. [Section 3 (or whichever section contains the case analysis for l=5)] The headline claims rest entirely on the correctness of the branching analysis that produces the bases 3.945, 4.947 and 5.951. The manuscript must exhibit the complete case distinction on the local structure around a chosen path or vertex together with the resulting system of recurrences and their characteristic polynomials; any omitted configuration would invalidate the claimed bounds.
  2. [Section 4 (analysis for l=6)] For each l, the measure-and-conquer analysis (if used) must be shown to be tight; the paper should state the measure explicitly and verify that every branching rule decreases the measure by at least the amount required to obtain the stated base.
  3. [Introduction, paragraph comparing to hitting set] The abstract and introduction assert that these bounds are better than those for l-hitting set, but the comparison requires an explicit citation or reproduction of the best known l-HS bases; without that, the “easier than” claim cannot be evaluated.
minor comments (2)
  1. Notation for the measure function and the branching vectors should be introduced once and used consistently; currently the recurrence equations appear without a preceding definition of the measure.
  2. The paper should include a short table summarizing the three bases together with the corresponding l-HS bases for direct comparison.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback on our manuscript. We address each major comment below and will revise the paper to improve clarity and completeness of the analysis.

read point-by-point responses

  1. Referee: [Section 3 (or whichever section contains the case analysis for l=5)] The headline claims rest entirely on the correctness of the branching analysis that produces the bases 3.945, 4.947 and 5.951. The manuscript must exhibit the complete case distinction on the local structure around a chosen path or vertex together with the resulting system of recurrences and their characteristic polynomials; any omitted configuration would invalidate the claimed bounds.

    Authors: We agree that the branching analysis must be fully verifiable. Section 3 already presents the case distinctions on local path and vertex configurations for l=5 (and analogously for higher l), along with the derived recurrences and their solutions yielding the stated bases. To fully address the concern and facilitate independent checking, the revised version will include an appendix that enumerates every configuration considered, the associated branching vectors, and the characteristic polynomials. revision: yes

  2. Referee: [Section 4 (analysis for l=6)] For each l, the measure-and-conquer analysis (if used) must be shown to be tight; the paper should state the measure explicitly and verify that every branching rule decreases the measure by at least the amount required to obtain the stated base.

    Authors: For l=6 and l=7 our analysis uses measure-and-conquer. The revised manuscript will explicitly define the measure (a linear combination of the number of vertices, paths, and other local structures with carefully chosen weights) and include a verification table confirming that each branching rule decreases the measure by at least the minimum amount needed to achieve the claimed bases 4.947 and 5.951. revision: yes

  3. Referee: [Introduction, paragraph comparing to hitting set] The abstract and introduction assert that these bounds are better than those for l-hitting set, but the comparison requires an explicit citation or reproduction of the best known l-HS bases; without that, the “easier than” claim cannot be evaluated.

    Authors: We will add explicit citations to the best-known FPT algorithms for l-hitting set (including the relevant bases from the literature) in both the abstract and introduction. A short comparison table will also be included to make the numerical improvement for l=5,6,7 immediately visible. revision: yes

Circularity Check

0 steps flagged

No circularity; direct algorithmic construction and recurrence analysis

full rationale

The paper presents explicit parameterized algorithms for l-path vertex cover (l=5,6,7) whose running times are obtained by exhaustive case analysis on local graph structure followed by solving the resulting branching recurrences. No equations, fitted parameters, or self-citations appear in the provided abstract or description that would reduce the claimed O* bounds to the inputs by construction. The derivation chain consists of algorithm description plus measure-and-conquer analysis, which is self-contained and externally verifiable by re-running the case analysis and characteristic polynomial solver. This matches the default expectation of no significant circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, invented entities or non-standard axioms are visible in the abstract; the work rests on standard graph-theoretic definitions and the usual FPT branching framework.

pith-pipeline@v0.9.0 · 5617 in / 984 out tokens · 20472 ms · 2026-05-25T17:44:07.053459+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

14 extracted references · 14 canonical work pages · 2 internal anchors

  1. [1]

    A fast branching algorithm for cluster vertex deletion

    Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, and Marcin Pilipczuk. A fast branching algorithm for cluster vertex deletion. Theory of Computing Systems, 58(2):357–376, 2016

    work page 2016

  2. [2]

    Faster FPT algorithm for 5-path vertex cover

    Radovan ˇCerven` y and Ondˇ rej Such` y. Faster FPT algorithm for 5-path vertex cover. In Proc. 44th Symposium on Mathematical Foundations of Computer Science (MFCS), 2019

    work page 2019

  3. [3]

    Fixed-parameter algorithms for vertex cover P3

    Maw-Shang Chang, Li-Hsuan Chen, Ling-Ju Hung, Peter Rossmanith, and Ping-Chen Su. Fixed-parameter algorithms for vertex cover P3. Discrete Opti- mization, 19:12–22, 2016

    work page 2016

  4. [4]

    Parameterized algorithms for hitting set: The weighted case

    Henning Fernau. Parameterized algorithms for hitting set: The weighted case. In Italian Conference on Algorithms and Complexity (CIAC) , pages 332–343, 2006

    work page 2006

  5. [5]

    Iterative compression and exact algorithms

    Fedor V Fomin, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, and Saket Saurabh. Iterative compression and exact algorithms. Theoretical Computer Science, 411(7-9):1045–1053, 2010

    work page 2010

  6. [6]

    A faster FPT algorithm for 3-path vertex cover

    J´ an Katreniˇ c. A faster FPT algorithm for 3-path vertex cover. Information Processing Letters, 116(4):273–278, 2016

    work page 2016

  7. [7]

    D. Tsur. Parameterized algorithm for 3-path vertex cover. Theoretical Com- puter Science, 783:1–8, 2019

    work page 2019

  8. [8]

    D. Tsur. An O∗(2.619k) algorithm for 4-path vertex cover. arXiv preprint arXiv:1811.03592, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  9. [9]

    D. Tsur. Faster parameterized algorithm for cluster vertex deletion. arXiv preprint arXiv:1901.07609, 2019. 10

    work page internal anchor Pith review Pith/arXiv arXiv 1901

  10. [10]

    A fixed-parameter algorithm for the vertex cover P3 problem

    Jianhua Tu. A fixed-parameter algorithm for the vertex cover P3 problem. Information Processing Letters, 115(2):96–99, 2015

    work page 2015

  11. [11]

    An FPT algorithm for the vertex cover P4 problem

    Jianhua Tu and Zemin Jin. An FPT algorithm for the vertex cover P4 problem. Discrete Applied Mathematics, 200:186–190, 2016

    work page 2016

  12. [12]

    PhD thesis, Department of Computer and Information Science, Link¨ opings universitet, 2007

    Magnus Wahlstr¨ om.Algorithms, measures and upper bounds for satisfiability and related problems . PhD thesis, Department of Computer and Information Science, Link¨ opings universitet, 2007

    work page 2007

  13. [13]

    A measure and conquer approach for the parameterized bounded degree-one vertex deletion

    Bang Ye Wu. A measure and conquer approach for the parameterized bounded degree-one vertex deletion. In Proc. 21st International Computing and Combi- natorics Conference (COCOON), pages 469–480, 2015

    work page 2015

  14. [14]

    Kernelization and parameterized algorithms for 3-path vertex cover

    Mingyu Xiao and Shaowei Kou. Kernelization and parameterized algorithms for 3-path vertex cover. In Proc. 14th International Conference on Theory and Applications of Models of Computation (TAMC) , pages 654–668, 2017. 11

    work page 2017