Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the Complexity of Role Colouring Planar Graphs, Trees and Cographs
150
0
0.0
(
0
)
Added by
Michaela Rombach
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We prove several results about the complexity of the role colouring problem. A role colouring of a graph $G$ is an assignment of colours to the vertices of $G$ such that two vertices of the same colour have identical sets of colours in their neighbourhoods. We show that the problem of finding a role colouring with $1< k <n$ colours is NP-hard for planar graphs. We show that restricting the problem to trees yields a polynomially solvable case, as long as $k$ is either constant or has a constant difference with $n$, the number of vertices in the tree. Finally, we prove that cographs are always $k$-role-colourable for $1<kleq n$ and construct such a colouring in polynomial time.
rate research
Read More
Best match graphs (BMG) are a key intermediate in graph-based orthology detection and contain a large amount of information on the gene tree. We provide a near-cubic algorithm to determine whether a BMG is binary-explainable, i.e., whether it can be explained by a fully resolved gene tree and, if so, to construct such a tree. Moreover, we show that all such binary trees are refinements of the unique binary-resolvable tree (BRT), which in general is a substantial refinement of the also unique least resolved tree of a BMG. Finally, we show that the problem of editing an arbitrary vertex-colored graph to a binary-explainable BMG is NP-complete and provide an integer linear program formulation for this task.
We examine the effect of bounding the diameter for well-studied variants of the Colouring problem. A colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. The corresponding decision problems are Acyclic Colouring, Star Colouring and Injective Colouring. The last problem is also known as $L(1,1)$-Labelling and we also consider the framework of $L(a,b)$-Labelling. We prove a number of (almost-)complete complexity classifications. In particular, we show that for graphs of diameter at most $d$, Acyclic $3$-Colouring is polynomial-time solvable if $dleq 2$ but NP-complete if $dgeq 4$, and Star $3$-Colouring is polynomial-time solvable if $dleq 3$ but NP-complete for $dgeq 8$. As far as we are aware, Star $3$-Colouring is the first problem that exhibits a complexity jump for some $dgeq 3$. Our third main result is that $L(1,2)$-Labelling is NP-complete for graphs of diameter $2$; we relate the latter problem to a special case of Hamiltonian Path.
For $kgeq 1$, a $k$-colouring $c$ of $G$ is a mapping from $V(G)$ to ${1,2,ldots,k}$ such that $c(u) eq c(v)$ for any two non-adjacent vertices $u$ and $v$. The $k$-Colouring problem is to decide if a graph $G$ has a $k$-colouring. For a family of graphs ${cal H}$, a graph $G$ is ${cal H}$-free if $G$ does not contain any graph from ${cal H}$ as an induced subgraph. Let $C_s$ be the $s$-vertex cycle. In previous work (MFCS 2019) we examined the effect of bounding the diameter on the complexity of $3$-Colouring for $(C_3,ldots,C_s)$-free graphs and $H$-free graphs where $H$ is some polyad. Here, we prove for certain small values of $s$ that $3$-Colouring is polynomial-time solvable for $C_s$-free graphs of diameter $2$ and $(C_4,C_s)$-free graphs of diameter $2$. In fact, our results hold for the more general problem List $3$-Colouring. We complement these results with some hardness result for diameter $4$.
In this paper we study the family of two-state Totalistic Freezing Cellular Automata (TFCA) defined over the triangular and square grids with von Neumann neighborhoods. We say that a Cellular Automaton is Freezing and Totalistic if the active cells remain unchanged, and the new value of an inactive cell depends only on the sum of its active neighbors. We classify all the Cellular Automata in the class of TFCA, grouping them in five different classes: the Trivial rules, Turing Universal rules,Algebraic rules, Topological rules and Fractal Growing rules. At the same time, we study in this family the Stability problem, consisting in deciding whether an inactive cell becomes active, given an initial configuration.We exploit the properties of the automata in each group to show that: - For Algebraic and Topological Rules the Stability problem is in $text{NC}$. - For Turing Universal rules the Stability problem is $text{P}$-Complete.
A directed odd cycle transversal of a directed graph (digraph) $D$ is a vertex set $S$ that intersects every odd directed cycle of $D$. In the Directed Odd Cycle Transversal (DOCT) problem, the input consists of a digraph $D$ and an integer $k$. The objective is to determine whether there exists a directed odd cycle transversal of $D$ of size at most $k$. In this paper, we settle the parameterized complexity of DOCT when parameterized by the solution size $k$ by showing that DOCT does not admit an algorithm with running time $f(k)n^{O(1)}$ unless FPT = W[1]. On the positive side, we give a factor $2$ fixed parameter tractable (FPT) approximation algorithm for the problem. More precisely, our algorithm takes as input $D$ and $k$, runs in time $2^{O(k^2)}n^{O(1)}$, and either concludes that $D$ does not have a directed odd cycle transversal of size at most $k$, or produces a solution of size at most $2k$. Finally, we provide evidence that there exists $epsilon > 0$ such that DOCT does not admit a factor $(1+epsilon)$ FPT-approximation algorithm.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
