# Tagged Questions

23 views

### Splitting a graph into two isomorphic parts

Say a graph $G$ has $2n$ vertices. I'd like to know if I can partition the vertices of $G$ into two parts $X$ and $Y$ such that $G[X]$ is isomorphic to $G[Y]$ ($G[S]$ denotes the subgraph of $G$ ...
25 views

110 views

### 2-colorable belongs to $\mathsf P$

To show that 2-colorable belongs to $\mathsf P$, I have a straightforward mental description in mind that I don't think will be considered as a formal proof. Hence I am interested to know how this ...
138 views

### Algorithm for topological sorting without explicit edge list

Suppose I have a set of vertices $V$ and a function $f(V_1, V_2)$ which given two vertices returns +1 if there is an edge from $V_1$ to $V_2$, -1 if there is an edge from $V_2$ to $V_1$, and 0 ...
76 views

### Homomorphical Equivalence is NP-complete

Two graphs $G,H$ are homomorphically equivalent if there are exists a homomorphism from $G$ to $H$ and a homomorphism from $H$ to $G$. The task is to prove that this decision problem ...
36 views

### is the $d$-dimensional arrangement of Trees still $NP$-hard?

The $d$ dimensional Arrangement Problem for general graphs is known to be $NP$-hard since the special case $d=1$ (OLA) already is (Garey et al, [1976]). For Trees however, the one dimensional case can ...
29 views

### How can i bound the largest edge length of an $n$-point metric in $O(n)$?

For a given metric $d$ on a finite (vertex) set $V$, how can I bound the largest edge length in $O(|V|)$? While (wlog) assuming that the smallest edge length is at least $1$.
255 views

### transform traveling salesman problem into subgraph isomorphism problem

Lets say, I could solve subgraph isomorphism problem in constant time. How could I use this to solve traveling salesman problem? aka... how to transform traveling salesman problem into subgraph ...
72 views

### A way to codify (pre-calculatate) if a one Tree Node is a descendant of another

I have a simple, 1-directional tree representing the veins in a human body. It looks somewhat like this (red dots are nodes, blood flow is always downwards, sorry for my drawing): What I need is a ...
350 views

### Is finding a hamiltonian cycle as hard as determining if one exists?

Is finding a hamiltonian cycle as hard as determining if one exists? Can a hamiltonian cycle be found in polynomial time given an oracle for detecting hamiltonian cycles?
65 views

### show that careful 5COLOR is in NP

We know that 5COLOR problem is NP-complete. careful 5COLOR problem is that: Given a graph G, can we color each vertex with an integer from the set {0,1,2,3,4}, so that for each edge, the colors of ...
2k views

### Algorithm to check whether a graph has no cycles

Let $G=(V,E)$ be an undirected graph. Design an algorithm which decides whether the graph contains a cycle and proove its correctness and determine its complexity in terms of ...
70 views

### Computational complexity of unknotting problem?

The Wikipedia article on the unknotting problem says "a major unresolved challenge is to determine [...] whether the problem lies in the complexity class P". It mentions some work towards this result ...
446 views

### What is the significance of the graph isomorphism problem?

It seems that graph isomorphism is an overwhelmingly interesting problem, particularly computationally. Why is that? What are the (theoretical and practical) implication of the existence of an ...