Pith. sign in

REVIEW 2 major objections 2 minor 90 references

Vertex splitting to cographs, P_t-free graphs, chordal graphs, and unit interval graphs is NP-complete under general, exclusive, and shallow splits, with strong ETH lower bounds.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-02 04:58 UTC pith:E4NVXJTE

load-bearing objection Solid hardness paper that settles several open vertex-splitting questions, but the Chordal-VS forward direction has a repairable gap in its split sequence and needs a careful rewrite before the proof is fully valid. the 2 major comments →

arxiv 2607.13517 v1 pith:E4NVXJTE submitted 2026-07-15 cs.DS math.CO

Hardness of Vertex Splitting: Cographs, Chordal Graphs, and Beyond

Satyabrata Jana , Shivesh K. Roy , R. B. Sandeep This is my paper
classification cs.DS math.CO MSC 05C8568Q17
keywords vertex splittingNP-completenesscographsP_t-free graphschordal graphsunit interval graphsexponential time hypothesisparameterized complexity
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper establishes that deciding whether a graph can be made to satisfy any of several natural hereditary properties using at most k vertex splits is NP-complete. The target classes are cographs, P_t-free graphs for every fixed t≥4, chordal graphs, and unit interval graphs. Under the Exponential Time Hypothesis, none of these problems admits a 2^{o(k)} n^{O(1)} algorithm, and all but the unit-interval cases also exclude 2^{o(n)} algorithms. These results show that vertex splitting cannot yield efficient exact algorithms for these target classes, even when splits are required to be exclusive or shallow.

Core claim

The central claim is that vertex splitting, a graph modification operation that replaces a vertex by two nonadjacent vertices whose neighborhoods together equal the original neighborhood, is computationally intractable for several target classes that are otherwise algorithmically tame. For cographs the hardness holds even on subcubic graphs of arbitrarily large girth, and for P_t-free graphs it holds for every fixed t≥4. The proof connects arbitrary splits to exclusive splits on high-girth graphs, then to edge partition problems in which the total split count equals the sum over vertices of the number of parts containing that vertex minus one. Chordal vertex splitting is reduced to chain ver

What carries the argument

The central mechanism is a chain of polynomial equivalences and reductions. On graphs of girth at least t+1, arbitrary and exclusive splits coincide for P_t-free targets through a lemma that chooses one representative edge between each pair of descendant sets and shows the resulting spanning subgraph remains P_t-free; the girth bound forbids an induced P_t that would otherwise arise from a short cycle. For cographs, exclusive splitting is equivalent to a star edge partition with vertex cost, and the cost formula cost(P)=m+r-n ties the split count to vertex cover size. For P_5-free graphs, the analogous object is a double-star edge partition, tied to edge dominating set. Chordal hardness uses

Load-bearing premise

The load-bearing premise is the lemma that on graphs of girth at least t+1 the general and exclusive versions of P_t-free vertex splitting coincide (and, for the unit-interval result, the cited characterization of colored unit 2-interval graphs); if either gives way, the corresponding NP-completeness proof collapses.

What would settle it

Enumerate all split sequences for small high-girth graphs (for instance, all graphs with girth at least 5 and up to 12 vertices) and check whether any instance is a YES instance of P_t-free-VS but a NO instance of P_t-free-EVS; such a pair would refute the equivalence lemma directly.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • For each target class considered, no polynomial-time algorithm exists unless P=NP.
  • Under ETH, none of the problems admits a 2^{o(k)} n^{O(1)} algorithm, so the split budget k does not provide useful fixed-parameter tractability.
  • Except for unit-interval vertex splitting, the lower bound strengthens to 2^{o(n)}, ruling out subexponential algorithms in the number of input vertices.
  • The hardness survives the exclusive, shallow, and shallow-exclusive restrictions, so restricting the operation itself does not restore tractability.
  • Cograph vertex splitting remains hard even on subcubic graphs with girth at least 5, and P_5-free vertex splitting on high-girth graphs with at least as many edges as vertices.

Where Pith is reading between the lines

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

  • The high-girth equivalence between arbitrary and exclusive splits may be a reusable template: any hereditary class whose members decompose into components of bounded diameter could inherit hardness through the same representative-edge argument.
  • The unit-interval bound of only 2^{o(√n)} leaves a gap; a natural next target is to determine whether the true complexity is 2^{Θ(√n)} or can be strengthened to 2^{o(n)} by another reduction.
  • The exact cost formula connecting star edge partitions to vertex covers suggests that approximation lower bounds for vertex cover and edge dominating set could carry over to the minimum number of splits, though the paper does not state such a transfer.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 2 minor

Summary. The paper studies vertex splitting, the operation that replaces a vertex by two nonadjacent vertices whose neighborhoods partition the original neighborhood, and proves NP-completeness and ETH lower bounds for several target classes. The main results are: Cograph Vertex Splitting and Cograph-EVS are NP-complete on subcubic graphs of arbitrarily large girth; P_t-free Vertex Splitting and its exclusive/shallow variants are NP-complete for every fixed t≥4; Chordal Vertex Splitting and its variants are NP-complete; and Unit-Interval Vertex Splitting and Unit-Interval-SVS are NP-complete. For cographs and P_5-free graphs the hardness is obtained through polynomial equivalences with star and double-star edge partition problems on high-girth graphs, while the chordal and unit-interval results use reductions from Chain Vertex Deletion and Colored Unit 2-interval Recognition. ETH lower bounds are claimed for all problems.

Significance. If the results are correct, they resolve several explicitly posed open problems and give a complete hardness picture for P_t-free vertex splitting for all fixed t≥4. The paper's structural lemmas—especially Lemma 10, which equates general and exclusive splitting for P_t-free targets on high-girth graphs—are valuable and, as far as I checked, sound. The reductions are detailed and the variant taxonomy (general/exclusive/shallow) is handled carefully. I specifically examined the reader's concern about Lemma 10 and do not think it lands: the girth argument is valid. However, two proof steps in Sections 7 and 6 need repair before the claims can be accepted as written.

major comments (2)
  1. [Theorem 4, Section 7 (⇒ direction)] The split sequence is not legally specified. The proof first splits x∈S_X and defines N(x_X)=(X∖S_X)∪{v_X:v∈S_X∖{x}}, and then splits y∈S_Y and defines N(y_Y)=(Y∖S_Y)∪{v_Y:v∈S_Y∖{y}}∪{x_Y:...}. At the moment the first y is split, the vertices v_Y do not exist unless v has already been split, so the definition does not give subsets of the current neighborhood. The same forward reference occurs for x_X. This is load-bearing because the construction must be a legitimate sequence of vertex splits. The gap is repairable: split all S_X first, defining N(x_X) with current unsplit vertices v∈S_X∖{x} and later assigning those edges to v_X when v is split; then split each y∈S_Y, defining N(y_Y) with current vertices v∈S_Y∖{y} and the already-existing x_Y vertices, and assign the y_Y-v edges to v_Y when v is split later. The paragraph should be rewritten with this explicit order.
  2. [Theorem 3, Claim 23 (⇒ direction)] The proof of H[R] being P_5-free contains a notational and a logical error. The construction adds edges in G_t[O] exactly for nonedges of G, so H[R] is isomorphic to \overline{G}, not G. The sentence 'Since G is house-free, the graph G contains no induced P_5' is false: P_5 itself is house-free. The correct argument is: choose the Vertex Cover source with girth at least 4, so G is triangle-free; then \overline{G} is P_5-free (an induced P_5 in \overline{G} would be an induced house in G, and a house contains a triangle). Hence H[R] is P_5-free. This step is needed before Claim 22 is applied, so the proof must be corrected.
minor comments (2)
  1. [Claim 22] The proof omits the case where the two pendant paths used by the induced path are attached to the same vertex x∈X. In that case the path has at most a+b+1=t-3<t vertices, so the claim still holds; the case should be stated explicitly.
  2. [Section 8, Theorem 5] The construction from Colored Unit 2-interval Recognition to Unit-Interval-VS is sound, but the forward direction would benefit from an explicit statement that splitting each white vertex according to the two representatives in the split (S,f) is a shallow split, since this is used to obtain the SVS version.

Circularity Check

0 steps flagged

No significant circularity; all hardness results are reductions from independent source problems.

full rationale

This is a hardness-reduction paper, not a fitting or self-derivation. Each main theorem reduces from an independently established NP-hard problem: Theorem 1 from Vertex Cover (via SEPVC and Lemma 13), Theorem 2 from Edge Dominating Set (via DSEPVC and Lemma 20), Theorem 4 from Chain Vertex Deletion (Proposition 24), and Theorem 5 from Colored Unit 2-interval Recognition (Proposition 28). The auxiliary equivalences (Lemmas 10, 12, 16, and 20) relate vertex-splitting variants to edge-partition problems, but in both directions they are proven using the definitions of splitting and the target graph classes; they do not presuppose the hardness of the target problems. No parameter is fitted to any subset of data and then called a prediction: the budgets k are carried through the reductions unchanged or shifted by m-n in closed form. The self-citations in the paper (e.g., reference [33]) are background references and are not load-bearing for the main reductions. The proof-correctness concern about the ordering in the Chordal-VS forward direction is a potential gap in a reduction argument, not a circularity: it does not make the conclusion equivalent to the input by construction. Therefore the paper's derivation chain is self-contained with respect to circularity, and no circular step can be quoted and exhibited.

Axiom & Free-Parameter Ledger

0 free parameters · 6 axioms · 0 invented entities

No free parameters are fitted and no new physical or mathematical entities are postulated. The paper relies on well-established NP-hard source problems, standard graph-theoretic facts, and the ETH assumption.

axioms (6)
  • standard math Proposition 7: Vertex Cover is NP-complete and ETH-hard on subcubic graphs of girth at least g, with every component containing a cycle [27].
    Used as the source problem for the cograph, P_5-free, and P_t-free reductions; accepted from the literature without proof in this paper.
  • standard math Propositions 17 and 18: reductions between Vertex Cover and Edge Dominating Set, and the effect of subdividing edges on Edge Dominating Set [11,12].
    Basis for the P_5-free / double-star edge partition hardness chain in Section 5.
  • standard math Proposition 24: Chain Vertex Deletion is NP-complete and ETH-hard on bipartite graphs [35].
    Source problem for the Chordal Vertex Splitting reduction in Section 7.
  • standard math Propositions 26 and 28: split characterization and restricted NP-hardness of Colored Unit 2-interval Recognition [29].
    Source for the Unit-Interval Vertex Splitting reduction in Section 8; the induced-claw property in Proposition 28 is essential for the argument.
  • domain assumption Exponential Time Hypothesis (ETH).
    All 2^{o(k)} and 2^{o(n)} lower-bound statements are conditional on this unproved complexity-theoretic hypothesis.
  • standard math Standard facts: cographs are exactly P4-free graphs; chordal graphs admit perfect elimination orderings; unit interval graphs are claw-free and closed under adding true twins.
    Invoked throughout Sections 4, 7, and 8 without proof.

pith-pipeline@v1.3.0-alltime-deepseek · 24096 in / 28863 out tokens · 285850 ms · 2026-08-02T04:58:47.421810+00:00 · methodology

0 comments
read the original abstract

Vertex splitting replaces a vertex (v) by two nonadjacent vertices whose neighborhoods together equal (N(v)). A split is \emph{exclusive} if these neighborhoods are disjoint and \emph{shallow} if no newly created vertex is split again. For a graph property (\Pi), \textsc{(\Pi)-Vertex Splitting} asks whether at most (k) splits can transform a graph (G) into one satisfying (\Pi). We continue the systematic study of this operation and settle several open problems. First, we prove that \textsc{Cograph Vertex Splitting} is \textsf{NP}-complete, even on graphs of girth at least 5, resolving a question of Firbas and Sorge (ISAAC 2024). More generally, \textsc{(P_t)-free Vertex Splitting} is \textsf{NP}-complete for every fixed (t\geq 4). We also prove that \textsc{Chordal Vertex Splitting} and \textsc{Unit-Interval Vertex Splitting} are \textsf{NP}-complete, resolving two questions of Abu-Khzam, Chakraborty, Isenmann, and Oijid (IWOCA 2026). Our hardness results extend to the exclusive and shallow variants. Assuming the Exponential Time Hypothesis, none of these problems admits an algorithm running in (2^{o(k)}n^{O(1)}) time; moreover, except for the unit-interval cases, none admits an algorithm running in (2^{o(n)}) time.

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

90 extracted references · 22 canonical work pages

  1. [2]

    Recognizing unit multiple interval graphs is hard , journal =

    Virginia Ard. Recognizing unit multiple interval graphs is hard , journal =. 2025 , url =

    2025

  2. [5]

    1981 , publisher=

    Yannakakis, Mihalis , journal=. 1981 , publisher=

    1981

  3. [7]

    Kumar, Hitendra , school=

  4. [8]

    Gaikwad, Ajinkya and Kumar, Hitendra and Padmapriya, S and Patra, Praneet Kumar and Sanklecha, Harsh and Maity, Soumen , journal=

  5. [9]

    IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) , pages=

    Subexponential parameterized odd cycle transversal on planar graphs , author=. IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) , pages=. 2012 , organization=

    2012

  6. [10]

    Faisal N. Abu. Combinatorial Optimization - 5th International Symposium,. 2018 , doi =

    2018

  7. [11]

    Faisal N. Abu. Computing and Combinatorics - 31st International Computing and Combinatorics Conference,. 2025 , doi =

    2025

  8. [12]

    Faisal N. Abu. 4th International Conference on Artificial Intelligence for Industries,. 2021 , doi =

    2021

  9. [13]

    Russell Impagliazzo and Ramamohan Paturi , title =. J. Comput. Syst. Sci. , volume =. 2001 , doi =

    2001

  10. [14]

    2007 , doi =

    Miroslav Chleb. 2007 , doi =

    2007

  11. [15]

    Approximation hardness of edge dominating set problems , journal =

    Miroslav Chleb. Approximation hardness of edge dominating set problems , journal =. 2006 , doi =

    2006

  12. [16]

    2018 , doi =

    Christian Komusiewicz , title =. 2018 , doi =

    2018

  13. [17]

    Edge domination in trees , author=. Proc. 8th SE Conf. Combin., Graph Theory and Computing, Congr. Numer , volume=

  14. [18]

    Discrete Mathematics & Theoretical Computer Science , volume=

    Demange, Marc and Ekim, T. Discrete Mathematics & Theoretical Computer Science , volume=. 2013 , publisher=

    2013

  15. [19]

    SIAM journal on applied mathematics , volume=

    Edge dominating sets in graphs , author=. SIAM journal on applied mathematics , volume=. 1980 , publisher=

    1980

  16. [20]

    Vazirani and Mihalis Yannakakis , title =

    Naveen Garg and Vijay V. Vazirani and Mihalis Yannakakis , title =. J. Algorithms , volume =. 2004 , url =. doi:10.1016/S0196-6774(03)00111-1 , timestamp =

    work page doi:10.1016/s0196-6774(03)00111-1 2004

  17. [21]

    2602.13981 , archivePrefix=

    Huairui Chu and Yuxi Liu and Daniel Lokshtanov and Junqiang Peng and Kangyi Tian and Mingyu Xiao , year=. 2602.13981 , archivePrefix=

    arXiv

  18. [22]

    Daniel Lokshtanov and M. S. Ramanujan and Saket Saurabh and Meirav Zehavi , editor =. 45th International Colloquium on Automata, Languages, and Programming,. 2018 , doi =

    2018

  19. [23]

    2016 , doi =

    Rajesh Chitnis and Marek Cygan and MohammadTaghi Hajiaghayi and Marcin Pilipczuk and Michal Pilipczuk , title =. 2016 , doi =

    2016

  20. [24]

    Finding small separators in linear time via treewidth reduction , journal =

    D. Finding small separators in linear time via treewidth reduction , journal =. 2013 , doi =

    2013

  21. [25]

    Karl Bringmann and Danny Hermelin and Matthias Mnich and Erik Jan van Leeuwen , title =. J. Comput. Syst. Sci. , volume =. 2016 , doi =

    2016

  22. [26]

    2018 , doi =

    Nicolas Bousquet and Jean Daligault and St. 2018 , doi =

    2018

  23. [27]

    Theory Comput

    Mingyu Xiao , title =. Theory Comput. Syst. , volume =. 2010 , doi =

    2010

  24. [28]

    Sylvain Guillemot , title =. Discret. Optim. , volume =. 2011 , doi =

    2011

  25. [29]

    2013 , doi =

    Marek Cygan and Marcin Pilipczuk and Michal Pilipczuk and Jakub Onufry Wojtaszczyk , title =. 2013 , doi =

    2013

  26. [30]

    Algorithmica , volume =

    Jianer Chen and Yang Liu and Songjian Lu , title =. Algorithmica , volume =. 2009 , doi =

    2009

  27. [31]

    Ford, L. R. and Fulkerson, D. R. , year=. doi:10.4153/CJM-1956-045-5 , journal=

    doi:10.4153/cjm-1956-045-5 1956

  28. [32]

    Node-and edge-deletion

    Yannakakis, Mihalis , booktitle=. Node-and edge-deletion. doi:10.1145/800133.804355 , year=

    arXiv

  29. [34]

    Faisal N. Abu. Combinatorial Algorithms - 37th International Workshop,. 2026 , doi =

    2026

  30. [36]

    10th International Symposium on Parameterized and Exact Computation (IPEC 2015) , pages=

    Parameterized lower bound and improved kernel for diamond-free edge deletion , author=. 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) , pages=. 2015 , doi=

    2015

  31. [38]

    International Symposium on Graph Drawing , pages=

    Vertex splitting and tension-free layout , author=. International Symposium on Graph Drawing , pages=. 1995 , doi =

    1995

  32. [39]

    Faisal N. Abu. CoRR , volume =. 2025 , doi =

    2025

  33. [43]

    Graphs and Applications , editor =

    Brad Jackson and Gerhard Ringel , title =. Graphs and Applications , editor =. 1985 , pages =

    1985

  34. [44]

    Graph Algorithms And Applications 2 , pages=

    Planarizing graphs—a survey and annotated bibliography , author=. Graph Algorithms And Applications 2 , pages=. 2004 , publisher=

    2004

  35. [45]

    International Symposium on Combinatorial Optimization , pages=

    Cluster editing with vertex splitting , author=. International Symposium on Combinatorial Optimization , pages=. 2018 , organization=

    2018

  36. [46]

    Archiv der Mathematik , volume=

    The splitting number of complete bipartite graphs , author=. Archiv der Mathematik , volume=. 1984 , publisher=

    1984

  37. [47]

    2008 , doi =

    Nathalie Henry and Anastasia Bezerianos and Jean. 2008 , doi =

    2008

  38. [48]

    Splitting number is

    Faria, Lu. Splitting number is. Discrete Applied Mathematics , volume=. 2001 , doi=

    2001

  39. [49]

    Parameterized graph separation problems , journal =

    D. Parameterized graph separation problems , journal =. 2006 , doi =

    2006

  40. [50]

    Kleinberg and

    Jon M. Kleinberg and. Algorithm design , publisher =. 2006 , isbn =

    2006

  41. [51]

    Cormen and Charles E

    Thomas H. Cormen and Charles E. Leiserson and Ronald L. Rivest and Clifford Stein , title =. 2009 , url =

    2009

  42. [52]

    Johnson and Christos H

    Elias Dahlhaus and David S. Johnson and Christos H. Papadimitriou and Paul D. Seymour and Mihalis Yannakakis , title =. 1994 , url =. doi:10.1137/S0097539792225297 , timestamp =

    work page doi:10.1137/s0097539792225297 1994

  43. [53]

    19th Scandinavian Symposium and Workshops on Algorithm Theory,

    Matthew Johnson and Barnaby Martin and Sukanya Pandey and Dani. 19th Scandinavian Symposium and Workshops on Algorithm Theory,. 2024 , doi =

    2024

  44. [54]

    Daniel Lokshtanov and N. S. Narayanaswamy and Venkatesh Raman and M. S. Ramanujan and Saket Saurabh , title =. 2014 , url =. doi:10.1145/2566616 , timestamp =

    work page doi:10.1145/2566616 2014

  45. [55]

    Liu and Richard Peng and Maximilian Probst Gutenberg and Sushant Sachdeva , title =

    Li Chen and Rasmus Kyng and Yang P. Liu and Richard Peng and Maximilian Probst Gutenberg and Sushant Sachdeva , title =. J. 2025 , url =. doi:10.1145/3728631 , timestamp =

    doi:10.1145/3728631 2025

  46. [56]

    2017 , isbn =

    Reinhard Diestel , title =. 2017 , isbn =

    2017

  47. [58]

    SIAM Journal on Computing , volume=

    Edge-deletion problems , author=. SIAM Journal on Computing , volume=. doi:10.1137/0210021 , year=

    doi:10.1137/0210021

  48. [59]

    NP-complete problems on a 3-connected cubic planar graph and their applications , author=

  49. [60]

    Reddy and Sartaj Sahni , title =

    Doowon Paik and Sudhakar M. Reddy and Sartaj Sahni , title =. Int. J. Found. Comput. Sci. , volume =. 1998 , url =. doi:10.1142/S0129054198000301 , timestamp =

    work page doi:10.1142/s0129054198000301 1998

  50. [63]

    2023 , doi=

    Establishing hereditary graph properties via vertex splitting , author=. 2023 , doi=

    2023

  51. [64]

    Graph Drawing and Network Visualization - 30th International Symposium,

    Martin N. Graph Drawing and Network Visualization - 30th International Symposium,. 2022 , doi =

    2022

  52. [65]

    Jakob Baumann and Matthias Pfretzschner and Ignaz Rutter , title =. Theor. Comput. Sci. , volume =. 2024 , doi =

    2024

  53. [66]

    35th International Symposium on Algorithms and Computation,

    Alexander Firbas and Manuel Sorge , editor =. 35th International Symposium on Algorithms and Computation,. 2024 , doi =

    2024

  54. [68]

    Faisal N. Abu. Combinatorial Algorithms - 36th International Workshop,. 2025 , doi =

    2025

  55. [69]

    Algorithmica , volume =

    Leizhen Cai and Yufei Cai , title =. Algorithmica , volume =. 2015 , url =. doi:10.1007/S00453-014-9937-X , timestamp =

    work page doi:10.1007/s00453-014-9937-x 2015

  56. [70]

    Abu-Khzam, Emmanuel Arrighi, Matthias Bentert, Pål Grønås Drange, Judith Egan, Serge Gaspers, Alexis Shaw, Peter Shaw, Blair D

    Faisal N. Abu-Khzam, Emmanuel Arrighi, Matthias Bentert, Pål Grønås Drange, Judith Egan, Serge Gaspers, Alexis Shaw, Peter Shaw, Blair D. Sullivan, and Petra Wolf. Cluster Editing with Vertex Splitting . Discrete Applied Mathematics , 371:185--195, 2025. https://doi.org/10.1016/j.dam.2025.04.013 doi:10.1016/j.dam.2025.04.013

    work page doi:10.1016/j.dam.2025.04.013 2025

  57. [71]

    Abu - Khzam, Joseph R

    Faisal N. Abu - Khzam, Joseph R. Barr, Amin Fakhereldine, and Peter Shaw. A Greedy Heuristic for Cluster Editing with Vertex Splitting . In 4th International Conference on Artificial Intelligence for Industries, AI4I 2021, Laguna Hills, CA, USA, September 20-22, 2021 , pages 38--41. IEEE , 2021. https://doi.org/10.1109/AI4I51902.2021.00017 doi:10.1109/AI4...

    arXiv 2021

  58. [72]

    Abu - Khzam, Dipayan Chakraborty, Lucas Isenmann, and Nacim Oijid

    Faisal N. Abu - Khzam, Dipayan Chakraborty, Lucas Isenmann, and Nacim Oijid. On the Complexity of Vertex-Splitting into an Interval Graph . In Florent Foucaud and Aline Parreau, editors, Combinatorial Algorithms - 37th International Workshop, IWOCA 2026, Clermont-Ferrand, France, June 8-11, 2026, Proceedings , volume 16587 of Lecture Notes in Computer Sci...

    work page doi:10.1007/978-3-032-27732-9 2026

  59. [73]

    Abu - Khzam, Tom Davot, Lucas Isenmann, and Sergio Thoumi

    Faisal N. Abu - Khzam, Tom Davot, Lucas Isenmann, and Sergio Thoumi. On the Complexity of 2-Club Cluster Editing with Vertex Splitting . In Fedor V. Fomin and Mingyu Xiao, editors, Computing and Combinatorics - 31st International Computing and Combinatorics Conference, COCOON 2025, Chengdu, China, August 15-17, 2025, Proceedings, Part II , volume 15984 of...

    work page doi:10.1007/978-981-95-0218-9 2025

  60. [74]

    Abu - Khzam, Judith Egan, Serge Gaspers, Alexis Shaw, and Peter Shaw

    Faisal N. Abu - Khzam, Judith Egan, Serge Gaspers, Alexis Shaw, and Peter Shaw. Cluster Editing with Vertex Splitting . In Jon Lee, Giovanni Rinaldi, and Ali Ridha Mahjoub, editors, Combinatorial Optimization - 5th International Symposium, ISCO 2018, Marrakesh, Morocco, April 11-13, 2018, Revised Selected Papers , volume 10856 of Lecture Notes in Computer...

    work page doi:10.1007/978-3-319-96151-4 2018

  61. [75]

    Abu - Khzam, Lucas Isenmann, and Zeina Merchad

    Faisal N. Abu - Khzam, Lucas Isenmann, and Zeina Merchad. Bicluster Editing with Overlaps: A Vertex Splitting Approach . In Henning Fernau and Binhai Zhu, editors, Combinatorial Algorithms - 36th International Workshop, IWOCA 2025, Bozeman, MT, USA, July 21-24, 2025, Proceedings , volume 15885 of Lecture Notes in Computer Science , pages 146--159. Springe...

    work page doi:10.1007/978-3-031-98740-3 2025

  62. [76]

    Abu - Khzam and Sergio Thoumi

    Faisal N. Abu - Khzam and Sergio Thoumi. On the Complexity of Claw-Free Vertex Splitting . CoRR , abs/2506.06044, 2025. https://doi.org/10.48550/ARXIV.2506.06044 doi:10.48550/ARXIV.2506.06044

    work page doi:10.48550/arxiv.2506.06044 2025

  63. [77]

    Kobourov, and Myroslav Kryven

    Abu Reyan Ahmed, Stephen G. Kobourov, and Myroslav Kryven. An FPT Algorithm for Bipartite Vertex Splitting . In Patrizio Angelini and Reinhard von Hanxleden, editors, Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Tokyo, Japan, September 13-16, 2022, Revised Selected Papers , volume 13764 of Lecture Notes in Computer Scie...

    doi:10.1007/978-3-031-22203-0 2022

  64. [78]

    Parameterized Complexity of Vertex Splitting to Pathwidth at Most 1

    Jakob Baumann, Matthias Pfretzschner, and Ignaz Rutter. Parameterized Complexity of Vertex Splitting to Pathwidth at Most 1 . In International Workshop on Graph-Theoretic Concepts in Computer Science , pages 30--43. Springer, 2023. https://doi.org/10.1007/978-3-031-43380-1\_3 doi:10.1007/978-3-031-43380-1\_3

    doi:10.1007/978-3-031-43380-1 2023

  65. [79]

    Parameterized complexity of vertex splitting to pathwidth at most 1

    Jakob Baumann, Matthias Pfretzschner, and Ignaz Rutter. Parameterized complexity of vertex splitting to pathwidth at most 1. Theor. Comput. Sci. , 1021:114928, 2024. https://doi.org/10.1016/J.TCS.2024.114928 doi:10.1016/J.TCS.2024.114928

    arXiv 2024

  66. [80]

    Approximation hardness of edge dominating set problems

    Miroslav Chleb \' k and Janka Chleb \' kov \' a . Approximation hardness of edge dominating set problems. J. Comb. Optim. , 11(3):279--290, 2006. https://doi.org/10.1007/S10878-006-7908-0 doi:10.1007/S10878-006-7908-0

    work page doi:10.1007/s10878-006-7908-0 2006

  67. [81]

    The Complexity of Combinatorial Optimization Problems on d-Dimensional Boxes

    Miroslav Chleb \' k and Janka Chleb \' kov \' a . The Complexity of Combinatorial Optimization Problems on d-Dimensional Boxes . SIAM J. Discret. Math. , 21(1):158--169, 2007. https://doi.org/10.1137/050629276 doi:10.1137/050629276

    work page doi:10.1137/050629276 2007

  68. [82]

    Fomin, Lukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh

    Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms . Springer, 2015. https://doi.org/10.1007/978-3-319-21275-3 doi:10.1007/978-3-319-21275-3

    doi:10.1007/978-3-319-21275-3 2015

  69. [83]

    Graph Theory, 5th Edition , volume 173 of Graduate texts in mathematics

    Reinhard Diestel. Graph Theory, 5th Edition , volume 173 of Graduate texts in mathematics . Springer, 2017. https://doi.org/10.1007/978-3-662-53622-3 doi:10.1007/978-3-662-53622-3

    doi:10.1007/978-3-662-53622-3 2017

  70. [84]

    Vertex splitting and tension-free layout

    Peter Eades and CFX de Mendon c a N. Vertex splitting and tension-free layout. In International Symposium on Graph Drawing , pages 202--211. Springer, 1995. https://doi.org/10.1007/BFB0021804 doi:10.1007/BFB0021804

    work page doi:10.1007/bfb0021804 1995

  71. [85]

    Splitting number is NP -complete

    Lu \'e rbio Faria, Celina MH de Figueiredo, and CFX de Mendon c a N. Splitting number is NP -complete. Discrete Applied Mathematics , 108(1-2):65--83, 2001. https://doi.org/10.1016/S0166-218X(00)00220-1 doi:10.1016/S0166-218X(00)00220-1

    work page doi:10.1016/s0166-218x(00)00220-1 2001

  72. [86]

    Fellows, Jan Kratochv \' l, Matthias Middendorf, and Frank Pfeiffer

    Michael R. Fellows, Jan Kratochv \' l, Matthias Middendorf, and Frank Pfeiffer. The Complexity of Induced Minors and Related Problems . Algorithmica , 13(3):266--282, 1995. https://doi.org/10.1007/BF01190507 doi:10.1007/BF01190507

    doi:10.1007/bf01190507 1995

  73. [87]

    Establishing hereditary graph properties via vertex splitting

    Alexander Firbas. Establishing hereditary graph properties via vertex splitting . PhD thesis, Technische Universit \"a t Wien, 2023. https://doi.org/10.34726/hss.2023.103864 doi:10.34726/hss.2023.103864

    arXiv 2023

  74. [88]

    On the Complexity of Establishing Hereditary Graph Properties via Vertex Splitting

    Alexander Firbas and Manuel Sorge. On the Complexity of Establishing Hereditary Graph Properties via Vertex Splitting . In Juli \' a n Mestre and Anthony Wirth, editors, 35th International Symposium on Algorithms and Computation, ISAAC 2024, Sydney, Australia, December 8-11, 2024 , volume 322 of LIPIcs , pages 30:1--30:15. Schloss Dagstuhl - Leibniz-Zentr...

    work page doi:10.4230/lipics.isaac.2024.30 2024

  75. [89]

    Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms

    Ajinkya Gaikwad, Hitendra Kumar, S Padmapriya, Praneet Kumar Patra, Harsh Sanklecha, and Soumen Maity. Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms . arXiv preprint arXiv:2510.26938 , 2025

    arXiv 2025

  76. [90]

    The splitting number of the complete graph

    Nora Hartsfield, Brad Jackson, and Gerhard Ringel. The splitting number of the complete graph. Graphs and Combinatorics , 1(1):311--329, 1985. https://doi.org/10.1007/BF02582960 doi:10.1007/BF02582960

    doi:10.1007/bf02582960 1985

  77. [91]

    Improving the Readability of Clustered Social Networks using Node Duplication

    Nathalie Henry, Anastasia Bezerianos, and Jean - Daniel Fekete. Improving the Readability of Clustered Social Networks using Node Duplication . IEEE Trans. Vis. Comput. Graph. , 14(6):1317--1324, 2008. https://doi.org/10.1109/TVCG.2008.141 doi:10.1109/TVCG.2008.141

    work page doi:10.1109/tvcg.2008.141 2008

  78. [92]

    Vertex-splitting and chromatic index critical graphs

    Anthony JW Hilton and C Zhao. Vertex-splitting and chromatic index critical graphs. Discrete applied mathematics , 76(1-3):205--211, 1997. https://doi.org/10.1016/S0166-218X(96)00125-4 doi:10.1016/S0166-218X(96)00125-4

    work page doi:10.1016/s0166-218x(96)00125-4 1997

  79. [93]

    On the Complexity of k-SAT

    Russell Impagliazzo and Ramamohan Paturi. On the Complexity of k-SAT . J. Comput. Syst. Sci. , 62(2):367--375, 2001. https://doi.org/10.1006/JCSS.2000.1727 doi:10.1006/JCSS.2000.1727

    arXiv 2001

  80. [94]

    The splitting number of complete bipartite graphs

    Brad Jackson and Gerhard Ringel. The splitting number of complete bipartite graphs. Archiv der Mathematik , 42(2):178--184, 1984

    1984

Showing first 80 references.