Abstract: This paper investigates the computational complexity of finding balanced independent and dominating sets in colored interval graphs. While finding a maximum independent set in an interval graph is a classic polynomial-time problem, the introduction of "fairness" or "diversity" constraints—requiring a specific number of vertices from each color class—significantly increases the problem's difficulty. We demonstrate that these balanced variants are NP-complete even on proper interval graphs, but we provide fixed-parameter tractable (FPT) algorithms and approximation strategies for practical use cases.
Introduction
In many optimization scenarios, the goal is not merely to find the largest possible solution, but one that is representative across multiple categories. For instance, in automated map labeling, an algorithm must select a set of non-overlapping labels (an independent set problem). If labels represent different types of points of interest (e.g., cinemas vs. museums), a standard maximum independent set might disproportionately favor one category.
To address this, the authors propose $f$-Balanced problems. Given a graph where each vertex is assigned a color, an $f$-balanced set must contain exactly $f$ vertices from every color class:
- $f$-BIS ($f$-Balanced Independent Set): Find $f$ non-adjacent vertices per color.
- $f$-BDS ($f$-Balanced Dominating Set): Find $f$ vertices per color such that every vertex in the graph is either in the set or adjacent to a member of the set.
Complexity and Hardness Reductions
The core finding of the paper is that the "global" constraint of color balance breaks the "local" greedy properties that typically make interval graphs easy to solve. The authors prove that both $f$-BIS and $f$-BDS are NP-complete on proper interval graphs (where no interval is strictly contained within another), even for the simplest case where $f=1$.
To establish this hardness, the authors employ reductions from the 3-Satisfiability (3SAT) problem. They construct interval graph instances where the selection of specific intervals corresponds to assigning truth values to variables in a Boolean formula.
As shown in Figure 1, the construction maps the logical structure of a 3SAT formula into overlapping intervals. The requirement to pick one vertex per color (representing a clause) forces the selection of a set of intervals that corresponds to a satisfying assignment. Figure 2 illustrates the more intricate gadgetry required to ensure consistency across variable assignments and clause satisfaction in the graph structure.
Algorithmic Frameworks
Despite the inherent hardness, the paper provides several algorithmic pathways for solving these problems when certain parameters are small:
- Dynamic Programming (FPT): For $f$-BIS, the authors design an algorithm using a sweep-line approach. By processing intervals from left to right and maintaining a "cardinality vector" of selected colors, the problem is solved in $O(n \log n + k(f + 1)^k n)$ time. This is fixed-parameter tractable (FPT) with respect to the number of colors $k$.
- Vertex Cover Parameterization: An alternative FPT algorithm is provided for general graphs based on the size of the minimum vertex cover, leveraging the limited number of maximal independent sets in such graphs.
- Greedy Approximation: For the optimization variant (1-MCIS), where the goal is to maximize the number of colors represented by picking at most one vertex per color, a greedy sweep-line strategy yields a 2-approximation.
Key Results and Insights
- Simplicity is Deceptive: Proper interval graphs, usually the "easiest" class for independent set problems, become intractable under color constraints.
- Scheduling Links: The 1-BIS problem is shown to be equivalent to the Job Interval Scheduling Problem (JISP), bridging graph theory and operations research.
- Planarity Correction: The authors clarify that the constructed graphs are non-planar (containing $K_{3,3}$ minors), which proves the problem is APX-hard and precludes certain types of approximation schemes.
Conclusion and Future Work
While the paper provides robust FPT algorithms, the runtime scales exponentially with the number of colors, limiting use in high-diversity datasets. Future research may extend these findings to higher-dimensional geometric intersection graphs, such as rectangle or unit disk graphs, which are highly relevant for 2D visualization and sensor network deployment. Additionally, the algorithmic gap for the Dominating Set version ($f$-BDS) remains an open area for further parameterized analysis.
Summary updated