When mathematics meets party planning: a new approach to the maximum independent set problem question

Our postdoc researcher, Mathieu Mari, explaines his recent paper on maximum independent set problem using the metaphore of organizing a party. Let’s get it started then!

19 May 2022

Imagine that you are organizing a party for your birthday, and you are thinking about which friends to invite. Ideally, you would like to invite everyone. The problem is that some of your friends are in conflict, and you would naturally prefer to avoid any dispute during your birthday. For instance, you know that Janusz would not come if either Andrzej, Antoni, Jarek, or Mateusz are also invited; that Grażyna cannot stand either Andrzej, Antoni, or Zbigniew; and probably that having Antoni and either Mateusz or Zbigniew in the same place would potentially ruin the party. To decide who to invite to avoid any potential conflict, you can represent this problem by a ‘conflict’ graph by putting an edge between any two of your friends that are in conflict.

For a collection of geometric objects in the Euclidean plane (for example disks, squares, rectangles, etc.), we can create an intersection graph that has one node for each object, and two objects are connected by an edge in the graph if they overlap in the plane. Finding an independent set in this intersection graph is equivalent to finding a family of objects in the Euclidean plane that does not intersect.

Mathieu Mari

postdoc researcher at IDEAS, NCBR

The perfect guest list

To avoid any conflict, you should invite some friends that form an independent set in this graph, that is nodes (here “your friends”), such that no two of them are connected by an edge (here “are in conflict”). For instance, you could invite Janusz and Grażyna, but this is not a very satisfying solution because then, you cannot invite anyone else. It seems that here, the optimal choice to have a peaceful party is to invite Zbigniew, Jarek, Mateusz, and Andrzej. In the language of graph theory, we say that they form a maximum independent set.

On small graphs, it is easy to find a maximum independent set by hand. However, on larger graphs, the task becomes much harder. Scholars of complexity theory would say that the Maximum Independent set problem is NP-hard, which means that unless the famous conjecture P≠NP is disproved, there is no fast algorithm to solve exactly this problem. Håstad showed that the situation is even worse: unless P=NP, there is no fast algorithm that computes a good approximate solution.

Håstad’s observation pushed computer scientists to look for good and fast algorithms for the Maximum Independent set problem in more restricted families of graphs. One particular type of graph that has attracted a lot of attention is called geometric intersection. For a collection of geometric objects in the Euclidean plane (for example disks, squares, rectangles, etc.), we can create an intersection graph that has one node for each object, and two objects are connected by an edge in the graph if they overlap in the plane. Finding an independent set in this intersection graph is equivalent to finding a family of objects in the Euclidean plane that does not intersect.

Here, the largest set of non-overlapping objects, or equivalently the maximum independent set in its intersection graph, is the set {A,C,E}.

Researchers have tried to understand the approximability of the maximum independent set problem for these geometric intersection graphs. And today, it is now well-understood for most of the most natural geometric objects: Intervals, disks, squares, etc. One important case which remains unsolved is the case of axis-parallel rectangles, for which we are still not able to describe the best approximation algorithm. Apart from its importance for the computational geometry community, this question is also motivated by numerous applications in practice including for instance channel admission control, map labeling, and data mining. Now a bit of history on the maximum independent set problem of Rectangles (in short MISR). There are multiple O(log n)-approximation algorithms. It had been a long-standing open problem to find a constant-approximation algorithm for MISR. One possible approach for this is to compute an optimal solution to the canonical linear programming relaxation of MISR and round it. This approach was used by Chalermsook and Chuzhoy to obtain an O(log log n)-approximation. On the other hand, it seems likely that MISR admits even a (1+ε)-approximation, given that it admits a QPTAS due to Adamaszek and Wiese.

A new approach to MISR.

Recently, in a breakthrough result presented in FOCS 2021, Mitchell proposed the first constant-approximation algorithm for the maximum independent set problem of rectangles and consequently solved the aforementioned long-standing open problem. Instead of rounding the linear program, he employs a recursive partitioning of the plane into a special type of rectilinear polygons called corner-clipped rectangles (CCRs). Given a CCR, he recursively subdivides it into at most five smaller CCRs until he obtains CCRs which essentially contain at most one rectangle from the optimal solution OPT each. In the end, he outputs the rectangles contained in these final CCRs plus some carefully chosen rectangles from OPT that are intersected by these recursive cuts. With a dynamic program, he computes the recursive partition that yields the largest number of output rectangles, which in particular “remembers” in each step a constant number of rectangles that were intersected by some previous cuts. In a structural theorem, he shows that there exists a set of at least |OPT|/10 rectangles that can be output by such a recursive partitioning, leading to the approximation ratio of 10. The structural theorem is proved using an exhaustive case analysis for defining the subdivision of a given CCR, with sixty cases in total.

Mitchell’s result yields several interesting open questions, most notably whether one can improve the approximation ratio and whether one can give a simpler analysis that does not rely on a large case distinction.

In a paper presented at SODA 22, Mathieu Mari and his co-authors answered both questions in the affirmative. In particular, they obtained a (2+ ε)-approximation algorithm for MISR which is also based on a recursive partitioning scheme. First, they use a partition into a class of axis-parallel polygons with constant complexity each more general than CCRs. This allows them to provide an arguably simpler analysis and at the same time already improves the approximation ratio to 4. Then, using a more elaborate charging scheme and a recursive partitioning into general axis-parallel polygons with constant complexity, they improve the approximation ratio to 2+ ε. In particular, they construct a recursive partitioning based on more general fences which can be sequences of up to 1/ε line segments each. This partitioning routine and their other new ideas may be useful for future work towards a (1+ε)-approximation for MISR. For more details, see the paper published on arxiv: https://arxiv.org/abs/2106.00623

To prove that the approximation ratio is bounded by 2+ ε, the authors had to develop an intricate charging scheme. This work has contributed to simplifying and exploiting the potential of Michell’s idea for the maximum independent set problem of rectangles. In particular, the new best approximation ratio for this problem can be arbitrarily close to 2. It seems that to improve further this approximation, and eventually exhibit the hidden PTAS, substantially new ideas will be needed. In the meantime, don’t worry even if you haven’t found the optimal independent set of friends for your party. Since the laws of friendship are usually less strict and formal than those of mathematics perhaps you could also just give Janusz, Grażyna and Jarek chance to clear things up between them?

Author: Mathieu Mari

Mathieu Mari is a postdoctoral fellow in IDEAS-NCBR and the University of Warsaw. Before coming to Poland, he achieved his Ph.D. at École Normale Supérieure de Paris, under the supervision of Claire Mathieu and Chien-Chung Huang. Mari’s work focuses on the design and the analysis of algorithms, including approximation algorithms, graph algorithms, and computational geometry. Recently, his interest is turning towards artificial intelligence and machine learning topics.

The IDEAS NCBR’s working group that will deal with research in the field of computer vision will be headed by habilitated doctor engineer Tomasz Trzciński, professor at the Warsaw University of Technology and at the Jagiellonian University. The research agenda of the group will focus on issues related to the effectiveness of artificial intelligence models both in the context of the accuracy and pace of computations, as well as resources necessary for their operation.

IDEAS NCBR has signed the understanding on cooperation with Center For Artificial Intelligence and Advanced Robotics at National Taiwan University, and research centre CVC Barcelona working on computer vision.

Dear User
we use cookies on this website to facilitate its use. This happens by saving information on the device you use when visiting our website. Taking care of your right to privacy, you can set your preferences regarding the use of cookies below. These settings can be changed at any time. However, please note that blocking certain types of cookies may have a negative impact on the use of our website and the services we offer.

Some of the cookies we use are essential for the website to function properly. You cannot change the use of these cookies in your preferences settings.

For more information on the types of cookies used, see Cookies Policy

these are files that are responsible for the proper operation of our website; their purpose is to enable the use of the services we provide, e.g. remembering the preferences for choosing the use of cookies, login authentication and ensuring security. These files may process the user's personal data. You cannot disable these files as part of your preferences settings, but you can block them in your browser settings. However, this action may result in some parts of the website not being available;

these are files that we use to personalize and optimize the use of our website. These files are used to remember the choices made regarding, for example, font size, language selection or content display resolution settings. These files do not process personal data. You can manage these files in your cookie preferences. If you do not agree, some functions of the website may not work properly;

these are files that we use to collect information about the use of our website, e.g. the number of visits, time spent, time of viewed content or access sources. These files allow us to understand how you use our website, which helps to better match the website and displayed content. These files do not contain personal data, but only anonymous information not assigned to the user. These files can be managed in the cookie preferences settings. If you do not consent, we will not know when, how often, for how long and from what access sources you visit our website;

these are files that enable the provision of personalized advertising content to the user (based on the collected information tailored to the user's preferences and interests). If you do not accept these cookies, you will not be able to use our website.