1
vote
0answers
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$ ...
1
vote
0answers
25 views

Directed Hamiltonian Reduction

The reduction function given by Richard Karp in 'Reducibility among combinatorial problems' for Directed Hamiltonian Cycle $\leq_{p}$ Undirected Hamiltonian Cycle goes as follows : for input $G = ...
1
vote
0answers
29 views

Can cuts of size 2 be detected in linear time in an undirected, unweighted graph?

I'm having trouble finding any literature on the specific subject of 2-edge cut detection. It's not hard to come up with an algorithm that finds all 2-edge cuts in quadratic time, but it's not clear ...
0
votes
1answer
40 views

Switching edges and vertices

I am attempting to convert the problem of finding an edge dominating set into a dominating set. I need a way to change the edges of a graph to the vertices and the vertices of a graph to the edges, ...
0
votes
1answer
33 views

Natural Decision Problem not in PTIME

Are there any natural decision problems which are guaranteed not to be in $\mathsf{PTIME}$? Preferably natural graph problems like $\mathsf{CLIQUE}, \mathsf{VERTEXCOVER}$ etc. (However, they would be ...
0
votes
1answer
28 views

Adding a point to shortest path

If there exists a set of n points in a 2D coordinate system and an n-dimensional vector V ...
2
votes
1answer
107 views

Finding no-self-intersecting path in geometric graphs

Is there a polynomial algorithm to determine whether there exists no-self-intersecting path between given vertices $s$ and $t$ in a geometric graph $G$? Geometric graph is an image of a graph on a ...
0
votes
1answer
58 views

Finding missing two edges in a MST in O(m) time

I need to write an algorithm in O(m) time to find the missing two edges of a minimum spanning tree. I am given a graph G(V,E) where m = |E| and n = |V| as an adjacency list, and T, a subset of G, with ...
0
votes
0answers
57 views

Travelling Salesman Problem with a pen

What's the best way to get a reasonable solution to the asynchronous TSP with a pen and paper?
2
votes
1answer
125 views

Finding the shortest/“most negative” closed directed trail in a weighted digraph with negative weights

I'm using the following definition of a "closed directed trail": a closed directed trail is a directed cycle in a digraph where all edges are distinct. Note that vertices may be repeated, so long as ...
1
vote
0answers
42 views

Fixed Length Cycle Search

I am given a list of $0 \le M \le 2n(n-1) $ edges of a graph. My goal is to find a connected subgraph of this graph such that the degree of every vertex in the subgraph is $n$ that has exactly $n$ ...
2
votes
0answers
86 views

Finding a matching to connect subsets of vertices

I'm studying a graph problem which, strangely, has applications in bioinformatics. I'm not asking for a solution, but rather for advice as to whether something similar to what I do has been studied ...
5
votes
0answers
63 views

Homomorphism for a fixed graph NP-complete?

Let $G$ be the following Graph: We want to decide whether for an input structure $\mathcal{S}$ there exists a homomorphism $S \to G$. We will call this problem $HOM_G$. The task at hand is to show ...
0
votes
0answers
171 views

Its just one point… How do I find it?

Okay so here is the deal... I have a CLOSED convex polyhedron $Ax \le b$ (where $x$ is in $R^n$) and it has i vertices denoted $V_i$ such that $V_i = (x_{i1}, x_{i2}, \ldots, x_{iN})$ where $0 \le ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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$.
2
votes
2answers
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 ...
2
votes
1answer
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 ...
3
votes
1answer
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?
2
votes
2answers
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
8
votes
1answer
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 ...
1
vote
1answer
128 views

Vertex Cover - upper bound

A few definitions: $\mathsf{VC} = \{ (G,k) \mid \text{There exists a vertex cover of size $k$ in $G$}\}$ $\mathsf{VC_{LOG}} = \{ G \mid \text{There exists a vertex cover of size $\leq \log |V|$ in ...
0
votes
1answer
150 views

How do you prove that a game is undecidable?

I'm studying a game that is played on a graph, there are two teams, attackers and defenders. The attackers are attempting to capture the King by occupying all of his neighbours, the defenders are ...
1
vote
1answer
145 views

Sum in tree nodes - algorithm

I've got one very hard problem. Given a tree with nodes with integers. We need to find the largest sum of label values for a set of nodes which does not include any adjacent pair of nodes. ...
3
votes
1answer
73 views

A card game with a long path

I recently played an online card game in which the cards were spread on the table. The goal was for me to pick up as many as possible, subject to the following rule: After picking up the first card, ...
1
vote
1answer
204 views

average distance in a graph

Having a graph of $n$ vertices in Euclidean $m$-dimensional space, is it possible to find average (Euclidean) distance between the vertices in $O(n)$ steps? Is there a deterministic algorithm for ...
0
votes
1answer
401 views

NP-Completeness of Certain Bounded Degree Graphs

I was studying time complexity when it comes to bounded degree graph problems and I was wondering if I can get help with the following two problems. 1) L = set of all (G, k) where G is a graph with ...
6
votes
1answer
2k views

Complexity of counting the number of triangles of a graph

The trivial approach of counting the number of triangles in a simple graph $G$ of order $n$ is to check for every triple $(x,y,z) \in {V(G)\choose 3}$ if $x,y,z$ forms a triangle. This procedure ...
6
votes
1answer
134 views

What is wrong with this decision procedure for 3SAT?

So I came up with a decision procedure for 3SAT which would seem to be completeable in a polynomial amount of time. Naturally, I am assuming it is incorrect, but I don't know where the mistake is. ...
3
votes
1answer
173 views

H-minor free Graph

Recently I cam across a statement which divides graphs into different classes w.r.t. the complexity of problems on them. planar < bounded genus < H-minor free < general graphs My question ...
3
votes
1answer
3k views

An algorithm for arbitrage in currency exchange

I found a really interesting problem and I wanted to hear people's opinion. It has to do with currency exchange rate. If we are give some coins $c_1,c_2,\dots,c_n$ and an array $R$ that keeps the ...
4
votes
1answer
148 views

Vertex arrangement on the unit sphere

The problem is how can I solve a following in polynomial time? There is a graph $G$ with $n$ vertices, and the goal is to find an arrangement of its vertices on an $n$-dimensional unit-sphere so as to ...
2
votes
0answers
157 views

Complexity of finding all edge cuts of a directed graph

I have a problem in which for a certain graph I need to compute the min cut for r times (r can be HUGE). Because each time the edge weights can be different, what i am doing (in practice) is to ...
2
votes
0answers
107 views

Complexity of map coloring

This is a follow up question to this one. I've recently read that for planar maps, it is possible to color these in $O(N^2)$, $N$ being that number of vertices [1]. What are the computational ...
3
votes
1answer
416 views

Find the subset of a graph that has the highest minimum spanning tree benefit and a total edge weight within some threshold

Suppose we have a graph $G$ = ($V$, $E$) where each vertex $v_i \in V$ has a benefit $b_i$ and each edge ($v_i, v_j$) $\in E$ has a weight of $w_{ij}$. I would like to find a subgraph of $G$ that ...
0
votes
2answers
65 views

Oracles and relativization in non-TM settings

I am looking to understand relativization in non-Turing Machine settings. For example, what is the "natural" relativization of Graph Isomorphism to an oracle A? How about HAMPATH? Specifically, ...