Paper Info
Title
Bi-Arc Digraphs and Conservative Polymorphisms.
Abstract
We introduce the class of bi-arc digraphs, and show they coincide with the class of digraphs that admit a conservative semi-lattice polymorphism, i.e., a min ordering. Surprisingly this turns out to be also the class of totally symmetric conservative polymorphisms of all arities. We give an obstruction characterization of, and a polynomial time recognition algorithm for, this class of digraphs. The existence of a polynomial time algorithm was an open problem due to Bagan, Durand, Filiot, and Gauwin. We also discuss a generalization to $k$-arc digraphs, which has a similar obstruction characterization and recognition algorithm. When restricted to undirected graphs, the class of bi-arc digraphs is included in the previously studied class of bi-arc graphs. In particular, restricted to reflexive graphs, bi-arc digraphs coincide precisely with the well known class of interval graphs. Restricted to reflexive digraphs, they coincide precisely with the class of adjusted interval digraphs, and restricted to bigraphs, they coincide precisely with the class of two directional ray graphs. All these classes have been previously investigated as analogues of interval graphs. We believe that, in a certain sense, bi-arc digraphs are the most general digraph version of interval graphs with nice algorithms and characterizations.
Year
Venue
Field
2016
arXiv: Data Structures and Algorithms
Discrete mathematics,Graph,Bigraph,Combinatorics,Arc (geometry),Open problem,Recognition algorithm,Time complexity,Mathematics,Digraph
DocType
Volume
Citations 
Journal
abs/1608.03368
2
PageRank 
References 
Authors
0.37
16
2
Name
Order
Citations
PageRank
Pavol Hell12638288.75
Arash Rafiey233928.08