@Article{KKV16pca,
  author =       {Johannes Köbler and Sebastian Kuhnert and Oleg Verbitsky},
  title =        {Solving the canonical representation and star system problems
                  for proper circular-arc graphs in logspace},
  journal =      {Journal of Discrete Algorithms},
  year =         2016,
  volume =       {38-41},
  pages =        {38-49},
  issn =         {1570-8667},
  doi =          {10.1016/j.jda.2016.03.001},
}

Solving the canonical representation and star system problems for proper circular-arc graphs in logspace.
With Johannes Köbler, Oleg Verbitsky.
Journal of Discrete Algorithms 38–41:38–49 (2016)

Abstract.

We present a logspace algorithm that constructs a canonical intersection model for a given proper circular-arc graph, where /canonical/ means that isomorphic graphs receive identical models. This implies that the recognition and the isomorphism problems for these graphs are solvable in logspace. For the broader class of concave-round graphs, which still possess (not necessarily proper) circular-arc models, we show that a canonical circular-arc model can also be constructed in logspace. As a building block for these results, we design a logspace algorithm for computing canonical circular-arc models of circular-arc hypergraphs. This class of hypergraphs corresponds to matrices with the /circular ones property/, which play an important role in computational genomics. Our results imply that there is a logspace algorithm that decides whether a given matrix has this property.

Furthermore, we consider the Star System Problem that consists in reconstructing a graph from its closed neighborhood hypergraph. We show that this problem is solvable in logarithmic space for the classes of proper circular-arc, concave-round, and co-convex graphs.

Note that solving a problem in logspace implies that it is solvable by a parallel algorithm of the class AC¹. For the problems under consideration, at most AC² algorithms were known earlier.

@InProceedings{KKV12pca,
  author =       {Johannes Köbler and Sebastian Kuhnert and Oleg Verbitsky},
  title =        {Solving the canonical representation and star system
                  problems for proper circular-arc graphs in logspace},
  booktitle =    {Proc. 32nd FSTTCS},
  pages =        {387-399},
  year =         2012,
  editor =       {Deepak D'Souza and Telikepalli Kavitha and
                  Jaikumar Radhakrishnan},
  series =       {LIPIcs},
  number =       18,
  publisher =    {Leibniz-Zentrum für Informatik},
  address =      {Dagstuhl},
  isbn =         {978-3-939897-47-7},
  doi =          {10.4230/LIPIcs.FSTTCS.2012.387},
}

Conference version:
Solving the canonical representation and star system problems for proper circular-arc graphs in logspace
With Johannes Köbler, Oleg Verbitsky.
Proceedings of 32nd FSTTCS. Leibniz-Zentrum für Informatik, 2012. Pp. 387–399.