On the computational complexity of the bipartizing matching problem
DOI10.1007/s10479-021-03966-9zbMath1497.05093arXiv1710.07741OpenAlexW3130437458MaRDI QIDQ2675722
Dieter Rautenbach, Uéverton S. Souza, Carlos Vinícius G. C. Lima, Jayme Luiz Szwarcfiter
Publication date: 26 September 2022
Published in: Annals of Operations Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1710.07741
planar graphsNP-completenessparameterized complexitygraph modification problemsdefective coloringedge bipartization
Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On bipartization of cubic graphs by removal of an independent set
- A new characterization of \(P_k\)-free graphs
- Fundamentals of parameterized complexity
- On 1-improper 2-coloring of sparse graphs
- On the bipartite vertex frustration of graphs
- Partitions of graphs into cographs
- Monadic second-order evaluations on tree-decomposable graphs
- New graph classes of bounded clique-width
- Hardness of edge-modification problems
- Some simplified NP-complete graph problems
- All structured programs have small tree width and good register allocation
- A partial k-arboretum of graphs with bounded treewidth
- Algorithmic meta-theorems for restrictions of treewidth
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
- Linear time solvable optimization problems on graphs of bounded clique-width
- Editing graphs to satisfy diversity requirements
- Degree-constrained 2-partitions of graphs
- Deadlock resolution in wait-for graphs by vertex/arc deletion
- Clique-width for 4-vertex forbidden subgraphs
- NP-completeness results for edge modification problems
- Decycling with a matching
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Vertex Partitions of Graphs into Cographs and Stars
- Vertex-Coloring with Defects
- Defective coloring revisited
- Minimum-weight triangulation is NP-hard
- Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
- Graph minors. II. Algorithmic aspects of tree-width
- Graph Bipartization and via minimization
- Edge-Deletion Problems
- Efficient Planarity Testing
- Handbook of Graph Grammars and Computing by Graph Transformation
- Splitting Planar Graphs of Girth 6 into Two Linear Forests with Short Paths
- Exploring the Kernelization Borders for Hitting Cycles
- Independent Feedback Vertex Set for P_5-free Graphs
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
- The complexity of satisfiability problems
- Node-and edge-deletion NP-complete problems
- Parameterized Algorithms
- Complexity classification of some edge modification problems
