Approximating the Maximum k-Colorable Subgraph Problem on Dotted Interval Graphs

Overview

MAXIMUM k-COLORABLE SUBGRAPH is a classic NP-Complete problem that inputs a simple graph G with n vertices and k colors; it asks for the largest subgraph in which every vertex is colored and no two vertices that share an edge have the same color. When k = 1, this problem becomes equivalent to the famous MAXIMUM INDEPENDENT SET Problem, which cannot even be approximated to a factor of n^(1-epsilon) for any epsilon > 0 in polynomial-time. The dotted interval graph DIG_D, first introduced as a generalization of the interval graph by Aumann et. al, represents the intersection of n arithmetic progressions with common differences at most D. We first prove that MAXIMUM k-COLORABLE SUBGRAPH is NP-Complete for D >= 2 on this class of graphs. We then present and analyze an approximation algorithm for this problem. Our algorithm generalizes a union-find procedure that was first established by Carlisle and Lloyd to solve the problem on the class of interval graphs (DIG_1) in 1991. In our analysis of the algorithm, we provide mathematical proofs to show 1) the returned solutions will always be feasible, 2) the approximation ratio is 1/D, and 3) the running time is bounded by O(n+k). We also give a second algorithm that can convert any dotted interval graph into an equivalent simple graph with vertices and edges in O(n^2 * logD)-time. Finally, we present a possible application of this mathematical work to genotyping, in which we approximate the optimal experimentation schedule for the simultaneous multiplexing of microsatellites.

Competition history

• ISEF 2015 Category not listed · Entry MATH032I

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.