Skip to main content

Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.

Filter by
Sorted by
Tagged with
-1 votes
0 answers
13 views

Show that it is Np-hard to determine whether a given graph has the crossing number k

I want to prove that this problem to find whether the crossing number of any given graph is K or not, is NP-Hard. I don't know how to do this. Can someone help me with this ?
Virar's user avatar
  • 1
0 votes
1 answer
11 views

Why is the Time Complexity of DFS Algorithm O(|V| + |E|) instead of O(|E|)?

I'm trying to understand time complexity in the context of graph algorithms, especially Depth-First Search (DFS). As far as I understand, time complexity indicates how the execution time of an ...
Pankaj Verma's user avatar
0 votes
1 answer
28 views

Optimizing Set Composition with String Edit Distance Constraints

A set $S$ consisting of strings of length $L$ using $N$ types of characters is such that the edit distance between any two strings is at least $d$. Among such sets $S$, I would like to find one with ...
Kazune Takahashi's user avatar
0 votes
0 answers
18 views

How can i allocate troops so as to maximize the number of bases conquered without going over a maximum time?

I have a set of bases which are connected by directed edges illustrating which bases can be attacked from any particular base. Bases have a health pool (ex: 1,000,...
paullc's user avatar
  • 1
2 votes
2 answers
64 views

Max cut 2-approximation algorithm

Given an undirected unweighted graph $G$, we'll define $f(G)$ as the maximum number of edges crossing a cut in $G$. Find a (polynomial) 2-approximation for $f$. I know about the probabilistic method, ...
sadcat_1's user avatar
  • 239
0 votes
0 answers
15 views

Are there any programs/libraries that can generate all acyclic digraphs on n vertices?

Are there any programs/libraries that can generate all unlabeled acyclic digraphs on n vertices? I'm thinking of something like Nauty's geng; but for DAGs. (I have ...
Zack's user avatar
  • 121
1 vote
0 answers
22 views

Efficiently generating the smallest directed graph subject to degree constraints that yields a requested flow

Given two (small-ish) sequences $I$ and $O$ of rational numbers with $\sum_{x \in I}x=\sum_{y \in O}y$, generate a directed graph $G = (V,E)$ with minimum $|V|$ that respects the following: $|I|$ ...
MarioVX's user avatar
  • 11
1 vote
0 answers
24 views

Minimum number of vertices in a tree with pathwidth $h$?

Let $\mathcal{T}_h$ be the set of trees with pathwidth $h$. What is the minimum,$|V(T)|$ over all $T \in \mathcal{T}_h$. I'm guessing this is a fairly easy question. We know that a complete binary ...
Harry Vinall-Smeeth's user avatar
0 votes
0 answers
9 views

Shortest path in a graph where edge weights can vary dynamically based on the path taken [duplicate]

I have a directed acyclic graph whith negative edges where edge weights can vary dynamically based on the path taken. ...
user1552545's user avatar
2 votes
1 answer
49 views

DFS (Depth-first search) vs BFS (Breadth-first search) Space Optimizations

Problem I am currently digging deep into some optimizations on the classical iterative approaches to both DFS and BFS algorithms. The material I'm currently using at my University presents both ...
Michel H's user avatar
  • 123
1 vote
1 answer
19 views

Algorithm for creating an esports season schedule

I run an esports league for my Boys & Girls Club and others that want to participate. I'm trying to find a way to take information about when different teams are available to compete and use that ...
malsatori's user avatar
0 votes
0 answers
16 views

Kernelization For Odd Cycle Transversal Problem on Perfect Graphs

This problem appears as exercise 2.33 in https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf (page 48). A perfect graph $G$ is bipartite if and only if it contains no triangle graphs. ...
Yavuz Bozkurt's user avatar
0 votes
1 answer
27 views

Will CSR format store the all 0 column?

In the matrix(3 rows and 7 columns) below with 4 all zero columns 0 4 0 0 0 0 0 2 1 0 0 0 0 0 0 0 3 0 0 0 0 The CSR format of storage is : row_ptr: [0, 1, 3, 4] col_ind: [0, 0, 1, 2] values: [4, 2, ...
san zhang's user avatar
0 votes
1 answer
32 views

Is this depth search correct (DFS) Shouldn't one act according to the LIFO principle?

Shouldn't we actually continue with C after A, thought a depth search, follows the LIFO principle, isn't C the last node added in this case and shouldn't we expand C before B?
test's user avatar
  • 1
6 votes
1 answer
889 views

Can every spanning tree result from a depth-first search?

A graph can have multiple spanning trees and the spanning tree resulting from a depth-first search depends on the order in which edges are processed. Can every possible spanning tree of a given graph ...
schuelermine's user avatar
0 votes
1 answer
16 views

Assigning classes to nodes in a graph to minimise intra-class distance

I have an complete undirected graph with n vertices, and the edge $(u,v)$ has weight $d(u,v)$ for some distance function. I also have $m<n$ elements, each of which belongs to a category $\{1...i\}...
minnie's user avatar
  • 1
1 vote
0 answers
11 views

Find minimum number of nodes to be removed so that each node has atmost one adjacent node in a graph (not necessarily a DAG)

I have directed graph G (not necessarily a DAG). I need to formulate an algorithm returning the minimum number of nodes that need to be removed, such that each node has atmost one adjacent node. Any ...
BruceWayne's user avatar
3 votes
1 answer
53 views

graph theory single bar vs double bar size notation

A follow-up on https://stackoverflow.com/questions/15037679/what-do-the-absolute-value-bars-mean-in-graph-theory What is the difference between single bar $|G|$ and double bar $||G||$ notation (both ...
J. Schmidt's user avatar
3 votes
1 answer
342 views

Is determining the existence of a Hamiltonian cycle in a chordal graph NP-hard?

The Hamiltonian cycle problem asks if a given graph contains a Hamiltonian cycle. The Hamiltonian cycle problem belongs to the class of NP-complete problems. However, for some special classes of ...
licheng's user avatar
  • 365
1 vote
1 answer
35 views

Weisfeiler-Leman Algorithm

We know that the Weisfeiler-Leman Algorithm will not always distinguish graphs that are not isomorphic but if two graphs are isomorphic are we guaranteed to get a certificate?
IsoCurious's user avatar
0 votes
1 answer
34 views

Coding the labyrinth solver

The question mathematically has been answered here: https://math.stackexchange.com/questions/4886084/guaranteed-graph-labyrinth-solving-sequence/4887473#4887473 To summarize, in an unknown strongly ...
user555076's user avatar
0 votes
1 answer
31 views

An "edge-spanning-tree" of minimum height

Given any connected undirected graph, we can convert it into a tree by "detaching" some edges from one of their endpoints. For example, consider the graph with the following edges: $$ (1) ~~~...
Erel Segal-Halevi's user avatar
2 votes
1 answer
75 views

Graph labyrinth solving sequence

Starting from a vertex of an unknown, finite, strongly connected directed graph, we want to 'get out' (reach the vertex of the labyrinth called 'end'). Each vertex has two exits (edge which goes from ...
user555076's user avatar
3 votes
1 answer
71 views

Maximum Vertex Set With a Minimum Pairwise Distance Requirement in Directed Acyclic Graphs

Let $G=(V,E)$ be an unweighted directed acyclic graph with a set $V$ of vertices and a set $E$ of edges. The all-pairs shortest path problem can be solved efficiently using the Floyd-Warshall ...
Daniel García's user avatar
1 vote
1 answer
72 views

How to find largest caterpillar in a tree

A caterpillar is a subgraph which consists of a path with at most four leaves (legs) attached to each node (but a node can also have no leaves). This is not the same as finding the longest path, ...
Stephen's user avatar
  • 11
0 votes
1 answer
26 views

How to find smallest n so that all walks of length greater or equal to n include set of paths

If we have a finite (directed) graph G, and a set of walks P in G. And assume that there exists an n so that all walks of lengths greater than n have at least one p in P as subpath, how would we find ...
hmmmmmmm's user avatar
  • 101
1 vote
1 answer
27 views

Proving that Breadth-First Search (BFS) results in a bipartition of a tree

In my studies of discrete mathematics, I've learned that a tree graph is inherently bipartite. I'm interested in finding an algorithmic approach to determine its bipartition. It seems to me that ...
Ferran Gonzalez's user avatar
5 votes
3 answers
1k views

Seeking a Polynomial Time Algorithm for Balanced Weight Assignment to Nodes in a Tree

I have a tree, $T$, with $n$ nodes. My goal is to assign a non-zero weight to each node such that the following condition is met: Upon removing any arbitrary node, the total weight of nodes in each ...
Ferran Gonzalez's user avatar
1 vote
1 answer
39 views

Path Through Graph That Minimizes Node Attributes

I have a directed graph (DAG) containing many nodes, all with various attributes (node attributes not edge attributes). I have a single target (finish) node and a set of source (start) nodes. I want ...
laurence 's user avatar
1 vote
1 answer
39 views

Shortest paths in $k$-partite DAG

Let $D(V, A)$ be a $k$-partite DAG; $P = \{ p_k : 1 \leqslant k \leqslant |P| \}$ such that $p_k \cap p_l = \emptyset$, $\forall k,l : k \neq l$, and $\bigcup_{1 \leqslant k \leqslant |P|} p_k = V$ ...
Matheus Diógenes Andrade's user avatar
1 vote
0 answers
21 views

Resolving distance constraints in 2D

I am currently writing a tool that will be used in an industrial process to place components with physical requirements. It boils down to the following: I have a set of points (typically, a few ...
Yoric's user avatar
  • 111
0 votes
1 answer
94 views

DFS to assign guards to nodes in a tree structure

Consider a uniquely designed museum where rooms are arranged in a tree structure. Each room can have up to two child rooms connected by a path. The task is to develop an algorithm to place a minimum ...
mark's user avatar
  • 67
2 votes
2 answers
98 views

No Neighbor Vertex Cover

Let $G=(V,E)$ be an undirected connected graph with a set of vertices $|V|$ and a set of edges $|E|$. A set cover $D$ satisfies $D \subseteq V$ and $uv \in E \implies u \in D \lor v \in D$. A variant ...
Daniel García's user avatar
0 votes
1 answer
59 views

P=NP? A reduction of CNF boolean satisfiability to the circulation problem in an undirected graph

The picture below shows how to reduce the Boolean Satisfiability problem in CNF to the circulation problem in undirected graph (see here). As you can see, a[i] are ...
Serge Rogatch's user avatar
0 votes
0 answers
15 views

Collapsing loops in a control-flow graph

Let's say we are given some CFG, maybe in SSA-form, and we want to "collapse" each top-level loop into s single node, whose successors would be all exit blocks of the original loop. So we ...
return true's user avatar
0 votes
1 answer
27 views

Find a negative cycle linearly?

In a directed graph, if you find scc (strongly connected components), then for each negative edge, if its 2 vertices are in the same scc and that scc has size > 1, then there is a negative cycle ...
Lorenzo Tinfena's user avatar
7 votes
3 answers
142 views

Finding a set of edges $E$ such that every $s$-$t$-path contains at least 2 edges from $E$

Given an undirected graph $G$ and two vertices $s$ and $t$, i want to find a minimum set of edges $E$ in $G$ such that every (simple) $s$-$t$-path contains at least 2 edges from $E$. Is this problem ...
tgnome's user avatar
  • 153
4 votes
1 answer
198 views

Tseitin formula on 2-connected graph

How can we prove that for $\\\\$ every $\\\\$ 2-connected graph G with an odd number of vertices, the unsatisfiable Tseitin formula for it is minimally unsatisfiable, that is, if we remove even a ...
Brett's user avatar
  • 1
8 votes
0 answers
96 views

Problem of constructing binary sequence with least possible 1s under given constraint

You are given a binary pattern p. Problem is to construct a binary sequence of length n such that by sliding p over our sequence there is always at least one position where two 1s align (one in the ...
Relja Šegvić's user avatar
0 votes
0 answers
21 views

Optimal way to send data across an unknown network

The problem goes as follows: Given a graph G with a set of Vertices V, each having some capacity u, and edges between them E (not fully-connected) associated with some cost c (cost to send a unit of ...
EnderNicky's user avatar
-1 votes
1 answer
68 views

Examples of algorithms best their class that require cyclical data structures

I remember that the Roc Lang website claimed that their choice to forbid any form of cyclic data structures prohibited their customer to implement some of the best in their class algorithms, id est ...
Delfin's user avatar
  • 99
0 votes
2 answers
104 views

Distinct edge weights assumption in second best MST algorithms only replacing an edge in MST

In a CP-algorithms wiki Second Best Minimum Spanning Tree - Using Kruskal and Lowest Common Ancestor: Let  $T$  be the Minimum Spanning Tree of a graph $G$ . It can be observed, that the second best ...
Kenneth Kho's user avatar
2 votes
1 answer
41 views

Why does Hopcroft-Karp only work on bipartite graphs?

I have a simple question which I cannot answer, and it relates to this question. What I cannot answer is this: Why does a graph with bidirectional edges destroy the "bipartiteness" of the ...
Joff's user avatar
  • 155
5 votes
1 answer
51 views

NP hardness of adaption of the graph bandwidth problem

Is the following adaptation of the graph bandwidth problem NP hard? If so, which problem could a reduction use? Given: Graph $G = (V , E )$ with $L\colon E\to \mathbb N$. Question: Is there a $f\...
CubeArrow's user avatar
1 vote
1 answer
62 views

Find all the induced paths with a start vertex

Let $G$ be a graph and let $v$ be a vertex. Is there a polynomial algorithm for the following operation? Operation. Find all the induced paths in $G$ with first vertex $v$. Background This problem is ...
licheng's user avatar
  • 365
1 vote
0 answers
38 views

Is there a proof for camerinis algorithm for finding a minimum bottleneck spanning tree?

Does someone know a proof for Camerinis Algorithm for finding a minimum bottleneck spanning tree? To my knowledge its the only algorithm that performs in linear time to solve this task but I cant find ...
identicon's user avatar
0 votes
1 answer
30 views

Lightest Paths Tree that is 10 times heavier than an MST of the same graph

Something I was asked to solve and tried to come up with a formula or some method to solve it after I did and couldn't. Given is a graph G=(V,E) that is undirected and weighted. Say we want to find ...
Eddie's user avatar
  • 1
1 vote
1 answer
72 views

Disconnection of a directed and weighted graph

Let $G = (V, E)$ be a directed weighted graph such that all the weights on the edges are positive. In $G$, we have two nodes, $v$ and $u$, that have a path from $v$ to $u$. The question asks to find a ...
Daniel's user avatar
  • 47
0 votes
0 answers
60 views

Find an independent set in which the cumulative sum of weights is maximized

I have a weighted undirected graph G=(V,E,W), I want to find an independent set S of V, such ...
Farah Mind's user avatar
2 votes
1 answer
32 views

How does additional assumptions increase approximation factor?

I am studying the greedy algorithm for maximal weighted matching in arbitrary graphs. I have proven that this algorithm has approximation factor $\frac{1}{2}$. Assume now that the weights in the graph ...
mNugget's user avatar
  • 123

1
2 3 4 5
99