Strip Graphs: Recognition and Scheduling

We consider the class of strip graphs, a generalization of interval graphs. Intervals are assigned to rows such that two vertices have an edge between them if either their intervals intersect or they belong to the same row. We show that recognition of the class of strip graphs is

$\mathcal{NP}$

-complete even if all intervals are of length 2. Strip graphs are important to the study of job selection, where we need an equivalence relation to connect multiple intervals that belong to the same job.

The problem we consider is Job Interval Selection (JISP) on

m

machines. In the single-machine case, this is equivalent to Maximum Independent Set on strip graphs. For

m

machines, the problem is to choose a maximum number of intervals, one from each job, such that the resulting choices form an

m

-colorable interval graph. We show the single-machine case to be fixed-parameter tractable in terms of the maximum number of overlapping rows. We also use a concatenation operation on strip graphs to reduce the

m

-machine case to the 1-machine case. This shows that

m

-machine JISP is fixed-parameter tractable in the total number of jobs.