Article ID Journal Published Year Pages File Type
431610 Journal of Discrete Algorithms 2015 10 Pages PDF
Abstract

We consider the problem of finding interval graph representations that additionally respect given interval lengths and/or pairwise intersection lengths, which are represented as weight functions on the vertices and edges, respectively. Pe'er and Shamir (1997 [25]) proved that the problem is NPNP-complete if only the former are given. For the case when both are given, Fulkerson and Gross (1965 [8]) gave an O(n2)O(n2) time algorithm; we improve this to O(n+m)O(n+m) time and supplement it with a logspace algorithm. For the case when only the latter are given, we give both an O(nm)O(nm) time algorithm and a logspace algorithm. In all these bounds, n is the number of vertices and m is the number of edges in the input graph.Complementing their hardness result, Pe'er and Shamir give a polynomial-time algorithm for the case that the input graph has a unique interval ordering of its maximal cliques. For such graphs, their algorithm computes an interval representation (if it exists) that respects a given set of distance inequalities between the interval endpoints. We observe that deciding if such a representation exists is NLNL-complete.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,