<div class="csl-bib-body">
<div class="csl-entry">Firbas, A., & Sorge, M. (2024). On the Complexity of Establishing Hereditary Graph Properties via Vertex Splitting. In <i>35th International Symposium on Algorithms and Computation (ISAAC 2024)</i> (pp. 1–15). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ISAAC.2024.30</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/210858
-
dc.description.abstract
Vertex splitting is a graph operation that replaces a vertex v with two nonadjacent new vertices u, w and makes each neighbor of v adjacent with one or both of u or w. Vertex splitting has been used in contexts from circuit design to statistical analysis. In this work, we generalize from specific vertex-splitting problems and systematically explore the computational complexity of achieving a given graph property Π by a limited number of vertex splits, formalized as the problem Π Vertex Splitting (Π-VS). We focus on hereditary graph properties and contribute four groups of results: First, we classify the classical complexity of Π-VS for graph properties characterized by forbidden subgraphs of order at most 3. Second, we provide a framework that allows one to show NP-completeness whenever one can construct a combination of a forbidden subgraph and prescribed vertex splits that satisfy certain conditions. Using this framework we show NP-completeness when Π is characterized by sufficiently well-connected forbidden subgraphs. In particular, we show that F-Free-VS is NP-complete for each biconnected graph F. Third, we study infinite families of forbidden subgraphs, obtaining NP-completeness for Bipartite-VS and Perfect-VS, contrasting the known result that Π-VS is in P if Π is the set of all cycles. Finally, we contribute to the study of the parameterized complexity of Π-VS with respect to the number of allowed splits. We show para-NP-hardness for K₃-Free-VS and derive an XP-algorithm when each vertex is only allowed to be split at most once, showing that the ability to split a vertex more than once is a key driver of the problems' complexity.
en
dc.description.sponsorship
WWTF Wiener Wissenschafts-, Forschu und Technologiefonds
-
dc.language.iso
en
-
dc.relation.ispartofseries
Leibniz International Proceedings in Informatics (LIPIcs)
-
dc.subject
NP-completenes
en
dc.subject
polynomial-time solvability
en
dc.subject
graph theory
en
dc.subject
graph transformation
en
dc.subject
graph modification
en
dc.title
On the Complexity of Establishing Hereditary Graph Properties via Vertex Splitting
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.relation.publication
35th International Symposium on Algorithms and Computation (ISAAC 2024)
-
dc.relation.isbn
978-3-95977-354-6
-
dc.description.startpage
1
-
dc.description.endpage
15
-
dc.relation.grantno
ICT22-029
-
dc.type.category
Full-Paper Contribution
-
tuw.booktitle
35th International Symposium on Algorithms and Computation (ISAAC 2024)
-
tuw.container.volume
322
-
tuw.peerreviewed
true
-
tuw.relation.publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
-
tuw.book.chapter
30
-
tuw.project.title
Parameterized Graph Drawing
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-01 - Forschungsbereich Algorithms and Complexity
-
tuw.publisher.doi
10.4230/LIPIcs.ISAAC.2024.30
-
dc.description.numberOfPages
15
-
tuw.event.name
ISAAC 2024
en
tuw.event.startdate
08-12-2024
-
tuw.event.enddate
11-12-2024
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Sydney
-
tuw.event.country
AU
-
tuw.event.presenter
Firbas, Alexander
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
item.languageiso639-1
en
-
item.openairetype
conference paper
-
item.grantfulltext
none
-
item.fulltext
no Fulltext
-
item.cerifentitytype
Publications
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.parentorg
E192 - Institut für Logic and Computation
-
crisitem.author.parentorg
E192 - Institut für Logic and Computation
-
crisitem.project.funder
WWTF Wiener Wissenschafts-, Forschu und Technologiefonds