# Questions tagged [graph-theory]

Questions about properties of and problems on graphs, discrete data structures that have the form of nodes connected by edges, that is networks.

1,649 questions
Filter by
Sorted by
Tagged with
0answers
12 views

### Bounded treewidth implies bounded clique-width

We have a graph G of treewidth $\operatorname{tw}(G)\leq k$, for some $k\in\mathbb{N}$. I've seen a claim that that implies that the clique-width of the same graph is at most $k \cdot 2^k$. This ...
0answers
11 views

### How to prove of disprove the following Control Flow Graph theory

See the attached image for some background on Control Flow Graph In a single-entry, single-exit control flow graph (CFG), a node u post-lead v if every path from v to the exit includes 𝑢. Let q be ...
0answers
8 views

### Graph with arboricity a, all verteces are marked active

So I came across this problem that I would like help solving/explaining: We have a graph with arboricity a (can be partitioned to a min of a trees). We run the following algorithm on the graph: - All ...
2answers
60 views

### For what applications of the traveling salesman problem, does visiting each city at most once truely matter?

Traditionally, the traveling salesman problem has you visit a city at least once and at most once. However, if you were an actual traveling salesman, you would want the least cost route to visit each ...
1answer
35 views

### Verifying connectivity of a graph in O(n^2)

I trying to solve the following problem in O(n^2): We have vertices which represents cities and a textfile containing an edge on each line. How many roads do we need to build to make the graph ...
0answers
26 views

### Modifying relaxation for the Bellman-Ford algorithm [on hold]

I'm using the Bellman-Ford algorithm to find the best path in my graph. However, instead of choosing the path with the lower value, I want to choose the path with the highest value. And instead of ...
1answer
75 views
+50

### Merging nodes of a DAG

I would like to merge connected nodes with a specific attribute of a directed acyclic graph. The purpose is to detect max connected clusters of blue nodes and merge them. After each merge operation, ...
0answers
12 views

### How to transform an arbitrary graph into a fixed vector representation?

Actuality I work in computer vision, specifically on a problem known as "scene graph modeling." This problem aims to convert an image $I$ in a graph $G=(V,E)$ where the nodes $V$ represent the objects ...
1answer
193 views

### Hamilton Circuit

The Dirac's theorem states that: "For a Graph G with N vertices, if the degree of each vertex is atleast N/2 then, the Graph has a Hamilton Circuit." Can the same be said if a graph has a Hamilton ...
0answers
49 views

### Matching of two weighted graphs allowing one-to-many mapping

I am looking for a heuristic for a graph matching problem as follows. Given two graphs: $A$ (consisting of nodes $a_i$) and $B$ (consisting of nodes $b_i$). Typically the size of $B$ is larger than ...
0answers
23 views

### Number of compatible trees with an ancestry matrix

Suppose you are given an ancestry matrix $M$ which means that $M[ij] = 1$ iff node $i$ is an ancestor of node $j$. If $M$ represents no cycles (treated as an adjacency matrix) the corresponding graph ...
0answers
40 views

### Similar-path shortest paths

Consider a directed graph with an out-degree of 2 for every vertex, i.e. all vertices have exactly two outgoing edges. This means, considering $n$ as the number of vertices, that the number of edges ...
1answer
42 views

### Is a simple graph connected, if every node has at least one adjacent edge and $|E|\ge |V|-1$?

Let $G=(V,E)$ be an undirected graph without self-loops or parallel edges. Is the following statement true? If $|V|=n, |E|\ge n-1$ and every node has at least one adjacent edge, then $G$ is connected....
1answer
13 views

### efficiently calculate nearest common ancestor in a family tree (each person has two parents)

I'm well aware of ways to efficiently calculate the lowest common ancestor in a tree of nodes which converge to a single root (ie, each node has only one parent). Just iterate back to root for each ...
0answers
32 views

### Directed Acyclic Graph partition into minimum subgraphs with a constraint

I have this problem, not sure there is a name for it, wherein a Directed Acyclic Graph has different colored nodes. The idea is to partition it into minimum number of subgraphs with the following 2 ...
0answers
30 views

### Ordering vertices of graph based on specific vertex-transitivity

Given any complete directed weighted graph $G$ with $n$ vertices and matrix of non-unique weights $W$, find a weak ordering $T(G, W)$ on the vertices of the graph satisfying the following conditions: ...
0answers
38 views

### Generate Hamiltonian path with obstacles

I want to make some Hamiltonian paths with obstacles in a grid that are hard to find It's for a game that I want to create, which consists of passing from all the cases of the grid without passing ...
0answers
14 views

### Looking for a similar graph algorithm to generate a graph given the edges a path took

I'm looking for some help on algorithms that may help generate a directed non-cyclic graph from a list of leaf nodes and the incomplete set of edge nodes taken to get to the leaf node. For example, ...
0answers
6 views

### maximize Steiner vertices in graphs of diameter 3

Let $G=(V, E)$ be a simple connected graph of diameter 3 and $T \subseteq V$ be a set of terminal vertices in $G$. For any $T' \subseteq T$, $(V', E')$ denotes a subgraph of $G$ containing $T',$ ...
1answer
44 views

### Number of ways painting graph in two colors, such that two nodes of same color are linked by edge

We are given undirected graph of $N$ nodes and $M$ edges, we want to count the number of possible ways to paint this graph in $2$ colors such that for each two nodes having the same color, there must ...
1answer
35 views

### Complexity of K-Colorful Coloring Problem for a Hypergraph

I searched a lot trying to find a reference for the complexity of K-colorful coloring problem for a hypergraph but I cannot find it. Please if anyone has a reference for the complexity of the problem ...
1answer
62 views

### Steiner tree problem in graphs of diameter 3

I have an unweighted undirected graph $G(V, E)$ of diameter 3 and a subset $T\subseteq V$ of these vertices. I want to find the minimum tree $(V', E')$ that contains all vertices in $T$, minimizing ...
1answer
23 views

### Selecting the right partition in NAUTY

Graph isomorphism solver Nauty has two main procedures, individualization and refinement, to get to a discrete partition. During refinement procedure, we take some cell of the current partition and ...
1answer
23 views

### Algorithm to compute partitions of a graph in N cliques

does anyone know of an efficient algorithm to compute the partition of a graph in N cliques? Notice that N is the number of the cliques and not the size of them. I have heard of the 2 cliques ...
1answer
46 views

### is it always true that the depth of BFS is $\leq$ DFS?

I have a simple theoretical question in very basic algorithms, as the title mentions, is it always true that the depth of BFS is $\leq$ DFS? From what I understand, the tricky part here is the ...
0answers
33 views

### Graphs - Shortest Path Algorithms - Summary

Are following statements valid? Shortest Path in an undirected graph can be found using BFS. Is DFS an option here? If DFS is not an option, why. Dijkstra's SPT works if there are no negative ...
0answers
17 views

### How to guarantee the minimum path removed from priority queue is the shortest path after all infinite vertices relaxed

I readed the proof of Dijkstra's algorithm in "CLRS"，and the code in Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. Figure 24.7 in CLRS proofs the correctness of Dijkstra's algorithm. ...
1answer
31 views

### negative weight cycle detection using dijkstra's algorithm

Can we store a struct in place of vertex. struct { int v, update_count; } run dijkstra's algorithm and whenever a node is updated we will increase update_count value. If update_count value is greater ...
0answers
10 views

### bipartite d regular expender explicit construction

I am looking for an explicit (and simple) construction of a d regular bi bipartite graph which is an expander. I searched the web and didn't find any sufficient answer. The only explicit graph I did ...
0answers
42 views

### Determine if a graph has exactly 1 cycle using a SAT solver

I have a connected undirected graph whose edges are either enabled or disabled. I want to create a set of clauses that are SAT iff all enabled edges are part of a single loop. If I assert that each ...
1answer
276 views

### SAT algorithm for determining if a graph is disjoint

What are some good algorithms to have a SAT (CNF) solver determine if a given graph is fully-connected or disjoint? The best one I can think of is this: Number the nodes 1..N, where N is the number ...
1answer
27 views

### Finding rainbow cycle in digraph colored with $\log n$ colors [closed]

Given a directed graph with $n$ vertices, and $k=\log n$, we are given a coloring of the vertices with $k$ colors. Describe an algorithm determining if there exists a simple cycle in $G$ of ...
1answer
42 views

### How to merge a lot of trees into one single graph?

I have a few different trees, which resemble what the AST that compilers often deal with. For example: tree 1 ( (a, b), (c, d) ) Imagine that each tree split represents the function "add", then ...
0answers
9 views

### Is Edmonds' Matroid partitioning algorithm optimal w.r.t lexicographical order?

We all know that, given a matroid $(E, \mathcal{I})$, Edmonds' Matroid partitioning algorithm will result in a tuple of $E$-covering, pairwise-disjoint independent sets $(I_1, ..., I_k)$ with optimal (...
1answer
33 views

### Normal colorings of cubic graphs to SAT

This problem is related to ”Normal coloring of cubic graphs (part 1) - a previous post. We repeat the definitions, slightly modified so as to get to the point (we define normal edge 5 colorability, ...
0answers
27 views

### Which computational framework lies behind the Chinese “Social Credit System”?

BACKGROUND The Social Credit System is a data-driven reputation system which draws on several sources to label various entities, namely businesses and individual citizens, with a trustworthiness ...
2answers
37 views

### For every undirected unweighted graph is every MST also a SPT

I have a feeling this might be wrong an I'm looking for a counter example, however, I couldn't find one yet.. can anyone guide me in the right direction?
1answer
35 views

### Normal colorings of cubic graphs (part 1)

Edit 2019 June 27 Question 3 is new ... Definition A normal $k$-coloring of a cubic graph (3-regular graph) is a proper coloring of the edges with $k$ colors such that each edge an its adjacent ...
0answers
69 views

0answers
17 views

### Random paths from one point to another going through all the cells of a square grid

I am looking for a very specific algorithm, so I think it doesn't exist yet. I would be satisfied if anyone was able to give me some hints to develop it. My problem is about a square grid of size <...