Pith. sign in

REVIEW 2 major objections 3 minor 1 cited by

Finding d-Cuts in Claw-free Graphs

T0 review · 2 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read This paper proves that for every $d\geq 2$, $d$-Cut on claw-free graphs is constant-time solvable when the maximum degree is at most $2d+1$ and NP-complete when it reaches $2d+3$, settling the previously open $d=2$ case.

desk verdict Solid paper that closes the d=2 open case for d-Cut on claw-free graphs; one missing clause normalization in the hardness proof, easily fixed. read the letter →

arxiv 2505.17993 v1 pith:T56OURSU submitted 2025-05-23 math.CO cs.CCcs.DM

Jungho Ahn , Tala Eagling-Vose , Felicia Lucke , Daniël Paulusma , Siani Smith This is my paper
classification math.COcs.CCcs.DM MSC 05C7005C8568Q17
keywords matchingcutd-cutclaw-freegraphsmaximumdegreeNP-completenessNAE3-Sat0-1constant-timealgorithmsS_{1^tl}-free
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

The paper resolves the open problem of $d$-Cut on claw-free graphs by proving a degree threshold: for every $d\geq 2$, the problem is constant-time solvable for graphs of maximum degree at most $2d+1$, and NP-complete for graphs of maximum degree at least $2d+3$. In the easy case the paper proves a structural theorem—every claw-free graph with $\Delta\leq 2d+1$ that is large enough (more than $4d^2(2d+1)$ vertices) contains a $d$-cut, and one can be found in linear time. The hardness direction uses a reduction from NAE 3-Sat 0-1 and a family of claw-free $(2d+2)$-regular graphs that provably have no $d$-cut. In particular, the previously missing case $d=2$ is settled: 2-Cut is NP-complete for claw-free graphs, specifically for such graphs of maximum degree 7, while being constant-time solvable for maximum degree at most 5.

What carries the argument

The key machinery is a linear-time red-blue colouring lemma (Lemma 9): given a set $S$ with $|S|+|\delta(S)|<|V|$ and every vertex of $S$ incident to at most $d$ edges leaving $S$, colour $S$ blue, repeatedly promote to blue any uncoloured vertex with at least $d+1$ blue neighbours, and colour the rest red; the degree bound then forces a $d$-cut, while the size condition guarantees both colours appear. For the sufficiency result, Theorem 10 builds such an $S$ in constant time from a ball of radius $\ell+1$ around any vertex of an $S_{1^t,\ell}$-free graph, where $S_{1^t,\ell}$ is obtained from a star by subdividing one edge $\ell$ times. For the hardness side, the paper constructs claw-free $(2d+2)$-regular graphs without a $d$-cut by taking $k$ cliques of size $r=2d+2$, partitioning each into $A_i$ (size $d+1$) and $B_i$, and adding a vertex $v_i$ complete to $B_i\cup A_{i+1}$; attaching extra `free' vertices to these graphs gives the gadget $H_{d,k,r}$ that appears for each variable occurrence. The reduction also uses a clause gadget consisting of two cliques $D_{i,1}$ (size $d$), $D_{i,2}$ (size $d+1$) and a vertex $c_i$, with asymmetric edges to the free vertices of the variable gadgets.

What would settle it

Search for a claw-free graph with maximum degree at most $2d+1$ and more than $4d^2(2d+1)$ vertices that has no $d$-cut: Theorem 3 guarantees such a graph does not exist, so any example would disprove the positive half of the dichotomy.

Watch

Extended reading notes

Core claim

The central claim is that $d$-Cut on claw-free graphs has a sharp maximum-degree threshold between $2d+1$ and $2d+3$ for every $d\geq 2$. Theorem 3 asserts that any claw-free graph with $\Delta\leq 2d+1$ and $|V|>4d^2(2d+1)$ has a $d$-cut, findable in linear time, and that the bound is tight because there are arbitrarily large claw-free $(2d+2)$-regular graphs with no $d$-cut. Theorem 4 then states that $d$-Cut is constant-time solvable on claw-free graphs with $\Delta\leq 2d+1$ and NP-complete on claw-free graphs with $\Delta=2d+3$; this completes the $d=2$ case of Open Problem 1, showing 2-Cut is NP-complete on claw-free graphs of maximum degree 7. The paper also proves that the positive half generalizes to $S_{1^t,\ell}$-free graphs.

Load-bearing premise

The load-bearing premise is that NAE 3-Sat 0-1 is NP-complete as asserted by [9] (not reproved in this paper), together with the implicit assumption that every clause can be reordered to put its single negative literal first so that the asymmetric clause gadget behaves as intended.

Editorial extensions

If this is right

  • The complexity of 2-Cut on claw-free graphs is no longer open: it is constant-time solvable for maximum degree at most 5 and NP-complete for maximum degree at least 7.
  • For every $d\geq 2$, any claw-free graph with maximum degree at most $2d+1$ and more than $4d^2(2d+1)$ vertices is guaranteed to have a $d$-cut, and one can be exhibited in linear time.
  • The only maximum-degree value for which the complexity of $d$-Cut on claw-free graphs remains unknown is $\Delta=2d+2$.
  • The positive result lifts to $S_{1^t,\ell}$-free graphs with a degree bound of roughly $\frac{t}{t-1}d$, giving linear-time $d$-cut algorithms for those classes as well.

Reading between the lines

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

  • The construction's reliance on a single negative literal per clause suggests that reworking the clause gadget to be symmetric under literal permutations could make the reduction more robust, though the paper's current version depends on that ordering.
  • The same chain-of-cliques construction that yields claw-free $(2d+2)$-regular graphs with no $d$-cut may produce hard instances for related partition problems, such as internal partitions or generalized $(b,d)$-colourings, where analogous degree thresholds might appear.
  • Since the easy case is decided by a pure size bound, one could test computationally whether the constant $4d^2(2d+1)$ is tight by exhaustively searching small claw-free graphs with $\Delta\leq 2d+1$ for $d=2$ and $d=3$.
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.

Referee Report

2 major / 3 minor

Summary. The paper studies the d-Cut problem (a generalization of Matching Cut) on claw-free graphs. The main results are: (i) Theorem 3, stating that every claw-free graph with maximum degree at most 2d+1 and more than 4d^2(2d+1) vertices has a d-cut findable in linear time, together with arbitrarily large claw-free (2d+2)-regular graphs with no d-cut; (ii) Theorem 4, stating that for d>=2, d-Cut is constant-time solvable for claw-free graphs of maximum degree at most 2d+1 and NP-complete for claw-free graphs of maximum degree 2d+3, resolving Open Problem 1 for d=2; and (iii) Theorem 10, a generalization of the positive result to S_{1^t,l}-free graphs. The positive proofs are self-contained and based on a generalization of Chvatal's argument. The hardness proof reduces from NAE 3-Sat 0-1 using gadgets built from the no-instance graphs of Theorem 11.

Significance. If the identified gaps are repaired, the paper makes a solid contribution: it resolves the previously open case d=2 for claw-free graphs, gives a sharp maximum-degree dichotomy for claw-free graphs, and strengthens the earlier NP-completeness result for claw-free graphs by adding a bounded maximum degree. The positive results are carefully argued, the counting in Theorem 10 is consistent, and Theorem 11 provides a useful infinite family of claw-free regular no-instances. The paper would benefit from a small number of clarifications in the NP-hardness reduction, but the overall approach is sound and the main claims are highly plausible.

major comments (2)
  1. [Section 4, proof of Theorem 4 (NP-completeness part)] The reduction as written does not state the clause ordering on which the gadget depends. The text says only that each clause may be assumed to contain exactly one negative literal, but then asserts: 'Note that this implies that both xi2 and xi3 take the opposite value of xi1.' This implication is valid only if the unique negative literal is written first, so that the clause has the form (¬x_{i1} ∨ x_{i2} ∨ x_{i3}). If the negative literal is in position 2 or 3, the subsequent contradiction at ci is not obtained: a non-NAE clause can satisfy all local degree constraints, and the reduction as written is incomplete. The fix is local: explicitly normalize every clause to (¬x_{i1} ∨ x_{i2} ∨ x_{i3}) before building the gadget, and use xi1, xi2, xi3 for the variable indices of the three literals so that F_{i_j} and w_{i_j} are well-defined.
  2. [Section 4, first paragraph of the forward direction of Theorem 4] The sentence 'Recall that by Lemma 13, Fℓ is monochromatic for each ℓ' is not a direct consequence of Lemma 13. Lemma 13 is proved for the standalone graph H_{d,k,r}; in the constructed graph G, each free vertex of Fℓ has additional neighbours in a clause gadget, so the induced subgraph on V(Fℓ) is not isomorphic to H_{d,k,r}. This is repairable: the non-free vertices of Fℓ (the graph H of Theorem 11) have no external neighbours and remain monochromatic by the argument of Lemma 13, and each free vertex then has d+2 neighbours in that monochromatic set, so Observation 7 forces it to the same colour. Please add this justification explicitly, since the monochromaticity of each Fℓ is used to define the variable assignment.
minor comments (3)
  1. [Section 3, proof of Lemma 9] The sentence 'So when we colour v blue, that is, add v to B' appears to describe the wrong operation. The inequality |δ(B′\{v})| ≥ |δ(B′)| + 1 corresponds to removing a blue vertex (colouring it red), not adding one. I recommend rewording this passage to avoid confusion.
  2. [Section 4, Proposition 12] Proposition 12, which is load-bearing for the hardness result, is cited to an unpublished CoRR paper with three overlapping authors. Since the paper already remarks that a direct reduction from Matching Cut could be combined, I suggest adding a proof sketch or a published reference for the NP-completeness of NAE 3-Sat 0-1.
  3. [Section 4, construction in the proof of Theorem 4] The notation 'Ci = (xi1 ∨ xi2 ∨ xi3)' is ambiguous: xi1, xi2, xi3 sometimes denote literals and sometimes variable indices. After the normalization suggested in the major comment, please define explicitly that xi_j is the index of the variable of the j-th literal, with the first literal negated.

Circularity Check

1 steps flagged · score 2.0 of 10

NP-hardness proof leans on a self-cited NAE 3-Sat 0-1 result, but the core structural results are self-contained and the dependency is not an equivalence.

  1. self citation load bearing [Section 4, Proposition 12]
    "▶ Proposition 12 (Eagling-Vose et al. [9]) . NAE 3-Sat 0-1 is NP-complete."

    The NP-completeness direction of Theorem 4 reduces from NAE 3-Sat 0-1 and relies on Proposition 12 for the NP-completeness of that problem. Proposition 12 is cited to [9], a preprint by Eagling-Vose, Martin, Paulusma, and Smith, three of whom are authors of the present paper, and no proof is given here. The paper itself notes that the reduction from Matching Cut to NAE 3-Sat 0-1 in [9] could be composed with the new reduction, showing that the authors' prior work supplies the essential hardness bridge. This is a load-bearing self-citation in the written proof, though it is not an equivalence with the target d-Cut statement: the clause gadget is a new reduction and the positive results are independent.

full rationale

The paper's positive results (Lemma 9, Theorems 3, 10, 11, and the constant-time part of Theorem 4) are derived from explicit constructions, counting arguments, and claw-freeness observations, with no fitted parameters or hidden equivalences; they are self-contained. The NP-completeness half of Theorem 4 reduces from NAE 3-Sat 0-1 and invokes Proposition 12, cited only to the authors' own preprint [9] and not proved in this text. This is a load-bearing self-citation for the hardness direction as written, but it is not circular in the sense of the target result being assumed: the new clause gadget is a genuine reduction, and the paper explicitly notes that a direct composition with a Matching Cut reduction from [9] is available, so the central claim does not collapse into the citation. A separate non-circular correctness issue is that the gadget is asymmetric and the proof implicitly assumes the unique negative literal of each clause is listed first; the text only says each clause contains exactly one negative literal, not that it is ordered first. That is a repairable gap, not a circularity. Overall circularity is therefore low.

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

The central positive result is self-contained, built on Chvátal's matching-cut argument extended in Lemma 9. The hardness result rests on an external NP-completeness result cited to the authors' own paper, which is the main non-self-contained dependency.

assumptions (3)
  • domain assumption NAE 3-Sat 0-1 is NP-complete (Proposition 12)
    Used as the source for the Karp reduction in Theorem 4. Cited to Eagling-Vose et al. [9], which shares three authors with this paper; not proved here.
  • domain assumption Clauses in NAE 3-Sat 0-1 can be reordered so each has exactly one negative literal, and the proof's WLOG places that literal first
    The reduction defines an asymmetric gadget for positions w_{i1}, w_{i2}, w_{i3}; the correctness proof assumes the negative literal is the first variable. This reordering is implicit, not stated when the gadget is constructed.
  • standard math Standard Karp-reduction framework: a polynomial-time reduction from an NP-complete problem establishes NP-hardness
    Invoked implicitly in Section 4 to conclude NP-completeness of d-Cut.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Finding d-Cuts in Claw-free Graphs." pith.science (2026). https://pith.science/paper/T56OURSU

@misc{pith2026250517993,
  author       = {Pith},
  title        = {Pith review of: Finding d-Cuts in Claw-free Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/T56OURSU}},
  note         = {Machine review of arXiv:2505.17993}
}
abstract

The Matching Cut problem is to decide if the vertex set of a connected graph can be partitioned into two non-empty sets $B$ and $R$ such that the edges between $B$ and $R$ form a matching, that is, every vertex in $B$ has at most one neighbour in $R$, and vice versa. If for some integer $d\geq 1$, we allow every neighbour in $B$ to have at most $d$ neighbours in $R$, and vice versa, we obtain the more general problem $d$-Cut. It is known that $d$-Cut is NP-complete for every $d\geq 1$. However, for claw-free graphs, it is only known that $d$-Cut is polynomial-time solvable for $d=1$ and NP-complete for $d\geq 3$. We resolve the missing case $d=2$ by proving NP-completeness. This follows from our more general study, in which we also bound the maximum degree. That is, we prove that for every $d\geq 2$, $d$-Cut, restricted to claw-free graphs of maximum degree $p$, is constant-time solvable if $p\leq 2d+1$ and NP-complete if $p\geq 2d+3$. Moreover, in the former case, we can find a $d$-cut in linear time. We also show how our positive results for claw-free graphs can be generalized to $S_{1^t,l}$-free graphs where $S_{1^t,l}$ is the graph obtained from a star on $t+2$ vertices by subdividing one of its edges exactly $l$ times.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Finding $d$-Cuts in Probe $H$-Free Graphs

    cs.DS 2025-05 conditional novelty 7.0 of 10

    Complete complexity dichotomies are proven for d-Cut, Perfect Matching Cut, and Maximum Matching Cut on partitioned probe H-free graphs.

Reference graph

Works this paper leans on

24 extracted references · 23 canonical work pages · cited by 1 Pith paper

  1. [1]

    N. R. Aravind, Subrahmanyam Kalyanasundaram, and Anjeneya Swami Kare. Vertex partitioning problems on graphs with bounded tree width. Discrete Applied Mathematics , 319:254--270, 2022

    work page 2022

  2. [2]

    N. R. Aravind and Roopam Saxena. An F P T algorithm for M atching C ut and d - C ut. Proc. IWOCA 2021, LNCS , 12757:531--543, 2021

    work page 2021

  3. [3]

    Internal partitions of regular graphs

    Amir Ban and Nati Linial. Internal partitions of regular graphs. Journal of Graph Theory , 83:5--18, 2016

    work page 2016

  4. [4]

    Cutting B arnette graphs perfectly is hard

    Edouard Bonnet, Dibyayan Chakraborty, and Julien Duron. Cutting B arnette graphs perfectly is hard. Proc. WG 2023, LNCS , 14093:116--129, 2023

    work page 2023

  5. [5]

    Paul S. Bonsma. The complexity of the M atching- C ut problem for planar graphs and other graph classes. Journal of Graph Theory , 62:109--126, 2009

    work page 2009

  6. [6]

    The complexity of the P erfect M atching- C ut problem

    Valentin Bouquet and Christophe Picouleau. The complexity of the P erfect M atching- C ut problem. Journal of Graph Theory , 108, 2025

    work page 2025

  7. [7]

    Matching C ut in graphs with large minimum degree

    Chi - Yeh Chen, Sun - Yuan Hsieh, Ho \` a ng - Oanh Le, Van Bang Le, and Sheng - Lung Peng. Matching C ut in graphs with large minimum degree. Algorithmica , 83:1238--1255, 2021

    work page 2021

  8. [8]

    Recognizing decomposable graphs

    Vasek Chv \' a tal. Recognizing decomposable graphs. Journal of Graph Theory , 8:51--53, 1984

    work page 1984

Show all 24 references
  1. [9]

    A forbidden subgraph study for cut problems on graphs permitting loops and multiedges

    Tala Eagling-Vose, Barnaby Martin, Daniel Paulusma, and Siani Smith. A forbidden subgraph study for cut problems on graphs permitting loops and multiedges. CoRR , abs/2502.07769, 2025

    2025

  2. [10]

    Matching cuts in graphs of high girth and H -free graphs

    Carl Feghali, Felicia Lucke, Dani\"el Paulusma, and Bernard Ries. Matching cuts in graphs of high girth and H -free graphs. Proc. ISAAC 2023, LIPIcs , 283:28:1--28:16, 2023

    2023

  3. [11]

    Golovach, Christian Komusiewicz, Dieter Kratsch, and Van Bang Le

    Petr A. Golovach, Christian Komusiewicz, Dieter Kratsch, and Van Bang Le. Refined notions of parameterized enumeration kernels with applications to matching cut enumeration. Journal of Computer and System Sciences , 123:76--102, 2022

    2022

  4. [12]

    Finding cuts of bounded degree: complexity, F P T and exact algorithms, and kernelization

    Guilherme Gomes and Ignasi Sau. Finding cuts of bounded degree: complexity, F P T and exact algorithms, and kernelization. Algorithmica , 83:1677--1706, 2021

    2021

  5. [13]

    Guilherme C. M. Gomes, Emanuel Juliano, Gabriel Martins, and Vin \' cius Fernandes dos Santos. Matching (multi)cut: Algorithms, complexity, and enumeration. Proc. IPEC 2024, LIPIcs , 321:25:1--25:15, 2024

    2024

  6. [14]

    Partitioning graphs into generalized dominating sets

    Pinar Heggernes and Jan Arne Telle. Partitioning graphs into generalized dominating sets. Nordic Journal of Computing , 5:128--142, 1998

    1998

  7. [15]

    Matching C ut: Kernelization, single-exponential time FPT , and exact exponential algorithms

    Christian Komusiewicz, Dieter Kratsch, and Van Bang Le. Matching C ut: Kernelization, single-exponential time FPT , and exact exponential algorithms. Discrete Applied Mathematics , 283:44--58, 2020

    2020

  8. [16]

    Algorithms solving the M atching C ut problem

    Dieter Kratsch and Van Bang Le. Algorithms solving the M atching C ut problem. Theoretical Computer Science , 609:328--335, 2016

    2016

  9. [17]

    Complexity results for matching cut problems in graphs without long induced paths

    Ho \` a ng - Oanh Le and Van Bang Le. Complexity results for matching cut problems in graphs without long induced paths. Proc. WG 2023, LNCS , 14093:417--431, 2023

    2023

  10. [18]

    The P erfect M atching C ut problem revisited

    Van Bang Le and Jan Arne Telle. The P erfect M atching C ut problem revisited. Theoretical Computer Science , 931:117--130, 2022

    2022

  11. [19]

    Finding minimum matching cuts in H -free graphs and graphs of bounded radius and diameter

    Felicia Lucke, Joseph Marchand, and Jannik Olbrich. Finding minimum matching cuts in H -free graphs and graphs of bounded radius and diameter. CoRR , abs/2502.18942, 2025

    2025

  12. [20]

    Finding d -cuts in graphs of bounded diameter, graphs of bounded radius and H -free graphs

    Felicia Lucke, Ali Momeni, Dani \"e l Paulusma, and Siani Smith. Finding d -cuts in graphs of bounded diameter, graphs of bounded radius and H -free graphs. Proc. WG 2024, LNCS , 14760:415--429, 2024. full version: arXiv:2404.11389

    2024

  13. [21]

    On the complexity of M atching C ut for graphs of bounded radius and H -free graphs

    Felicia Lucke, Dani\"el Paulusma, and Bernard Ries. On the complexity of M atching C ut for graphs of bounded radius and H -free graphs. Theoretical Computer Science , 936, 2022

    2022

  14. [22]

    Finding matching cuts in H -free graphs

    Felicia Lucke, Dani \" e l Paulusma, and Bernard Ries. Finding matching cuts in H -free graphs. Algorithmica , 85:3290--3322, 2023

    2023

  15. [23]

    Dichotomies for maximum matching cut: H -freeness, bounded diameter, bounded radius

    Felicia Lucke, Dani \"e l Paulusma, and Bernard Ries. Dichotomies for maximum matching cut: H -freeness, bounded diameter, bounded radius. Theoretical Computer Science , 1017:114795, 2024

    2024

  16. [24]

    Augustine M. Moshi. Matching cutsets in graphs. Journal of Graph Theory , 13:527--536, 1989

    1989

Pith tools

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