Approximation algorithm to visit all nodes in an undirected, weighted, complete graph, with shortest sum of edge weights

I’m looking for an algorithm that gives a smallest sum of ‘travel time’ within the following constraints:

  • a complete, connected, weighted graph,
  • vertices are defined in 3d euclidean space,
  • relatively low number of vertices (less than 500),
  • no limits on how many times a node may be visited,
  • a fixed starting vertex,
  • no requirement for which vertex to end at.

I’ve looked at minimum spanning tree algorithms, but those could create sub-optimal result, because they optimize for lowest summed edge weight.

I’m suspecting this may be a variant of the travelling salesman problem and thus NP-hard. For our use case however, a good approximation will be good enough.

efficiently find connected components in undirected graph considering transitive equivalence

I have a set of nodes and a function foo(u,v) that can determine whether two nodes are equal. By “equal” I mean transitive equivalence: If 1==2 and 2==3 then 1==3 and also: If 1==2 and 1!=4 then 2!=4

When given a set of nodes I can find all connected components in the graph by passing every possible combination of nodes to foo(u,v) function and building the needed edges. Like this:

import networkx as nx import itertools from matplotlib import pyplot as plt  EQUAL_EDGES = {(1, 2), (1, 3), (4, 5)}   def foo(u, v):     # this function is simplified, in reality it will do a complex calculation to determine whether nodes are equal.     return (u, v) in EQUAL_EDGES   def main():     g = nx.Graph()     g.add_nodes_from(range(1, 5 + 1))     for u, v in itertools.combinations(g.nodes, 2):         are_equal = foo(u, v)         print '{u}{sign}{v}'.format(u=u, v=v, sign='==' if are_equal else '!=')         if are_equal:             g.add_edge(u, v)      conn_comps = nx.connected_components(g)     nx.draw(g, with_labels=True)     return conn_comps   if __name__ == '__main__':     main() 

the problem with this approach is that I get many redundant checks that I would like to avoid:

1==2  # ok 1==3  # ok 1!=4  # ok 1!=5  # ok 2!=3  # redundant check, if 1==2 and 1==3 then 2==3  2!=4  # redundant check, if 1!=4 and 1==2 then 2!=4  2!=5  # redundant check, if 1!=5 and 1==2 then 2!=5 3!=4  # redundant check, if 1!=4 and 1==3 then 3!=4 3!=5  # redundant check, if 1!=5 and 1==3 then 3!=5 4==5  # ok 

I want to avoid running in O(n^2) time complexity. What is the correct way (or maybe an existing function in any python library) to efficiently find all connected components by a custom function?

count all possible paths of length n in an undirected graph with dynamic programming

Given is an infinitely large grid graph. Use dynamic programming to calculate the number of possible paths of a given length n from a given start node, so that fjor every path applies: a) no vertex may be visited twice within it and b) never to go down an edge example of lattice graph for paths of length 2

I found out, that the number of possible paths corresponds to the row sums of the binomial coefficent, times 2 minus the center row, but if n is bigger than 3 other paths emerge which I struggle to include in my dynamic programming solution

Count paths in an undirected tree

I have an undirected tree, suppose I am given a path in that tree from some node u to node v. Now I want the count of rest paths in the tree which share only 1 node with my first path(u to v).

For example for tree with 5 nodes connected as:

1 2

2 3

3 4

3 5

For path ( 1,5) answer will be 1 ie. path (3 ,4)

THere are about 10^5 queries so simple brute force wont work.

I tried dfs to find all the nodes that share the path and then finding all paths in tree and excluding those which have more than 1 node common. But bruteforce takes too long. I am new to graph theory. Please help me proceed with this problem.

divide and conquer algorithm for finding a 3-colored triangle in an undirected graph with the following properties?

In an undirected Graph G=(V,E) the vertices are colored either red, yellow or green. Furthermore there exist a way to partition the graph into two subsets so that |V1|=|V2| or |V1|=|V2|+1 where the following conditions apply: either every vertex of V1 is connected to every vertex of V2 or no Vertex of V1 is connected to a vertex of V2 . This applies recursively to all induced subgraphs of V1 and V2

I can find all triangles in the Graph by multiplying the adjacency matrix with itself three times and step up the nodes corresponding to the non zero entries of the main diagonal. Then I can see if the nodes of the triangle are colored the right way. O(n^~2,8)! But given the unique properties of the graph I want to find a solution using divide and conquer to find the colored triangle. this is an example graph with the given properties. I need to find the bold triangle: this is an example graph with the given properties. I need to find the bold triangle

Blue boxes symbolize the partitions are fully connected, purple boxes mean no connection between the partitions There is no connection between the coloring of nodes and the partitions, also the partitions have to be computed on the fly

NL problem? $CONN$= {$〈G,k〉$ ∶$G$ is undirected graph with at least k connected components}

Consider the following decision problems:

$ CONN$ = {$ 〈G,k〉$ $ G$ is undirected graph with at least $ k$ connected components}
$ E-CONN$ = {$ 〈G,k〉$ $ G$ is undirected graph with exactly $ k$ connected components}

I’d like to show this two problem are in $ NL$ . I Know it’s possible to guess a vertex from each connected component and then verify the connectivity of the component (by guessing paths to other vertices). But how can I verify all guessed vertices are different, when it’s impossible to hold $ k$ vertices on the work tape?