# Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.

4,146 questions
Filter by
Sorted by
Tagged with
12 views

### How to use XML format of graphs in Graph neural network?

I have manually labeled directed graphs that I need a GNN to train on and then predict when given a new directed graph, what the labels for the vertexes in the graph should be. My graphs are in the ...
75 views

### Do a pair of parallel edges form a cycle in a graph

Whenever there is a back edge, a cycle is detected. Then, do a pair of parallel edges form a cycle in a graph? If no, why it is not a back edge?
20 views

### Practical ml model explainability with graphs and prolog

How practical are logic engines for proof paths combined with knowledge graphs in Providing reasonable explainability for ML models trained using GNNs? Adding more context. there is a history of ...
34 views

### Planarity testing given an embedding

I am given a connected graph $G$ with some embedding. I want to find a non-deterministic algorithm running in $O(n)$ time to decide whether $G$ with that embedding is a plane graph (i.e, can be drawn ...
51 views

### 3-cycle cover decision problem for directed graphs: best known algorithm and maximum size of tractable problems

I know that the 3-cycle cover decision problem for directed graphs (3-DCC), defined as finding whether a directed graph has a disjoint vertex cycle cover in which every cycle has at least 3 edges, is ...
127 views

### Hamiltonian path greedy and anti-greedy algorithms

I had this question on a problem set recently, but I wasn't sure how to solve it. Given a complete weighted undirected graph $G$, here are two "algorithms" to find a Hamiltonian path: ...
28 views

### Cyclic finite scheduling algorithm

I have a scheduling problem with the following specifications: A single machine is used. $n$ jobs $\mathbb{J} = \{J_1,...,J_n\}$ are available from the start $t = 0$. Each job can be executed several ...
37 views

### Shortest path algorithm where the path can travel through at most 2 vertices in X ⊂ V

I am trying to model a problem to enable me to use Dijkstra's Shortest Path algorithm. Given are a set of vertices V, and a set of vertices X ⊂ V. Between these vertices are given a set of edges where:...
46 views

### Reducing infinite paths of a transition system to its set of sets of states

Consider a transition system defined by $\langle S,T \rangle$, where $S$ is a set of states and $T \subseteq S \times S$ is a set of transitions, where $T$ is total, i.e. for every state $s$ there is ...
61 views

### For any DFS of a directed graph, is the strongly connected component containing the vertex with the lowest post order number also contains the sink?

I am stumped on the following question: For any depth first search of a directed graph, is it true that the strongly connected component containing the vertex with the lowest post order number also ...
33 views

### Polynomial time algorithm to find an induced cycle in non-chordal graph

Let $G=(V,E),n=|V|,m=|E|$ be a graph. There exists an algorithm with time complexity $O(n+m)$ to test if given graph $G$ is chordal. If I know the graph is NOT chordal, is there a algorithm to find ...
76 views

### Approximation Algorithms via Unit Disk Graph Embeddings

A unit disk graph is defined by a collection of $n$ vertices corresponding to $n$ points on the plane, with an edge between any two vertices whose distance is at most $r$. Some $NP$-hard problems ...
73 views

### How to quickly determine whether a poset is a lattice?

Recently I encountered an interesting problem while studying discrete mathematics: Give the pseudo code to judge whether a poset $(S,\preceq)$ is a lattice, and analyze the time complexity of the ...
88 views

### Dynamic programming for graph splitting

I have a directed graph which has edges between every vertices $i$ and $j$ such that $i < j$ and the edge is from i->j and every vertex needs to be visited. I need to divide the graph into two ...
21 views

### Probability of arising of simple graph in configuration model

I am studying a configuration model building $d$-regular graphs and reading the following article: The expansion of random regular graphs by David Ellis. I am stuck on the following step: Each simple ...
23 views

### Can the Bellman-Ford Algorithm be used to find the longest path in an undirected graph through first negating the weight of all the edges? [duplicate]

I understand that the Bellman-Ford Algorithm can solve the single-source shortest-paths problem. However, can it also be used to determine the longest path in an undirected, graph through first ...
80 views

### If a graph has $15$ vertices, one with degree $8$, $6$ with degree $6$, $8$ with degree $4$, is it a planar graph?

The question is as above. I want to prove that there exists a $K_5$ as a subgraph, so this graph is not a planar graph. But I failed. If you can help me, I will be very appreciative.
28 views

106 views

### Graph add at most 2 edges to make all graph nodes degree even

Given an undirected graph that is represented by its adjacency matrix, return whether or not is it possible to add no more than two edges to this graph in order to make all the degrees of nodes even. ...
48 views

### Maximum matching for general graph

I am studying the maximum matching problem and I was trying to understand why the classical augmenting path algorithm does not work for the general graph (i.e. for non bipartite graph) and you must ...
44 views

### Finding shortest path for DAG using dynamic programming vs topological sort?

Why is it that when I read about finding the shortest path for a DAG I usually just hear about topological sort? Why not use dynamic programming where the shortest path to a vertex is simply the ...
Suppose we have a simple graph $G$. We know that finding the minimum vertex covering set for $G$ is in the NP-hard class. But, what about the complexity class of finding the size of the set, i.e., the ...