Pith. sign in

REVIEW 1 major objections 4 minor 29 references

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

T0 review · 1 major / 4 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 For every forbidden graph H, d-cut on probe H-free graphs is now fully classified.

desk verdict Solid complete dichotomies for cut problems on probe H-free graphs, with a non-load-bearing overclaim in Theorem 13 that the authors should fix. read the letter →

arxiv 2505.22351 v1 pith:CGPCX65E submitted 2025-05-28 cs.DS cs.CCcs.DMmath.CO

Konrad K. Dabrowski , Tala Eagling-Vose , Matthew Johnson , Giacomo Paesani , Daniël Paulusma This is my paper
classification cs.DScs.CCcs.DMmath.CO MSC 68Q1705C85
keywords d-CutMatchingCutPerfectMaximumprobegraphsH-freecomplexitydichotomycolour-processing
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 studies d-Cut (the problem of finding an edge cut so that each vertex has at most d neighbours on the other side), along with Perfect Matching Cut and Maximum Matching Cut, on partitioned probe H-free graphs: graphs with a distinguished independent set of non-probes whose missing edges can be completed to make the graph H-free. The main result is a complete dichotomy, Theorem 4: 1-Cut, Perfect Matching Cut, and Maximum Matching Cut are polynomial-time solvable on partitioned probe H-free graphs exactly when H is an induced subgraph of $sP_1+P_4$ for some $s\geq 0$, and NP-complete for every other H; for every $d\geq 2$, d-Cut is polynomial-time solvable exactly when H is an induced subgraph of $P_1+P_4$, and NP-complete otherwise. This settles, for every fixed H and every d, what happens when the classical H-free results are moved to the probe model that allows missing edge information. The significance is that the boundary between tractable and intractable is much steeper in the probe setting: even $H=2P_2$ becomes NP-complete for 1-Cut, and $H=4P_1$ becomes NP-complete for all $d\geq 2$.

What carries the argument

The machinery that carries the argument is the red-blue d-colouring characterisation of d-cuts (Observation 5), together with the colour-processing rules R1 and R2 from Lemma 6: if a vertex already has $d+1$ neighbours forced red, it must be blue, and vice versa. In the positive direction, the algorithms repeatedly guess the colouring of the closed neighbourhood of a constant-size set $Q$, exploiting that every vertex has at most $d$ opposite-colour neighbours and hence only $O(n^{cd})$ branches are needed. The structural heart is that in a probe $(P_1+P_4)$-free graph the probe subgraph $G[P]$ is a cograph (P4-free), and Lemma 10 shows that in any red-blue d-colouring of a cograph one colour class has size at most $2d$; this constant bound lets the algorithm guess the small colour class and reduce the remaining problem to colouring an independent set, which is easy. In the hardness direction, the central objects are the gadget constructions: replacing edges by pairs of intermediate vertices (Theorem 12), four-time subdivision (Theorem 13), split-graph completions (Theorem 14), and a 3-SAT gadget (Theorem 15).

What would settle it

To test the weakest point, take the cube graph (a cubic bipartite planar graph), subdivide every edge four times, and attempt the claimed completion at each vertex; if any instance forces a choice that creates an induced claw or diamond or destroys planarity, the argument in Theorem 13 needs repair. More broadly, brute-force search over all small connected probe $(P_1+P_4)$-free graphs can check whether the Theorem 11 algorithm ever fails to find a 2-cut when a red-blue 2-colouring exists, which would contradict the dichotomy's polynomial side.

Watch

Extended reading notes

Core claim

The paper claims Theorem 4: for every graph H, the computational complexity of d-Cut on partitioned probe H-free graphs is fully determined by whether H is an induced subgraph of $P_1+P_4$ (for $d\geq 2$) or of $sP_1+P_4$ for some $s\geq 0$ (for $d=1$, Perfect Matching Cut, and Maximum Matching Cut). In the polynomial cases the paper gives explicit algorithms that, given a certified completion, guess a constant-size coloured set and propagate the rest of a red-blue d-colouring; in the NP-complete cases it constructs, for each offending H, a probe graph that is H-free after adding edges among non-probes and whose d-cut answers encode a known hard problem. Because every H-free graph is a partitioned probe H-free graph with empty non-probe set, the hardness side automatically includes all prior H-free NP-completeness results, while the algorithmic side genuinely extends the tractable classes. The net effect is that the probe version of all three problems is now classified for every H and every d.

Load-bearing premise

The load-bearing premise is the assertion in the proof of Theorem 13 that, starting from a cubic bipartite planar graph, subdividing each edge four times and adding exactly one edge among the two intermediate-close neighbours at each original vertex can always be done to keep the graph planar and $(K_{1,3},2P_1+P_2)$-free; this is stated as 'readily seen' and the Perfect Matching Cut hardness on probe $K_{1,3}$-free graphs depends on it.

Editorial extensions

If this is right

  • For 1-Cut, Perfect Matching Cut, and Maximum Matching Cut, any H that is not an induced subgraph of some $sP_1+P_4$ makes the problem NP-complete on partitioned probe H-free graphs.
  • For $d\geq 2$, only H an induced subgraph of $P_1+P_4$ keeps d-Cut polynomial; already $H=4P_1$ (four isolated vertices) makes d-Cut NP-complete for every $d\geq 2$.
  • Comparing with the known H-free dichotomies, the probe model makes all three problems strictly harder unless P=NP: for example, 1-Cut is polynomial on $2P_2$-free graphs but NP-complete on probe $2P_2$-free graphs, and d-Cut is polynomial on $4P_1$-free graphs for $d\geq2$ but NP-complete on probe $4P_1$-free graphs.
  • The polynomial-time algorithms are constructive: they output an actual red-blue d-colouring, a maximum matching cut, or a perfect matching cut when one exists.

Reading between the lines

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

  • The paper works with partitioned inputs, where the probe set P and non-probe set N are given; the same dichotomies are not automatic for non-partitioned probe graphs, because recognising probe H-free graphs is still open for most H, so a natural next step is to test whether the d-Cut thresholds survive when P and N must be guessed.
  • The colour-processing plus small-colour-class strategy is not obviously tied to these three problems: the same style could yield threshold dichotomies for other cut variants that bound each vertex's opposite-colour degree, such as weighted or list-coloured versions of d-Cut.
  • The one 'readily seen' planarity claim in Theorem 13 is the point that most deserves independent checking; if it fails on some cubic bipartite planar graph, the Perfect Matching Cut hardness on probe $K_{1,3}$-free graphs would still seem plausible but would need a different gadget construction.
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

1 major / 4 minor

Summary. The paper studies d-Cut (with 1-Cut being Matching Cut), Perfect Matching Cut, and Maximum Matching Cut on partitioned probe H-free graphs. In this model, the input is a graph G with a probe set P and an independent non-probe set N, and the promise is that some set F of edges between non-probes can be added so that G+F is H-free. The main result, Theorem 4, is a complete dichotomy: for d = 1 and for Perfect and Maximum Matching Cut, the problem is polynomial-time solvable exactly when H is an induced subgraph of sP1+P4 for some s ≥ 0 and NP-complete otherwise; for d ≥ 2, d-Cut is polynomial-time solvable exactly when H is an induced subgraph of P1+P4 and NP-complete otherwise. The positive results are obtained in Section 3 by colour-processing and bounded branching over small colour-class-defining sets, and the hardness results are proved in Section 4 by reductions from known NP-complete cases, with new probe-class hardness for 2P2-free, K1,3-free, split, and 4P1-free graphs.

Significance. If correct, Theorem 4 is a strong and complete complexity dichotomy. It extends the known H-free results to the probe model with a clean threshold: sP1+P4 for the matching-cut variants and P1+P4 for d ≥ 2. The polynomial algorithms are nontrivial and are presented in detail, with no fitted parameters, and the hardness proofs assemble known theorems and external reductions. The central derivation is not circular. The main defect is local: Theorem 13 overclaims (2P1+P2)-freeness, and the statement as written is false. However, the K1,3-free consequence used in Theorem 4 is sound, so the central dichotomy is not damaged.

major comments (1)
  1. [§4, Theorem 13] The assertion that the constructed graph G′+F is (K1,3,2P1+P2)-free is stated without proof ('readily seen') and is false under the standard definition of 2P1+P2 as the disjoint union of P2 and two isolated vertices. For a cubic input G, fix an original vertex u incident with three edges e1, e2, e3. The four vertices y2_{e1}, y3_{e1}, y4_{e2}, y1_{e3} induce a 2P1+P2 in G′+F regardless of the choice of F, because F only joins intermediate-close vertices that share an original neighbour and no two of these four vertices have that property. Thus Theorem 13 as stated is overstrong. The weaker statement needed for Theorem 4, namely NP-completeness on probe K1,3-free graphs, is sound: at each original vertex the three y1-neighbours receive one F-edge, so no vertex has three pairwise nonadjacent neighbours, and planarity and subcubicity are clear from the construction. The authors should delete the (2P1+P2)-free part from the theorem, or, if the intended forbidden graph is the diamond, state and prove that claim. They should also replace 'readily seen' with an explicit argument and specify that the F-edge at each original vertex is chosen between two consecutive intermediate-close neighbours in the cyclic order, which makes the planarity assertion immediate.
minor comments (4)
  1. [§2, colour-processing rules] The two propagation rules are both labelled R1; the second should be R2.
  2. [§4, paragraph before Theorem 13] The sentence 'The diamond 2P1 + P2 is obtained from taking the complement of 2P1 + P2' is garbled; the diamond is the complement of 2P1+P2, not a graph called 'diamond 2P1+P2'.
  3. [§4, proof of Theorem 13] The phrase 'while maintaining planarity' is not justified; choosing the F-edge between two consecutive intermediate-close neighbours in the local cyclic order at each original vertex resolves this.
  4. [§3, proof of Theorem 11] The branching counts such as O(n^{4d^2}) in Case 11.2 are asserted without derivation; adding a short counting explanation would make the polynomial bound easier to verify.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the probe dichotomy is assembled from external prior theorems and direct reductions, not from the paper's own conclusion; the main caveat, an unproved freeness claim in Theorem 13, is a correctness gap rather than a circular step.

full rationale

The derivation chain is self-contained in the relevant sense. The polynomial-time results (Lemma 7, Lemma 8, Theorems 9 and 11) are proved directly via colour-processing, dominating pairs, cograph structure, and the definition of the probe classes; they do not assume Theorem 4. The NP-completeness results are reductions from independent NP-complete problems and prior H-free dichotomies: Matching Cut, Perfect Matching Cut on cubic bipartite planar graphs, d-Cut on bipartite graphs, and 3-SAT, citing Chvátal, Moshi, Le and Telle, Bonsma, Lucke et al., and others. The probe certificate F is constructed and checked in each reduction rather than defined by the target property. The statement in Theorem 13 that a planar completion is 'readily seen' to preserve (K1,3,2P1+P2)-freeness is an omitted proof and a potential correctness issue, but it is not a circular reduction, and the K1,3-free hardness used for Theorem 4 does not depend on the 2P1+P2 clause. Self-citations appear, including refs. [1] and [23], but they are citation of external proof-carrying results, not an assumption of the paper's own dichotomy. No fitted parameter is relabelled as a prediction, and no load-bearing uniqueness theorem is imported from the present authors. Thus no circular step can be exhibited.

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

No free parameters are fit to data; the paper is a pure complexity classification. The axioms are standard NP-completeness results and prior dichotomies that the new results build on. The only seemingly ad hoc element is the planar edge-selection in Theorem 13, which is not an axiom but an unproven construction detail, and is flagged separately.

assumptions (8)
  • domain assumption Darmann and Döcker's restricted 3-SAT variant (each variable appears twice positively and twice negatively, clauses are all-positive or all-negative) is NP-complete.
    Used in Theorem 15 as the source problem for the d-Cut NP-completeness reduction on probe 4P1-free graphs.
  • domain assumption Perfect Matching Cut is NP-complete on cubic bipartite planar graphs (Bonnet, Chakraborty, Duron).
    Used in Theorem 13 as the source problem for the Perfect Matching Cut hardness on probe (K1,3,2P1+P2)-free graphs.
  • domain assumption Moshi's equivalence: replacing an edge by two intermediate vertices preserves the existence of a matching cut.
    Used in Theorem 12 to transfer 1-Cut hardness to the probe K1,3-free construction.
  • domain assumption Le-Telle equivalence: subdividing an edge four times preserves the existence of a perfect matching cut.
    Used in Theorem 13 to transfer Perfect Matching Cut hardness to the subdivided graph.
  • domain assumption Known dichotomies for d-Cut, Perfect Matching Cut, and Maximum Matching Cut on H-free graphs (Theorems 1-3).
    The paper inherits NP-completeness for probe H-free graphs when H is large enough; the prior classifications are cited to [1,5,9,13,20,22,23,24,25,26,27].
  • domain assumption Lemma 21 of Lucke et al. [26]: a polynomial-time algorithm exists for Maximum Matching Cut when the uncoloured vertices form an independent set.
    Invoked in Lemma 7 to finish the polynomial-time algorithm for Maximum Matching Cut.
  • standard math Cographs (P4-free graphs) have a spanning complete bipartite subgraph.
    Used in the proof of Lemma 10 to bound the size of a colour class.
  • standard math Courcelle-Makowsky-Rotics meta-theorem: MSO1-definable problems are linear-time on graphs of bounded clique-width.
    Used in Lemma 8 as an alternative proof for Perfect Matching Cut on probe P4-free graphs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Finding $d$-Cuts in Probe $H$-Free Graphs." pith.science (2026). https://pith.science/paper/CGPCX65E

@misc{pith2026250522351,
  author       = {Pith},
  title        = {Pith review of: Finding $d$-Cuts in Probe $H$-Free Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CGPCX65E}},
  note         = {Machine review of arXiv:2505.22351}
}
abstract

For an integer $d\geq 1$, the $d$-Cut problem is that of deciding whether a graph has an edge cut in which each vertex is adjacent to at most $d$ vertices on the opposite side of the cut. The $1$-Cut problem is the well-known Matching Cut problem. The $d$-Cut problem has been extensively studied for $H$-free graphs. We extend these results to the probe graph model, where we do not know all the edges of the input graph. For a graph $H$, a partitioned probe $H$-free graph $(G,P,N)$ consists of a graph $G=(V,E)$, together with a set $P\subseteq V$ of probes and an independent set $N=V\setminus P$ of non-probes such that we can change $G$ into an $H$-free graph by adding zero or more edges between vertices in $N$. For every graph $H$ and every integer $d\geq 1$, we completely determine the complexity of $d$-Cut on partitioned probe $H$-free graphs.

Figures

Figures reproduced from arXiv: 2505.22351 by the authors.

Figure 1
Figure 1. A graph G with a set P of probes. The set F is the set of dashed edges. The blue-red colouring corresponds to a 2-cut of G and a 3-cut in G + F. at most d blue neighbours, then the edge cut M is said to be a d-cut of G. See also [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. The graphs sP1 + P4, K1,3 and H∗ i , from left to right. second is to decide if a connected graph has a perfect matching cut, that is, an edge cut that is a perfect matching. This problem is also NP-complete [19]. Known Results. For two vertex-disjoint graphs G1 and G2, let G1 + G2 = (V (G1) ∪ V (G2), E(G1) ∪ E(G2)). We let sG be the disjoint union of s copies of G. We write G1 ⊆i G2 if G1 is an induced subgraph of … view at source ↗
Figure 3
Figure 3. Illustration of Case 11.2. Lines represent edges and [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: Illustration of the types described in Case 11.3, spe [PITH_FULL_IMAGE:figures/full_fig_p010_4.png]
Figure 5
Figure 5. Figure 5: A P-dominating pair {u, v}. can consider all O(n d 2 ) possible red-blue colourings of the neighbourhood of C1 in N. Afterwards, all uncoloured vertices in N have received a colour (as they were all complete to C1). It remains to check whether the obtained colouring of…
Figure 6
Figure 6. Figure 6: Illustration of Case 11.3.3, where there is a [PITH_FULL_IMAGE:figures/full_fig_p014_6.png]
Figure 7
Figure 7. Figure 7: An example of a graph G from the proof of Theorem 12 with edges uv, vw and wz, together with the graph G′ + F, where the edges of F are blue. From the above, we conclude that there are no uncoloured vertices, and we have obtained a red-blue colouring of G. It now remai…
Figure 8
Figure 8. Figure 8: An example of a graph G from the proof of Theorem 13, together with the graphs G′ and G′ + F, from left to right, where the edges of F are coloured blue. Proof. We reduce from 1-Cut, which we recall is NP-complete [9]. From a con￾nected graph G = (V, E) we construct a …
Figure 9
Figure 9. Figure 9: An example of a graph G in the proof of Theorem 15, namely when X = {x1, . . . , x6} and C = {{x1, x2, x3}, {x1, x3, x4}, {x2, x5, x6}, {x4, x5, x6}} ∪ {{x1, x2, x4}, {x1, x3, x5}, {x2, x4, x6}, {x3, x5, x6}}. For readability the edges in￾side the cliques K and K′ are …

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

29 extracted references · 28 canonical work pages

  1. [1]

    Finding d-Cuts in Claw-free Graphs

    Ahn, J., Eagling-Vose, T., Lucke, F., Paulusma, D., Smith , S.: Finding d-cuts in claw-free graphs. CoRR arXiv:2505.17993 (2025) Finding d-Cuts in Probe H-Free Graphs 19

    work page Pith review arXiv 2025

  2. [2]

    Dis- crete Applied Mathematics 160, 2502–2513 (2012)

    Araújo, J., Cohen, N., Giroire, F., Havet, F.: Good edge-l abelling of graphs. Dis- crete Applied Mathematics 160, 2502–2513 (2012)

    work page 2012

  3. [3]

    SIAM Journal on Discrete Mathem atics 21, 573–591 (2007)

    Berry, A., Golumbic, M.C., Lipshteyn, M.: Recognizing ch ordal probe graphs and cycle-bicolorable graphs. SIAM Journal on Discrete Mathem atics 21, 573–591 (2007)

    work page 2007

  4. [4]

    Bonnet, E., Chakraborty, D., Duron, J.: Cutting Barnette graphs perfectly is hard. Proc. WG 2023, LNCS 14093, 116–129 (2023)

    work page 2023

  5. [5]

    Journal of Graph Theory 62, 109–126 (2009)

    Bonsma, P.S.: The complexity of the Matching-Cut problem for planar graphs and other graph classes. Journal of Graph Theory 62, 109–126 (2009)

    work page 2009

  6. [6]

    Theo retical Computer Sci- ence 1032, 115088 (2025), conference version in Proc

    Brettell, N., Oostveen, J.J., Pandey, S., Paulusma, D., R auch, J., van Leeuwen, E.J.: Computing subset vertex covers in h-free graphs. Theo retical Computer Sci- ence 1032, 115088 (2025), conference version in Proc. FCT 2024

    work page 2025

  7. [7]

    Discrete Applied Mathematics 157, 2611–2619 (2009)

    Chandler, D.B., Chang, M., Kloks, T., Liu, J., Peng, S.: On probe permutation graphs. Discrete Applied Mathematics 157, 2611–2619 (2009)

    work page 2009

  8. [8]

    Chang, M., Kloks, T., Kratsch, D., Liu, J., Peng, S.: On the recognition of probe graphs of some self-complementary classes of perfect graph s. Proc. COCOON 2005, Lecture Notes in Computer Science 3595, 808–817 (2005)

    work page 2005

Show all 29 references
  1. [9]

    Journal o f Graph Theory 8, 51–53 (1984)

    Chvátal, V.: Recognizing decomposable graphs. Journal o f Graph Theory 8, 51–53 (1984)

    1984

  2. [10]

    Theory of Computing Systems 33, 125– 150 (2000)

    Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time s olvable optimization prob- lems on graphs of bounded clique-width. Theory of Computing Systems 33, 125– 150 (2000)

    2000

  3. [11]

    Discrete Applied Mathematics 292, 45–58 (2021)

    Darmann, A., Döcker, J.: On simplified NP-complete varia nts of Monotone 3-Sat. Discrete Applied Mathematics 292, 45–58 (2021)

    2021

  4. [12]

    Net- works 12, 393–403 (1982)

    Farley, A.M., Proskurowski, A.: Networks immune to isol ated line failures. Net- works 12, 393–403 (1982)

    1982

  5. [13]

    Feghali, C., Lucke, F., Paulusma, D., Ries, B.: Matching cuts in graphs of high girth and H-free graphs. Proc. ISAAC 2023, LIPIcs 283, 28:1–28:16 (2023)

    2023

  6. [14]

    Theoretical Computer S cience 457, 86–100 (2012)

    Golovach, P.A., Paulusma, D., Song, J.: Computing verte x-surjective homomor- phisms to partially reflexive trees. Theoretical Computer S cience 457, 86–100 (2012)

    2012

  7. [15]

    Di screte Applied Mathe- matics 143, 221–237 (2004)

    Golumbic, M.C., Lipshteyn, M.: Chordal probe graphs. Di screte Applied Mathe- matics 143, 221–237 (2004)

    2004

  8. [16]

    Annals of Operations Research 188, 175–183 (2011)

    Golumbic, M.C., Maffray, F., Morel, G.: A characterizati on of chain probe graphs. Annals of Operations Research 188, 175–183 (2011)

    2011

  9. [17]

    Algorithmica 83, 1677–1706 (2021)

    Gomes, G., Sau, I.: Finding cuts of bounded degree: compl exity, FPT and exact algorithms, and kernelization. Algorithmica 83, 1677–1706 (2021)

    2021

  10. [18]

    Annals of the New York Academy of Sciences 175, 170–186 (1970)

    Graham, R.L.: On primitive graphs and optimal vertex ass ignments. Annals of the New York Academy of Sciences 175, 170–186 (1970)

    1970

  11. [19]

    Nordic Journal of Computing 5, 128–142 (1998)

    Heggernes, P., Telle, J.A.: Partitioning graphs into ge neralized dominating sets. Nordic Journal of Computing 5, 128–142 (1998)

    1998

  12. [20]

    Le, H., Le, V.B.: Complexity results for matching cut pro blems in graphs without long induced paths. Proc. WG 2023, LNCS 14093, 417–431 (2023)

    2023

  13. [21]

    Theoretical Computer Science 931, 117–130 (2022)

    Le, V.B., Telle, J.A.: The Perfect Matching Cut problem r evisited. Theoretical Computer Science 931, 117–130 (2022)

    2022

  14. [22]

    CoRR abs/2502.18942 (2025)

    Lucke, F., Marchand, J., Olbrich, J.: Finding minimum ma tching cuts in H- free graphs and graphs of bounded radius and diameter. CoRR abs/2502.18942 (2025)

    2025

  15. [23]

    Lucke, F., Momeni, A., Paulusma, D., Smith, S.: Finding d-cuts in graphs of bounded diameter, graphs of bounded radius and H-free graphs. Proc. WG 2024, LNCS 14760, 415–429 (2025) 20 K.K. Dabrowski, T. Eagling-Vose, M. Johnson, G. Paesani, D. Paulusma

    2025

  16. [24]

    Theoretical Computer Science 936, 33–42 (2022)

    Lucke, F., Paulusma, D., Ries, B.: On the complexity of Ma tching Cut for graphs of bounded radius and H-free graphs. Theoretical Computer Science 936, 33–42 (2022)

    2022

  17. [25]

    Algo- rithmica 85, 3290–3322 (2023)

    Lucke, F., Paulusma, D., Ries, B.: Finding matching cuts in H-free graphs. Algo- rithmica 85, 3290–3322 (2023)

    2023

  18. [26]

    Theoretical C omputer Science 1017, 114795 (2024)

    Lucke, F., Paulusma, D., Ries, B.: Dichotomies for Maxim um Matching Cut: H- freeness, bounded diameter, bounded radius. Theoretical C omputer Science 1017, 114795 (2024)

    2024

  19. [27]

    Journal of Grap h Theory 13, 527–536 (1989)

    Moshi, A.M.: Matching cutsets in graphs. Journal of Grap h Theory 13, 527–536 (1989)

    1989

  20. [28]

    Patrignani, M., Pizzonia, M.: The complexity of the Matc hing-Cut problem. Proc. WG 2001, LNCS 2204, 284–295 (2001)

    2001

  21. [29]

    Computer Applications in the Biosciences 10, 309–317 (1994)

    Zhang, P., Schon, E.A., Fischer, S.G., Cayanis, E., Weis s, J., Kistler, S., Bourne, P.E.: An algorithm based on graph theory for the assembly of c ontigs in physical mapping of DNA. Computer Applications in the Biosciences 10, 309–317 (1994)

    1994

Pith tools

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