ECCC-Report TR12-032https://eccc.weizmann.ac.il/report/2012/032Comments and Revisions published for TR12-032en-usWed, 04 Apr 2012 20:31:30 +0300
Paper TR12-032
| Interval graph representation with given interval and intersection lengths |
Sebastian Kuhnert,
Johannes Köbler,
Osamu Watanabe
https://eccc.weizmann.ac.il/report/2012/032We consider the problem of finding interval representations of graphs 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 proved that the problem is NP-complete if only the former are given [SIAM J. Discr. Math. 10.4, 1997]. We give both a logspace and a linear-time algorithm for the case when both are given, and both a logspace and an $O(nm)$ time algorithm when only the latter are given. We also show that the resulting interval systems are unique up to isomorphism.
Complementing their hardness result, Pe'er and Shamir give a polynomial-time algorithm for the case that the input graph has a unique minimal interval representation. For such graphs, their algorithm computes an interval representation that respects a given set of distance inequalities between the interval endpoints (if it exists). We observe that deciding if such a representation exists is NL-complete.Wed, 04 Apr 2012 20:31:30 +0300https://eccc.weizmann.ac.il/report/2012/032