On the computational complexity of the bipartizing matching problem

DOI10.1007/S10479-021-03966-9MaRDI QIDQ2675722zbMATH OpenOpenAlexFDO

Authors Dieter Rautenbach, Uéverton S. Souza, Carlos Vinícius G. C. Lima, Jayme L. 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

zbMATH Keywords

defective coloringedge bipartizationgraph modification problemsNP-completenessparameterized complexityplanar graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39)

Abstract: We study the problem of determining whether a given graph~$G=(V,E)$ admits a matching~$M$ whose removal destroys all odd cycles of~$G$ (or equivalently whether~$G-M$ is bipartite). This problem is equivalent to determine whether~$G$ admits a~$(2,1)$-coloring, which is a~$2$-coloring of~$V(G)$ such that each color class induces a graph of maximum degree at most~$1$. We determine a dichotomy related to the~{sf NP}-completeness of this problem, where we show that it is~{sf NP}-complete even for $3$-colorable planar graphs of maximum degree~$4$, while it is known that the problem can be solved in polynomial time for graphs of maximum degree at most~$3$. In addition we present polynomial-time algorithms for some graph classes, including graphs in which every odd cycle is a triangle, graphs of small dominating sets, and~$P_5$-free graphs. Additionally, we show that the problem is fixed parameter tractable when parameterized by the clique-width, which implies polynomial-time solution for many interesting graph classes, such as distance-hereditary, outerplanar, and chordal graphs. Finally, an~$Oleft(2^{Oleft(vc(G)ight)}cdotnight)$-time algorithm and a kernel of at most~$2cdotnd(G)$ vertices are presented, where~$vc(G)$ and~$nd(G)$ are the vertex cover number and the neighborhood diversity of~$G$, respectively.

Recommendations

• Solving matching problems efficiently in bipartite graphs
• An efficient algorithm for the bipartite matching problem
• Improved complexity bound for the maximum cardinality bottleneck bipartite matching problem
• scientific article; zbMATH DE number 1305475
• On the Bipartite Unique Perfect Matching Problem
• A polynomial-time approximation algorithm for the number of k-matchings in bipartite graphs
• On maximum bipartite matching with separation
• On the Robust Communication Complexity of Bipartite Matching
• Parallel algorithms for bipartite matching problems on distributed memory computers

Cites work

• A new characterization of P_k-free graphs
• A partial k-arboretum of graphs with bounded treewidth
• Algorithmic meta-theorems for restrictions of treewidth
• All structured programs have small tree width and good register allocation
• Clique-width for 4-vertex forbidden subgraphs
• Complexity classification of some edge modification problems
• Deadlock resolution in wait-for graphs by vertex/arc deletion
• Decycling a graph by the removal of a matching: new algorithmic and structural aspects in some classes of graphs
• Decycling with a matching
• Defective coloring revisited
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Degree-constrained 2-partitions of graphs
• Edge-Deletion Problems
• Editing graphs to satisfy diversity requirements
• Efficient Planarity Testing
• Exploring the kernelization borders for hitting cycles
• Fundamentals of parameterized complexity
• Graph Bipartization and via minimization
• Graph minors. II. Algorithmic aspects of tree-width
• Graph structure and monadic second-order logic. A language-theoretic approach
• Graph theory
• Handbook of Graph Grammars and Computing by Graph Transformation
• Hardness of edge-modification problems
• scientific article; zbMATH DE number 3979083 (Why is no real title available?)
• scientific article; zbMATH DE number 4008419 (Why is no real title available?)
• scientific article; zbMATH DE number 1250667 (Why is no real title available?)
• scientific article; zbMATH DE number 5279372 (Why is no real title available?)
• scientific article; zbMATH DE number 3243267 (Why is no real title available?)
• Independent Feedback Vertex Set for P₅-free Graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Minimum-weight triangulation is NP-hard
• Monadic second-order evaluations on tree-decomposable graphs
• New graph classes of bounded clique-width
• Node-and edge-deletion NP-complete problems
• NP-completeness results for edge modification problems
• On 1-improper 2-coloring of sparse graphs
• On bipartization of cubic graphs by removal of an independent set
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• On the bipartite vertex frustration of graphs
• On the clique-width of some perfect graph classes
• Parameterized algorithms
• Partitions of graphs into cographs
• Some simplified NP-complete graph problems
• Splitting planar graphs of girth 6 into two linear forests with short paths
• The complexity of satisfiability problems
• 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

Cited in

(11)

• Bipartizing with a matching
• Recognizing Graphs Close to Bipartite Graphs
• scientific article; zbMATH DE number 7053293 (Why is no real title available?)
• Computational complexity of simultaneous elementary matching problems
• Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration
• On maximum bipartite matching with separation
• Near-bipartiteness on graphs having small dominating sets
• Perfect matching cuts partitioning a graph into complementary subgraphs
• The complexity of (P₃,H)-Arrowing and beyond
• Graph modification of bounded size to minor-closed classes as fast as vertex deletion
• An 0(n log n) algorithm for the convex bipartite matching problem

This page was built for publication: On the computational complexity of the bipartizing matching problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2675722)