Balanced Independent and Dominating Sets on Colored Interval Graphs

Sujoy Bhore, Jan-Henrik Haunert, Fabian Klute, Guangping Li, Martin Nöllenburg

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.

Figure 1: A reduction from a 3SAT formula to a colored interval graph instance, where intervals represent literals and color classes correspond to clauses.

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.

Figure 2: Detailed gadget construction for the hardness reduction, showing variable gadgets (x1, x2, x3) and their connections to clause requirements.

Algorithmic Frameworks

Despite the inherent hardness, the paper provides several algorithmic pathways for solving these problems when certain parameters are small:

  1. 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$.
  2. 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.
  3. 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

Abstract

We study two new versions of independent and dominating set problems on vertex-colored interval graphs, namely f-Balanced Independent Set (f-BIS) and f-Balanced Dominating Set (f-BDS). Let \(G=(V,E)\) be an interval graph with a color assignment function \({{\,\mathrm{\gamma }\,}}:V \rightarrow \{1,\ldots ,k\}\) that maps all vertices in G onto k colors. A subset of vertices \(S\subseteq V\) is called f-balanced if S contains f vertices from each color class. In the f-BIS and f-BDS problems, the objective is to compute an independent set or a dominating set that is f-balanced. We show that both problems are NP-complete even on proper interval graphs. For the BIS problem on interval graphs, we design two FPT algorithms, one parameterized by (f, k) and the other by the vertex cover number of G. Moreover, for an optimization variant of BIS on interval graphs, we present a polynomial time approximation scheme (PTAS) and an \(O(n\log n)\) time 2-approximation algorithm.
BibTeX
@inproceedings{bhore2021balanced,
  author = {Sujoy Bhore and Jan-Henrik Haunert and Fabian Klute and Guangping Li and Martin Nöllenburg},
  title = {{Balanced Independent and Dominating Sets on Colored Interval Graphs}},
  booktitle = {SOFSEM},
  year = {2021},
  doi = {10.1007/978-3-030-67731-2\_7},
}
Figure