2026-07-21T03:13:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24912 2026-02-09T08:01:56Z ddc:004 open_access

Finding d-Cuts in Claw-Free Graphs Ahn, Jungho Eagling-Vose, Tala Lucke, Felicia Paulusma, Daniël Smith, Siani matching cut d-cut claw-free maximum degree 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 ≥ 1, we allow every vertex 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 ≥ 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 ≥ 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 ≥ 2, d-Cut, restricted to claw-free graphs of maximum degree p, is constant-time solvable if p ≤ 2d+1 and NP-complete if p ≥ 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,𝓁}-free graphs where S_{1^t,𝓁} is the graph obtained from a star on t+2 vertices by subdividing one of its edges exactly 𝓁 times. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jungho Ahn and Tala Eagling-Vose and Felicia Lucke and Daniël Paulusma and Siani Smith 2025 Is Part Of LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2025.4 urn:nbn:de:0030-drops-249121 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.4 eng https://creativecommons.org/licenses/by/4.0/legalcode