Projects per year
Abstract
This paper studies kclawfree graphs, exploring the connection between an extremal combinatorics question and the power of a convex program in approximating the maximumweight independent set in this graph class. For the extremal question, we consider the notion, that we call conditional Xboundedness of a graph: Given a graph G that is assumed to contain an independent set of a certain (constant) size, we are interested in upper bounding the chromatic number in terms of the clique number of G. This question, besides being interesting on its own, has algorithmic implications (which have been relatively neglected in the literature) on the performance of SDP relaxations in estimating the value of maximumweight independent set. For k=3, Chudnovsky and Seymour (JCTB 2010) prove that any 3clawfree graph G with an independent set of size three must satisfy. Their result implies a factor 2estimation algorithm for the maximum weight independent set via an SDP relaxation (providing the first nontrivial result for maximumweight independent set in such graphs via a convex relaxation). An obvious open question is whether a similar conditional Xboundedness phenomenon holds for any kclawfree graph. Our main result answers this question negatively. We further present some evidence that our construction could be useful in studying more broadly the power of convex relaxations in the context of approximating maximum weight independent set in kclaw free graphs. In particular, we prove a lower bound on families of convex programs that are stronger than known convex relaxations used algorithmically in this context.
Original language  English 

Title of host publication  Approximation and Online Algorithms  21st International Workshop, WAOA 2023, Proceedings 
Editors  Jarosław Byrka, Andreas Wiese 
Publisher  Springer 
Pages  205218 
Number of pages  14 
ISBN (Print)  9783031498145 
DOIs  
Publication status  Published  2023 
MoE publication type  A4 Conference publication 
Event  Workshop on Approximation and Online Algorithms  Amsterdam, Netherlands Duration: 7 Sept 2023 → 8 Sept 2023 Conference number: 21 
Publication series
Name  Lecture Notes in Computer Science 

Publisher  Springer 
Volume  14297 LNCS 
ISSN (Print)  03029743 
ISSN (Electronic)  16113349 
Workshop
Workshop  Workshop on Approximation and Online Algorithms 

Abbreviated title  WAOA 
Country/Territory  Netherlands 
City  Amsterdam 
Period  07/09/2023 → 08/09/2023 
Keywords
 Convex relaxation
 Ramsey theory
 Xboundedness
Fingerprint
Dive into the research topics of 'Independent Set in kClawFree Graphs : Conditional XBoundedness and the Power of LP/SDP Relaxations'. Together they form a unique fingerprint.Projects
 2 Finished

ALGOCom: Novel Algorithmic Techniques through the Lens of Combinatorics
Chalermsook, P. (Principal investigator), Jindal, G. (Project Member), Franck, M. (Project Member), Khodamoradi, K. (Project Member), Yingchareonthawornchai, S. (Project Member), Gadekar, A. (Project Member), Orgo, L. (Project Member), Jiamjitrak, W. (Project Member) & Spoerhase, J. (Project Member)
01/02/2018 → 31/01/2024
Project: EU: ERC grants

Combinatorics of Graph Packing and Online Binary Search Trees
Chalermsook, P. (Principal investigator), Franck, M. (Project Member), Uniyal, S. (Project Member), Obscura Acosta, N. (Project Member), Gadekar, A. (Project Member) & Jiamjitrak, W. (Project Member)
01/09/2017 → 31/08/2022
Project: Academy of Finland: Other research funding