Approximation hardness of domination problems on generalized convex graphs

DOI10.1016/j.tcs.2024.115035MaRDI QIDQ6664063

Po-Yuan Wang, Toshimitsu Masuzawa, Taisuke Izumi, Naoki Kitamura

Publication date: 16 January 2025

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

approximation hardnessdomination problemgeneralized convex graphtree-convex bipartite graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
• Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
• Graph classes with structured neighborhoods and algorithmic applications
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Feedback vertex sets on restricted bipartite graphs
• Approximating the minimum maximal independence number
• On approximating the minimum independent dominating set
• Domination, independent domination, and duality in strongly chordal graphs
• Domination in convex and chordal bipartite graphs
• Approximation hardness of dominating set problems in bounded degree graphs
• Labelling algorithms for paired-domination problems in block and interval graphs
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
• Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits
• Preface: 13th Cologne-Twente workshop on graphs and combinatorial optimization (CTW 2015)
• Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
• HAMILTONian circuits in chordal bipartite graphs
• Tractable connected domination for restricted bipartite graphs
• A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph
• Independent Domination on Tree Convex Bipartite Graphs
• A threshold of ln n for approximating set cover
• Feedback Vertex Sets on Tree Convex Bipartite Graphs
• Complexity of Finding Embeddings in a k-Tree
• Node-Deletion Problems on Bipartite Graphs
• Treewidth of Chordal Bipartite Graphs
• Reducibility among Combinatorial Problems
• More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints
• Analytical approach to parallel repetition
• Independent Domination: Reductions from Circular- and Triad-Convex Bipartite Graphs to Convex Bipartite Graphs
• Maximum matching in a convex bipartite graph
• Solving problems on generalized convex graphs via mim-width

This page was built for publication: Approximation hardness of domination problems on generalized convex graphs