Document Open Access Logo

Bilu-Linial Stability, Certified Algorithms and the Independent Set Problem

Authors Haris Angelidakis, Pranjal Awasthi, Avrim Blum, Vaggos Chatziafratis, Chen Dan

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.7.pdf
  • Filesize: 0.55 MB
  • 16 pages

Document Identifiers

Author Details

Haris Angelidakis
  • ETH Zürich, Switzerland
Pranjal Awasthi
  • Rutgers University, New Brunswick, NJ, USA
Avrim Blum
  • Toyota Technological Institute at Chicago, IL, USA
Vaggos Chatziafratis
  • Stanford University, CA, USA
Chen Dan
  • Carnegie Mellon University, Pittsburgh, PA, USA

Funding

  • Angelidakis, Haris: Part of this work was done while the author was a student at TTI-Chicago, and was supported by the National Science Foundation under the grant CCF-1718820.
  • Blum, Avrim: This work was supported in part by the National Science Foundation under grants CCF-1733556, CCF-1800317, and CCF-1815011.

Acknowledgements

We would like to thank Konstantin Makarychev and Yury Makarychev for sharing their manuscript [Konstantin Makarychev and Yury Makarychev, 2018], and Yury Makarychev and Mrinalkanti Ghosh for useful discussions.

Cite As Get BibTex

Haris Angelidakis, Pranjal Awasthi, Avrim Blum, Vaggos Chatziafratis, and Chen Dan. Bilu-Linial Stability, Certified Algorithms and the Independent Set Problem. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ESA.2019.7

Abstract

We study the classic Maximum Independent Set problem under the notion of stability introduced by Bilu and Linial (2010): a weighted instance of Independent Set is gamma-stable if it has a unique optimal solution that remains the unique optimal solution under multiplicative perturbations of the weights by a factor of at most gamma >= 1. The goal then is to efficiently recover this "pronounced" optimal solution exactly. In this work, we solve stable instances of Independent Set on several classes of graphs: we improve upon previous results by solving O~(Delta/sqrt(log Delta))-stable instances on graphs of maximum degree Delta, (k - 1)-stable instances on k-colorable graphs and (1 + epsilon)-stable instances on planar graphs (for any fixed epsilon > 0), using both combinatorial techniques as well as LPs and the Sherali-Adams hierarchy.
For general graphs, we present a strong lower bound showing that there are no efficient algorithms for O(n^(1/2 - epsilon))-stable instances of Independent Set, assuming the planted clique conjecture. To complement our negative result, we give an algorithm for (epsilon n)-stable instances, for any fixed epsilon > 0. As a by-product of our techniques, we give algorithms as well as lower bounds for stable instances of Node Multiway Cut (a generalization of Edge Multiway Cut), by exploiting its connections to Vertex Cover. Furthermore, we prove a general structural result showing that the integrality gap of convex relaxations of several maximization problems reduces dramatically on stable instances. 
Moreover, we initiate the study of certified algorithms for Independent Set. The notion of a gamma-certified algorithm was introduced very recently by Makarychev and Makarychev (2018) and it is a class of gamma-approximation algorithms that satisfy one crucial property: the solution returned is optimal for a perturbation of the original instance, where perturbations are again multiplicative up to a factor of gamma >= 1 (hence, such algorithms not only solve gamma-stable instances optimally, but also have guarantees even on unstable instances). Here, we obtain Delta-certified algorithms for Independent Set on graphs of maximum degree Delta, and (1+epsilon)-certified algorithms on planar graphs. Finally, we analyze the algorithm of Berman and Fürer (1994) and prove that it is a ((Delta + 1)/3 + epsilon)-certified algorithm for Independent Set on graphs of maximum degree Delta where all weights are equal to 1.

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
  • Theory of computation → Algorithm design techniques
Keywords
  • Bilu-Linial stability
  • perturbation resilience
  • beyond worst-case analysis
  • Independent Set
  • Vertex Cover
  • Multiway Cut

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Noga Alon and Nabil Kahale. Approximating the independence number via the θ-function. Math. Program., 80:253-264, 1998. Google Scholar
  2. Noga Alon, Michael Krivelevich, and Benny Sudakov. Finding a large hidden clique in a random graph. Random Structures and Algorithms, 13(3-4):457-466, 1998. Google Scholar
  3. Haris Angelidakis, Pranjal Awasthi, Avrim Blum, Vaggos Chatziafratis, and Chen Dan. Bilu-Linial stability, certified algorithms and the Independent Set problem. CoRR, abs/1810.08414, 2018. URL: http://arxiv.org/abs/1810.08414.
  4. Haris Angelidakis, Konstantin Makarychev, and Yury Makarychev. Algorithms for stable and perturbation-resilient problems. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 438-451, 2017. Google Scholar
  5. Per Austrin, Subhash Khot, and Muli Safra. Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs. Theory of Computing, 7(1):27-43, 2011. Google Scholar
  6. Pranjal Awasthi, Avrim Blum, and Or Sheffet. Center-based clustering under perturbation stability. Inf. Process. Lett., 112(1-2):49-54, 2012. Google Scholar
  7. Brenda S. Baker. Approximation Algorithms for NP-Complete Problems on Planar Graphs. J. ACM, 41(1):153-180, 1994. Google Scholar
  8. Maria-Florina Balcan, Nika Haghtalab, and Colin White. k-Center Clustering Under Perturbation Resilience. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), pages 68:1-68:14, 2016. Google Scholar
  9. Maria-Florina Balcan and Yingyu Liang. Clustering under Perturbation Resilience. SIAM J. Comput., 45(1):102-155, 2016. Google Scholar
  10. Nikhil Bansal. Approximating independent sets in sparse graphs. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1-8, 2015. Google Scholar
  11. Nikhil Bansal, Anupam Gupta, and Guru Guruganesh. On the Lovász Theta function for Independent Sets in Sparse Graphs. In Proceedings of the 47th Annual ACM on Symposium on Theory of Computing (STOC), pages 193-200, 2015. Google Scholar
  12. Nikhil Bansal, Daniel Reichman, and Seeun William Umboh. LP-based robust algorithms for noisy minor-free and bounded treewidth graphs. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1964-1979, 2017. Google Scholar
  13. Piotr Berman and Martin Fürer. Approximating Maximum Independent Set in Bounded Degree Graphs. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 365-371, 1994. Google Scholar
  14. Daniel Bienstock and Nuri Özbay. Tree-width and the Sherali-Adams operator. Discrete Optimization, 1(1):13-21, 2004. Google Scholar
  15. Yonatan Bilu. On spectral properties of graphs and their application to clustering. PhD Thesis, pages 77-78, 2004. Google Scholar
  16. Yonatan Bilu, Amit Daniely, Nati Linial, and Michael E. Saks. On the practically interesting instances of MAXCUT. In Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 526-537, 2013. Google Scholar
  17. Yonatan Bilu and Nathan Linial. Are Stable Instances Easy? Combinatorics, Probability & Computing, 21(5):643-660, 2012. Google Scholar
  18. Avrim Blum and Joel Spencer. Coloring random and semi-random k-colorable graphs. Journal of Algorithms, 19(2):204-234, 1995. Google Scholar
  19. Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science, 209(1):1-45, 1998. Google Scholar
  20. R. L. Brooks. On colouring the nodes of a network. Mathematical Proceedings of the Cambridge Philosophical Society, 37(2):194-197, 1941. Google Scholar
  21. Siu On Chan. Approximation Resistance from Pairwise-Independent Subgroups. J. ACM, 63(3):27:1-27:32, 2016. Google Scholar
  22. Vaggos Chatziafratis, Tim Roughgarden, and Jan Vondrák. Stability and Recovery for Independence Systems. In Proceedings of the 25th Annual European Symposium on Algorithms (ESA), pages 26:1-26:15, 2017. Google Scholar
  23. Chandra Chekuri and Shalmoli Gupta. Perturbation Resilient Clustering for k-Center and Related Problems via LP Relaxations. In Proceedings of the 21st International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2018. Google Scholar
  24. Eden Chlamtac and Madhur Tulsiani. Convex Relaxations and Integrality Gaps, pages 139-169. Springer US, Boston, MA, 2012. Google Scholar
  25. Vincent Cohen-Addad and Chris Schwiegelshohn. On the Local Structure of Stable Clustering Instances. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 49-60, 2017. Google Scholar
  26. Amit Deshpande, Anand Louis, and Apoorv Vikram Singh. On Euclidean k-Means Clustering with alpha-Center Proximity. In the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS), pages 2087-2095, 2019. Google Scholar
  27. Uriel Feige. Approximating Maximum Clique by Removing Subgraphs. SIAM J. Discrete Math., 18(2):219-225, 2004. Google Scholar
  28. Uriel Feige and Joe Kilian. Heuristics for semirandom graph problems. Journal of Computer and System Sciences, 63(4):639-671, 2001. Google Scholar
  29. Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, and Ying Xiao. Statistical Algorithms and a Lower Bound for Detecting Planted Cliques. J. ACM, 64(2):8:1-8:37, 2017. Google Scholar
  30. Zachary Friggstad, Kamyar Khodamoradi, and Mohammad R. Salavatipour. Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-MEANS. In Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2958-2972, 2019. Google Scholar
  31. Magnús M. Halldórsson. Approximations of Weighted Independent Set and Hereditary Subset Problems. J. Graph Algorithms Appl., 4(1), 2000. Google Scholar
  32. Magnús M. Halldórsson and Jaikumar Radhakrishnan. Improved Approximations of Independent Sets in Bounded-Degree Graphs via Subgraph Removal. Nord. J. Comput., 1(4):475-492, 1994. Google Scholar
  33. Eran Halperin. Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs. SIAM J. Comput., 31(5):1608-1623, 2002. Google Scholar
  34. Johan Håstad. Clique is Hard to Approximate Within n^1-ε. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS), pages 627-636, 1996. Google Scholar
  35. Dorit S. Hochbaum. Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Applied Mathematics, 6(3):243-254, 1983. Google Scholar
  36. Akihisa Kako, Takao Ono, Tomio Hirata, and Magnús M. Halldórsson. Approximation algorithms for the weighted independent set problem in sparse graphs. Discrete Applied Mathematics, 157(4):617-626, 2009. Google Scholar
  37. Subhash Khot and Ashok Kumar Ponnuswami. Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion. In Proceedings of the 33rd International Colloquium on Automata, Languages, and Programming (ICALP), pages 226-237, 2006. Google Scholar
  38. Hunter Lang, David Sontag, and Aravindan Vijayaraghavan. Optimality of Approximate Inference Algorithms on Stable Instances. In the 21st International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1157-1166, 2018. Google Scholar
  39. Hunter Lang, David Sontag, and Aravindan Vijayaraghavan. Block Stability for MAP Inference. In the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS), pages 216-225, 2019. Google Scholar
  40. Avner Magen and Mohammad Moharrami. Robust Algorithms for Maximum Independent Set on Minor-Free Graphs Based on the Sherali-Adams Hierarchy. In Proceedings of the 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 258-271, 2009. Google Scholar
  41. Konstantin Makarychev and Yury Makarychev. Certified approximation algorithms: Bridging worst-case and beyond-the-worst-case analysis. Manuscript, 2018. Google Scholar
  42. Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 890-906, 2014. Google Scholar
  43. Yury Makarychev. Private communication, 2018. Google Scholar
  44. Raghu Meka, Aaron Potechin, and Avi Wigderson. Sum-of-squares Lower Bounds for Planted Clique. In Proceedings of the 47th Annual ACM on Symposium on Theory of Computing (STOC), pages 87-96, 2015. Google Scholar
  45. Matús Mihalák, Marcel Schöngens, Rastislav Srámek, and Peter Widmayer. On the Complexity of the Metric TSP under Stability Considerations. In SOFSEM 2011: Theory and Practice of Computer Science - 37th Conference on Current Trends in Theory and Practice of Computer Science, pages 382-393, 2011. Google Scholar
  46. G. L. Nemhauser and L. E. Trotter. Vertex packings: Structural properties and algorithms. Mathematical Programming, 8(1):232-248, 1975. Google Scholar
  47. Leslie G. Valiant and Vijay V. Vazirani. NP is as easy as detecting unique solutions. Theor. Comput. Sci., 47(3):85-93, 1986. Google Scholar
  48. David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pages 681-690, 2006. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact