The hardness of the functional orientation 2-color problem

MaRDI QIDQ2848741zbMATH OpenFDO

Authors Søren Bøg, Morten Stöckel, Hjalte Wedel Vildhøj

Publication date 26 September 2013

Published in The Australasian Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.2544

zbMATH Keywords

2-color problemfunctional orientation

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15)

Abstract: We consider the Functional Orientation 2-Color problem, which was introduced by Valiant in his seminal paper on holographic algorithms [SIAM J. Comput., 37(5), 2008]. For this decision problem, Valiant gave a polynomial time holographic algorithm for planar graphs of maximum degree 3, and showed that the problem is NP-complete for planar graphs of maximum degree 10. A recent result on defective graph coloring by Corr^ea et al. [Australas. J. Combin., 43, 2009] implies that the problem is already hard for planar graphs of maximum degree 8. Together, these results leave open the hardness question for graphs of maximum degree between 4 and 7. We close this gap by showing that the answer is always yes for arbitrary graphs of maximum degree 5, and that the problem is NP-complete for planar graphs of maximum degree 6. Moreover, for graphs of maximum degree 5, we note that a linear time algorithm for finding a solution exists.

Review text

A functional orientation of a graph is a function \(f\) from the vertex set to itself such that each vertex \(u\) is adjacent to \(v = f(u)\). The name arises from assigning a direction on the edge \(uv\): each vertex then has exactly one edge directed outwards. Functional orientations occur in applications such as finite-state machines, the analysis of algorithms, and hash functions.NEWLINENEWLINEThe functional orientation 2-color problem is to determine when a graph has a vertex 2-coloring and a functional orientation \(f\) such that any edge \(uv\) joining two vertices of the same color has either \(f(u) = v\) or \(f(v) = u\). This problem is known to be NP-complete for planar graphs of maximum degree at least ten, but is polynomial-time solvable for planar graphs of maximum degree three.NEWLINENEWLINEThe authors show that this problem is solvable in linear time for planar graphs of maximum degree five and is NP-complete for planar graphs of maximum degree six.

Recommendations

• Oriented coloring in planar, bipartite, bounded degree 3 acyclic oriented graphs
• SOFSEM 2006: Theory and Practice of Computer Science
• The complexity of the proper orientation number
• Orientations of graphs with prescribed weighted out-degrees
• Computational complexity of (2,2) path chromatic number problem

Cited in

(1)

• Orientations of graphs with prescribed weighted out-degrees

This page was built for publication: The hardness of the functional orientation 2-color problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2848741)