Umeå University's logo

umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On the complexity of vertex-splitting into an interval graph
Lebanese American University, Beirut, Lebanon.
LIS, Centrale Méditerranée, Aix-Marseille Université, Marseille, France.
Université de Strasbourg, Strasbourg, France.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2026 (English)In: Combinatorial Algorithms - 37th International Workshop, IWOCA 2026, Proceedings / [ed] Foucaud F.; Parreau A., Cham: Springer, 2026, p. 1-15Conference paper, Published paper (Refereed)
Abstract [en]

Vertex splitting is a graph modification operation in which a vertex is replaced by multiple vertices such that the union of their neighborhoods equals the neighborhood of the original vertex. We introduce and study vertex splitting as a graph modification operation for transforming graphs into interval graphs. Given a graph G and an integer k, we consider the problem of deciding whether G can be transformed into an interval graph using at most k vertex splits. We prove that this problem is NP-hard, even when the input is restricted to subcubic planar bipartite graphs. We further observe that vertex splitting differs fundamentally from vertex and edge deletions as graph modification operations when the objective is to obtain a chordal graph, even for graphs with maximum independent set size at most two. On the positive side, we give a polynomial-time algorithm for transforming, via a minimum number of vertex splits, a given graph into a disjoint union of paths, and that splitting triangle free graphs into unit interval graphs is also solvable in polynomial time.

Place, publisher, year, edition, pages
Cham: Springer, 2026. p. 1-15
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 16587
National Category
Computer Sciences Discrete Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-255471DOI: 10.1007/978-3-032-27732-9_1Scopus ID: 2-s2.0-105041614770ISBN: 9783032277312 (print)ISBN: 9783032277329 (electronic)OAI: oai:DiVA.org:umu-255471DiVA, id: diva2:2078453
Conference
37th International Workshop on Combinatorial Algorithms, IWOCA 2026, June 8-11, 2026, Clermont-Ferrand, France
Available from: 2026-06-24 Created: 2026-06-24 Last updated: 2026-06-24Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Oijid, Nacim

Search in DiVA

By author/editor
Oijid, Nacim
By organisation
Department of Mathematics and Mathematical Statistics
Computer SciencesDiscrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 15 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf