Questions tagged [graphs]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
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 ...
0
votes
1answer
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?
0
votes
0answers
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 ...
4
votes
0answers
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 ...
2
votes
0answers
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 ...
4
votes
1answer
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: ...
1
vote
0answers
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 ...
0
votes
2answers
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:...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
4
votes
0answers
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 ...
2
votes
0answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
4
votes
0answers
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.
0
votes
1answer
28 views

Structural parametrization for weighted vertex cover

Let $G$ be a graph which is a tree with $\ell$ added edges. I wish to show that VWVC ((Vertex-)Weighted Vertex cover) is FPT with respect to $\ell$. In particular, I'd like an algorithm running in $O(...
1
vote
1answer
53 views

Minimal Spanning Tree vs Minimum Spanning Tree

I got confused about minimal and minimum in context of graph theory. Although, I have understanding that minimal means more than one minimum i.e. none qualifies as actual minimum so we say them ...
1
vote
1answer
23 views

Power of adjacency matrix

Let $G$ be a weighted graph with a weight function $w \longrightarrow \mathbb{R}^{+}$. Let $G'$ denotes the weighted matrix with adjacency matrix $$A_{G'} = \sum_{i=0}^{k} (xA)^{i}$$ where $k$ is ...
1
vote
1answer
20 views

Are there any established methods for generating random graphs/networks that are both planar and meshlike?

There are well-defined methods for generating random graphs / networks that satisfy certain properties, including small-world graphs, scale-free networks, and totally random non-planar graphs. I am ...
3
votes
1answer
60 views

Why do we use DAG rather than trees to represent search space of a search problem?

I saw people use DAGs to represent the search space of a search problems like the travelling salesman problem. Why is this better than the tree representation? Is the reason to save memory space on ...
2
votes
0answers
36 views

Tree Decomposition Construction with Balanced Separations: Why 2/3?

I am working through the book "Parameterized Algorithms" https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf and at the chapter about tree decomposition I am trying to ...
0
votes
1answer
42 views

Vertex cover of minimal graph

I'm looking for algorithm that, for given undirected graph $G=(V,E)$, find graph $G'=(V,E')$ with minimal amount of edges that have same vertex cover as G. I mean, vertices $U$ are vertex cover of $G$ ...
0
votes
0answers
16 views

Walks on Directed graphs

Let G = (V,E) be a directed graph, where V is a finite set of nodes, and E ⊆ V × V be the set of (directed) edges (arcs). In particular, we identify a node as the initial node, and a node as the final ...
2
votes
0answers
142 views

Optimal Item Locations given Traversal Paths

I have a given fully-connected undirected graph associated with (known) distances or alternatively a distance matrix, where the nodes or matrix rows/columns represent locations. Additionally, I have a ...
0
votes
0answers
29 views

Minimum cost bin assignment

I've been trying to solve the below problem the entire day but couldn't come up with a solution. I have the suspicion that it could by solved by a graph algorithm (or maybe some greedy approach?) but ...
3
votes
0answers
39 views

Hardness of an instance of a problem independent of algorithms?

The paper “Where the really hard problems are” (https://www.ijcai.org/Proceedings/91-1/Papers/052.pdf) and others that cite it provide evidence that lots of algorithms for many NP complete problems (...
1
vote
0answers
20 views

How to efficiently flatten a hierarchical state machine?

David Harel's StateCharts introduces hierarchical states and history mechanism, which are really powerful when modeling complex system behaviour. But when doing model based testing we need a "...
1
vote
2answers
157 views

How to prove that the dual of the dual of a connected planar graph $G$ is isomorphic to $G$?

I find in many references the fact that if $G$ is a connected planar graph, then for any embedding, $G^{**} \cong G$. However, all those references either say that this fact is trivial, or give the ...
2
votes
0answers
39 views

Relationship between proof and algorithm of Ramsey's Theorem

The following is a problem statement from "Introduction to Theory of Computation" Chapter 0 Problem 0.14: Let $G$ be a graph. A clique in $G$ is a subgraph in which every two nodes are ...
0
votes
1answer
33 views

Alternatives for finding sources in a DAG

I have a hard time seeing what the alternative approach is in linearizing a directed acyclic graph (DAG). Chapter 3 of Algorithms by Dasgupta et al. states: Property Every dag has at least one source ...
0
votes
1answer
34 views

How to simulate online matching algorithms (implementation)

I was reading about online algorithms and bipartite matching. I found an implementation that works fine on several websites (like geeksforgeeks). For the online version, I found this paper https://...
1
vote
1answer
40 views

Concrete example of an admissible A* heuristic compared to Djisktra

As I understand it, A* is a general form of Djikstra where the selection of the next node to visit can be based on something other than the actual distance. For example, with Djikstra, you'd use a ...
2
votes
2answers
82 views

Find cycles with specific weights in complete graph

(this is a cross-post from mathoverflow) Assume I have an undirected edge-weighted complete graph $G$ of $N$ nodes (every node is connected to every other node, and each edge has an associated weight)....
0
votes
1answer
83 views

Create Shortest Path tree for every node after Floyd Warshall in O(nm)

Right now I am stuck with the problem, how all shortest path trees can be created in O(n*m) given G = (V,E,c) with negative and positive costs without negative cycles and n =|V| m = |E| after ...
6
votes
0answers
81 views

Scheduling tasks on a graph with assistance

This is a follow-up to a question that I recently posted here: Completing tasks on a graph. In that question, I posted the following: Consider a graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, n\}$. ...
0
votes
1answer
31 views

Isn't an improper subset of edges of a cyclic graph, cyclic and thus not a minimum spanning tree?

This is the formal definition of a minimum spanning tree taken from Algorithms by Dasgupta, Papadimitrious and U. Vazirani. Input: An undirected graph $G = (V,E)$; edge weights $w_e$. Output: A tree $...
2
votes
1answer
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. ...
1
vote
2answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
18 views

What is the complexity class of finding vertex cover number of a simple graph?

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 ...
1
vote
2answers
43 views

Selecting connected subgraph that exceeds value c, with least possible weight

Given a graph $G$ where each node has a value $c$ and weight $w$, I want to select a connected subgraph $V^*$, such that, Sum of all values in $V^*$ crosses threshold $t$. Sum of all weights(say $w^*...
1
vote
1answer
13 views

Is it possible to compute the minimum vertex covering set in quasi-polynomial time, by knowing the vertex cover number?

If we know the vertex cover number for a simple graph $G$ denoted by $\tau(G)$, is it possible to find the minimum vertex cover set for $G$‌ in quasi-polynomial time? As I found, we cannot find any ...
1
vote
0answers
81 views

Finding s-t min-cut of undirected graph

Given an undirected graph with non-negative edge weights, and two vertices $s,t$ in the graph. I would like to find the minimal cut such that $s$ and $t$ are on different sides of the cut. For example ...
1
vote
0answers
29 views

Equivalence of two approximation algorithms for min Steiner tree

I learned two approximation algorithms for the min Steiner tree: The first algorithm: 1- Compute the metric closure G' of G. 2- Compute a min spanning tree T' of G' 3- Construct the union U of the ...
0
votes
0answers
82 views

Devise Mont Carlo and Las Vegas Algorithms to Solve Maximum Independent Set

I am trying to devise a Las Vegas algorithm to solve Maximum Independent Set, but I don't know how to start. Also, I want to devise a Mont Carlo algorithm for this problem. I would appreciate any help....
1
vote
1answer
34 views

“Equality” problem in distributed computation

I recently started learning about distributed computation on graphs (not to be confused with parallel computation with threads). I have seen as a side note in a few lower bound proofs, a reference ...
-3
votes
1answer
37 views

Finding a clique in undirected graph is P or NP? (proof) [duplicate]

Finding a clique $C$ in an undirected graph $G= (V, E)$ such that $|C| > |V|/2$ is in P or NP-hard? How can I prove it?
2
votes
1answer
65 views

Generating sparse connected Erdős–Rényi random graphs

Given a random graph $G(n, p)$, where $n$ is the number of nodes and $p$ is the probability of connecting any two edges, it is known that $t = \frac{\ln(n)}{n}$ is a threshold for the connectedness of ...

1
3 4
5
6 7
83