On the Complexity of Bilevel Independent Set Problem
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910255410053120 |
|---|---|
| author | Muluk, Komal |
| author_facet | Muluk, Komal |
| contents | We consider a bilevel optimization problem in which the ground set is partitioned between two decision makers, a leader and a follower, whose optimization problems are interleaved. We study the Bilevel Independent Set problem, and its special case, the Bilevel Interval Selection problem, on different variants emerging from a combination of the type of leader's objective function, the type of follower's objective function, and the setting in which the follower reacts, i.e., either optimistically or pessimistically. Here we consider sum and bottleneck type objective functions. We investigate the computational complexity of all these variants for the Bilevel Independent Set problem, and sort them into their respective level of the polynomial hierarchy. Our results range from $\mathsf{P}$, $\mathsf{NP}$-completeness to $Σ_2^\mathsf{p}$-completeness. For the Bilevel Interval Selection problem, we give a dynamic programming algorithm running in time $\mathcal{O}(n^4\log n)$ for the variants in which the leader and the follower have objective functions of the sum type. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_25927 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the Complexity of Bilevel Independent Set Problem Muluk, Komal Data Structures and Algorithms Optimization and Control We consider a bilevel optimization problem in which the ground set is partitioned between two decision makers, a leader and a follower, whose optimization problems are interleaved. We study the Bilevel Independent Set problem, and its special case, the Bilevel Interval Selection problem, on different variants emerging from a combination of the type of leader's objective function, the type of follower's objective function, and the setting in which the follower reacts, i.e., either optimistically or pessimistically. Here we consider sum and bottleneck type objective functions. We investigate the computational complexity of all these variants for the Bilevel Independent Set problem, and sort them into their respective level of the polynomial hierarchy. Our results range from $\mathsf{P}$, $\mathsf{NP}$-completeness to $Σ_2^\mathsf{p}$-completeness. For the Bilevel Interval Selection problem, we give a dynamic programming algorithm running in time $\mathcal{O}(n^4\log n)$ for the variants in which the leader and the follower have objective functions of the sum type. |
| title | On the Complexity of Bilevel Independent Set Problem |
| topic | Data Structures and Algorithms Optimization and Control |
| url | https://arxiv.org/abs/2605.25927 |