Buchumschlag

On the Complexity of Establishing Hereditary Graph Properties via Vertex Splitting

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Firbas, Alexander, Sorge, Manuel
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

The Complexity of Cluster Vertex Splitting and Company
von: Firbas, Alexander, et al.
Veröffentlicht: (2023)

On the Complexity of 2-club Cluster Editing with Vertex Splitting
von: Abu-Khzam, Faisal N., et al.
Veröffentlicht: (2024)

Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms
von: Gaikwad, Ajinkya, et al.
Veröffentlicht: (2025)

List Locally Surjective Homomorphisms in Hereditary Graph Classes
von: Dvořák, Pavel, et al.
Veröffentlicht: (2022)

A Complexity Analysis of the c-Closed Vertex Deletion Problem
von: Lehner, Lisa, et al.
Veröffentlicht: (2025)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
von: Herrmann, Anton, et al.
Veröffentlicht: (2025)

Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number
von: Tale, Prafullkumar
Veröffentlicht: (2025)

Parameterized Complexity of Finding a Maximum Common Vertex Subgraph Without Isolated Vertices
von: Dey, Palash, et al.
Veröffentlicht: (2026)

Exact and Approximate Algorithms for Polytree Learning
von: Harviainen, Juha, et al.
Veröffentlicht: (2026)

Parameterized Vertex Integrity Revisited
von: Hanaka, Tesshu, et al.
Veröffentlicht: (2024)

Parameterized Capacitated Vertex Cover Revisited
von: Lampis, Michael, et al.
Veröffentlicht: (2026)

Bandwidth Parameterized by Cluster Vertex Deletion Number
von: Gima, Tatsuya, et al.
Veröffentlicht: (2023)

Parameterized Max Min Feedback Vertex Set
von: Lampis, Michael, et al.
Veröffentlicht: (2023)

Exact Algorithms for Distance to Unique Vertex Cover
von: Fioravantes, Foivos, et al.
Veröffentlicht: (2025)

Computational Complexity in Property Testing
von: Pinto Jr., Renato Ferreira, et al.
Veröffentlicht: (2025)

Knapsack with Vertex Cover, Set Cover, and Hitting Set
von: Dey, Palash, et al.
Veröffentlicht: (2024)

The Parameterized Complexity of Vertex-Coloring Edge-Weighting
von: Aute, Shubhada, et al.
Veröffentlicht: (2026)

A Faster Randomized Algorithm for Vertex Cover: An Automated Approach
von: Clinch, Katie, et al.
Veröffentlicht: (2025)

Semi-Streaming Algorithms for Graph Property Certification
von: Das, Avinandan, et al.
Veröffentlicht: (2025)

Streaming Complexity Separations for Dense and Sparse Graphs
von: Liu, Yang P., et al.
Veröffentlicht: (2026)

On the Complexity of Fundamental Problems for DAG-Compressed Graphs
von: Chudigiewitsch, Florian, et al.
Veröffentlicht: (2026)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
von: Döring, Simon, et al.
Veröffentlicht: (2024)

Bounded Independence Edge Sampling for Combinatorial Graph Properties
von: Putterman, Aaron, et al.
Veröffentlicht: (2026)

The Query Complexity of Local Search in Rounds on General Graphs
von: Brânzei, Simina, et al.
Veröffentlicht: (2026)

Self-referential instances of the dominating set problem are irreducible
von: Zhou, Guangyan
Veröffentlicht: (2026)

Novel Complexity Results for Temporal Separators with Deadlines
von: Dondi, Riccardo, et al.
Veröffentlicht: (2025)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
von: Focke, Jacob, et al.
Veröffentlicht: (2023)

FPT Approximation using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set
von: Chu, Huairui, et al.
Veröffentlicht: (2023)

The Parameterized Landscape of Labeled Graph Contractions
von: Lafond, Manuel, et al.
Veröffentlicht: (2025)

Asymmetric Number Partitioning with Splitting and Interval Targets
von: Bismuth, Samuel, et al.
Veröffentlicht: (2022)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
von: Greilhuber, Jakob, et al.
Veröffentlicht: (2025)

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
von: Focke, Jacob, et al.
Veröffentlicht: (2022)

Computing Subset Vertex Covers in $H$-Free Graphs
von: Brettell, Nick, et al.
Veröffentlicht: (2023)

Complexity of the (Connected) Cluster Vertex Deletion problem on $H$-free graphs
von: Le, Hoang-Oanh, et al.
Veröffentlicht: (2024)

Complexity of Paired Domination Problems on Circle and $k$-Polygon Graphs
von: Mu, Ta-Yu, et al.
Veröffentlicht: (2024)

The Trichotomy of Regular Property Testing
von: Bathie, Gabriel, et al.
Veröffentlicht: (2025)

Testing Properties of Edge Distributions
von: Fei, Yumou
Veröffentlicht: (2026)

Parameterized Complexity of Vehicle Routing
von: Döring, Michelle, et al.
Veröffentlicht: (2025)

The Complexity of Finding and Counting Subtournaments
von: Döring, Simon, et al.
Veröffentlicht: (2025)