On the complexity of making a distinguished vertex minimum or maximum degree by vertex deletion

DOI10.1016/J.JDA.2015.03.002MaRDI QIDQ491619zbMATH OpenOpenAlexFDO

Authors Sounaka Mishra, Ashwin Pananjady, N. Safina Devi

Publication date 18 August 2015

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.3779

zbMATH Keywords

approximation algorithmhardness of approximationnode deletion problems

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Abstract: In this paper, we investigate the approximability of two node deletion problems. Given a vertex weighted graph $G=(V,E)$ and a specified, or "distinguished" vertex $pinV$, MDD(min) is the problem of finding a minimum weight vertex set $SsubseteqVsetminusp$ such that $p$ becomes the minimum degree vertex in $G[VsetminusS]$; and MDD(max) is the problem of finding a minimum weight vertex set $SsubseteqVsetminusp$ such that $p$ becomes the maximum degree vertex in $G[VsetminusS]$. These are known $NP$-complete problems and have been studied from the parameterized complexity point of view in previous work. Here, we prove that for any $epsilon>0$, both the problems cannot be approximated within a factor $(1-epsilon)logn$, unless $NPsubseteqDTIME(n^{loglogn})$. We also show that for any $epsilon>0$, MDD(min) cannot be approximated within a factor $(1-epsilon)logn$ on bipartite graphs, unless $NPsubseteqDTIME(n^{loglogn})$, and that for any $epsilon>0$, MDD(max) cannot be approximated within a factor $(1/2-epsilon)logn$ on bipartite graphs, unless $NPsubseteqDTIME(n^{loglogn})$. We give an $O(logn)$ factor approximation algorithm for MDD(max) on general graphs, provided the degree of $p$ is $O(logn)$. We then show that if the degree of $p$ is $n-O(logn)$, a similar result holds for MDD(min). We prove that MDD(max) is $APX$-complete on 3-regular unweighted graphs and provide an approximation algorithm with ratio $1.583$ when $G$ is a 3-regular unweighted graph. In addition, we show that MDD(min) can be solved in polynomial time when $G$ is a regular graph of constant degree.

Recommendations

• Approximating bounded degree deletion via matroid matching
• Approximating partially bounded degree deletion on directed graphs
• Approximating partially bounded degree deletion on directed graphs
• Degree-Constrained Subgraph Problems: Hardness and Approximation Results
• On the approximability of some degree-constrained subgraph problems

Cites work

• A new approach for approximating node deletion problems
• A threshold of ln n for approximating set cover
• A unified approximation algorithm for node-deletion problems
• Approximating k-set cover and complementary graph coloring
• On making a distinguished vertex minimum degree by vertex deletion
• Optimization, approximation, and complexity classes
• Parameterized complexity of candidate control in elections and related digraph problems
• Strong lower bounds on the approximability of some NPO PB-complete maximization problems
• The vertex cover \(P_3\) problem in cubic graphs

Cited in

(8)

• Approximating partially bounded degree deletion on directed graphs
• On the complexity of singly connected vertex deletion
• Decreasing the maximum average degree by deleting an independent set or a \(d\)-degenerate subgraph
• A Note on the Minimum H-Subgraph Edge Deletion
• On making a distinguished vertex minimum degree by vertex deletion
• Minimum degree up to local complementation: bounds, parameterized complexity, and exact algorithms
• Approximating partially bounded degree deletion on directed graphs
• On making a distinguished vertex of minimum degree by vertex deletion

This page was built for publication: On the complexity of making a distinguished vertex minimum or maximum degree by vertex deletion

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