TY - JOUR
T1 - Additive stabilizers for unstable graphs
AU - Chandrasekaran, Karthekeyan
AU - Gottschalk, Corinna
AU - Könemann, Jochen
AU - Peis, Britta
AU - Schmand, Daniel
AU - Wierz, Andreas
N1 - Publisher Copyright:
© 2018 Elsevier B.V.
Copyright:
Copyright 2019 Elsevier B.V., All rights reserved.
PY - 2019/2
Y1 - 2019/2
N2 - A weighted graph is called stable if the maximum weight of an integral matching equals the cost of a minimum-weight fractional vertex cover. We address the following question: how can we modify a given unstable graph in the least intrusive manner in order to achieve stability? Previous works have addressed stabilization through addition or deletion of the smallest possible number of edges/vertices. In this work we investigate the following more fine-grained additive stabilization strategy: given a graph G=(V,E) with unit edge weights; find non-negative c∈R E with minimum ∑ e c e such that adding c e to the unit edge weight of each e∈E yields a stable graph. We provide the first super-constant hardness of approximation results for any graph stabilization problem: (i) unless the current best-known algorithm for the densest- k-subgraph problem can be improved, there is no o(|V| 1∕24 )-approximation for additive stabilizers; (ii) the additive stabilizer problem has no o(log|V|) approximation unless P=NP. On the algorithmic side, we present (iii) a polynomial time algorithm with approximation factor at most |V| for a super-class of the instances generated in our hardness proofs, (iv) an algorithm to solve min additive stabilizer in factor-critical graphs exactly in polynomial time, and (v) an algorithm to solve min additive stabilizer in arbitrary graphs exactly in time exponential in the size of the Tutte set. Our main tools are the Gallai–Edmonds decomposition and structural results for the problem that reduce the continuous decision domain to a discrete decision domain.
AB - A weighted graph is called stable if the maximum weight of an integral matching equals the cost of a minimum-weight fractional vertex cover. We address the following question: how can we modify a given unstable graph in the least intrusive manner in order to achieve stability? Previous works have addressed stabilization through addition or deletion of the smallest possible number of edges/vertices. In this work we investigate the following more fine-grained additive stabilization strategy: given a graph G=(V,E) with unit edge weights; find non-negative c∈R E with minimum ∑ e c e such that adding c e to the unit edge weight of each e∈E yields a stable graph. We provide the first super-constant hardness of approximation results for any graph stabilization problem: (i) unless the current best-known algorithm for the densest- k-subgraph problem can be improved, there is no o(|V| 1∕24 )-approximation for additive stabilizers; (ii) the additive stabilizer problem has no o(log|V|) approximation unless P=NP. On the algorithmic side, we present (iii) a polynomial time algorithm with approximation factor at most |V| for a super-class of the instances generated in our hardness proofs, (iv) an algorithm to solve min additive stabilizer in factor-critical graphs exactly in polynomial time, and (v) an algorithm to solve min additive stabilizer in arbitrary graphs exactly in time exponential in the size of the Tutte set. Our main tools are the Gallai–Edmonds decomposition and structural results for the problem that reduce the continuous decision domain to a discrete decision domain.
KW - Approximation algorithm
KW - Gallai–Edmonds decomposition
KW - Graph stabilization
KW - Hardness
KW - Matching
KW - Vertex cover
UR - http://www.scopus.com/inward/record.url?scp=85052760260&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85052760260&partnerID=8YFLogxK
U2 - 10.1016/j.disopt.2018.08.003
DO - 10.1016/j.disopt.2018.08.003
M3 - Article
AN - SCOPUS:85052760260
VL - 31
SP - 56
EP - 78
JO - Discrete Optimization
JF - Discrete Optimization
SN - 1572-5286
ER -