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.

Filter by
Sorted by
Tagged with
3
votes
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 ...
-1
votes
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 ...
0
votes
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 ...
2
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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, ...
0
votes
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 ...
1
vote
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 ...
2
votes
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 ...
0
votes
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 ...
2
votes
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 ...
2
votes
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....
0
votes
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 ...
0
votes
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 ...
1
vote
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: ...
1
vote
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 ...
0
votes
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, ...
0
votes
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',$ ...
2
votes
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 ...
1
vote
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 ...
2
votes
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 ...
1
vote
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 ...
2
votes
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 ...
2
votes
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 ...
0
votes
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 ...
0
votes
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. ...
0
votes
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 ...
1
vote
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 ...
3
votes
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 ...
5
votes
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 ...
1
vote
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 ...
2
votes
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 ...
0
votes
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 (...
4
votes
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, ...
0
votes
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 ...
1
vote
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?
4
votes
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 ...
2
votes
0answers
69 views

Proving NP-completeness of an extension in List Coloring Problem

In the List Coloring Problem (LCP), one is given an undirected graph $G(V,E)$, each vertex $v \in V$ is given a list of permissible colors $L(v) \subseteq \{1,2,\dots,k\}$, we want to find a coloring $...
0
votes
1answer
44 views

Online algorithm for finding of clique of size k

I am trying to write an online algorithm that can detect cliques of size k. I first start out with a set of vertices. For each iteration, I add an edge. The algorithm will detect the first time an ...
2
votes
1answer
26 views

Log-Space Reduction $USTCON\le_L CO-2Col$

I want to show that $USTCON\le_L CO-2Col$ (Log-Space reduction) $USTCON$ The $s-t$ connectivity problem for undirected graphs is called $USTCON$. Input: An undirected graph $G=(V,E)$, $s,t \in V$. ...
2
votes
0answers
49 views

Is there an algorithm to add edges to a DAG to make it strongly connected with minimum cost?

I have a weighted DAG and a function computing the weight of edges that is not connected in the DAG. The weight of u to v equals ...
1
vote
2answers
37 views

What is a polynomial-time algorithm for determining whether two trees, with colored nodes, are isomorphic or not

Provide any polynomial-time algorithm (even a large degree polynomial) which determines whether two rooted colored trees are isomorphic to each-other or not. For example, consider the following two ...
3
votes
0answers
84 views

Minimum clique cover

How can the problem of finding the minimal clique cover be solved using linear/integer programming in a reasonable amount of time? Having an undirected graph, I am trying to partition all its ...
2
votes
1answer
30 views

Showing Maximum Independent Set is $NP-hard$

I've read about Maximum Independent Set problem being both $NP-hard$ and $CoNP-hard$. I know this can be shown using reduction from the corresponding Max-Clique problem, But I'm wondering - Is that ...
1
vote
0answers
59 views

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 ...
2
votes
1answer
31 views

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 ...
2
votes
1answer
27 views

Partitioning a graph with specific constraints

We have an exercise where we need to find the partitions G[V1] and G[V2] of a graph G=(V,E), that fulfill the following constraints. We also know that there exists at least one partition that fulfills ...
1
vote
0answers
13 views

Log-space reduction from $USTCON$

Is it possible to use $USTCON$ log-space decision algorithm in order to show reduction from $USTCON$ to some other decision problem $A$? I mean - the reduction will run $USTCON$ decision algorithm and ...
3
votes
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 <...