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
0 votes
0 answers
3 views

Clever algorithm for ordered compact sub-grouping

I have a set of 2D points (called "seats"), with each having a scalar numerical value attached to it. I have an ordered sequence of groups, each with an integer attributed to it, such that ...
Gouvernathor's user avatar
1 vote
2 answers
42 views

Is this graph grouping problem $\mathsf{NP}$-hard?

Let's introduce the notion of layer: given a simple graph $G$ a layer is a subgraph of $G$ satisfying the following property: If any pair of vertices is connected with an edge, these two vertices ...
rus9384's user avatar
  • 1,696
1 vote
1 answer
20 views

Do edge lists have O(E) storage if default values are used for absent keys?

Ordinarily, edge list representations of graphs take $O(V+E)$ space, where $V$ is the number of vertices and $E$ is the number of edges. For example, consider a graph with 5 nodes and a single edge ...
Ellen Spertus's user avatar
-2 votes
1 answer
33 views

$O(|V||E|)$ algorithm for finding all the cut vertices in a connected graph

Given a connected graph $G = (V, E)$, how to find all the cut vertices in $G$ in $O(|V||E|)$ time? I have considered some algorithms for finding all cut vertices in a connected graph as follows. ...
XYJ's user avatar
  • 7
1 vote
0 answers
27 views

Bron-Kerbosch algorithm for finding cliques missing a few edges?

The Bron-Kerbosch algorithm takes a graph and finds its maximal cliques in an efficient manner (as far as I'm aware, it is $O(3^{n/3})$, where $n$ is the number of vertices). Let $t$ be a positive ...
Alvaro Martinez's user avatar
0 votes
0 answers
25 views

Kruskal's algorithm including an edge

I'm trying to solve the following question in which I have to find a list of critical edges and pseudocritical edges. From my understanding of the problem, critical edges are edges that must be ...
S10000's user avatar
  • 101
4 votes
3 answers
206 views

MSOL and Courcelle's theorem for maximum clique

The Clique Problem is known to be NP-complete but is known to be fixed-parameter-tractable (FPT) if the treewidth of the underlying graph is fixed. The traditional proof is by a dynamic programming ...
Lisa E.'s user avatar
  • 537
1 vote
0 answers
31 views

Chromatic Polynomial of Hamming Graphs

I'm trying to calculate the chromatic polynomial of different Hamming Graphs , especially $H(3, 3) = K_3 \times K_3 \times K_3$, so the Graph Cartesian product of the complete graph with three ...
Dan's user avatar
  • 61
1 vote
1 answer
49 views

Find the transitive closure but with a twist

Situation I have a set of set of elements V, and relations over V: a R b: "a is related to b" (reflexive and symmetrical) a N b: "a is not related to b" (anti-reflexive and ...
aioobe's user avatar
  • 229
2 votes
1 answer
73 views

Proof of NP-hardness: Is the problem of finding the minimum edge-weighted subgraph with at least M pairwise connectivity NP-hard?

Given an undirected graph $G=(V,E)$ with non-negative edge weights $c_{ij}$ for each $(i,j)\in E$ and a positive integer $M$, the problem asks to determine the minimum-weight set of edges $S\subseteq ...
HonestSJ's user avatar
2 votes
0 answers
30 views

Complexity of strong graph realization problem

Given a simple graph $G$, let $k^{th}$ degree of a vertex $v_i\in G$ denote the number of vertices that have distance $k$ from $v$. Notice that first degree is equivalent to degree by standard ...
rus9384's user avatar
  • 1,696
1 vote
1 answer
77 views

MSOL for a vertex-cover enlargement problem

Consider the following problem. Given a graph $G=(V,E)$, and two positive integers $k$ and $\gamma$, decide if there is a set of new edges to be added such that $|E'|\le k$, and any subset $V'\...
Lisa E.'s user avatar
  • 537
0 votes
0 answers
27 views

Adding edges to enlarge vertex cover

Given a graph $G=(V,E)$, and two positive integers $k$ and $\gamma$, decide if there is a set of new edges to be added such that $|E'|=k$, $E' \cap E = \emptyset$ and any subset $V'\subseteq V$ of ...
Lisa E.'s user avatar
  • 537
1 vote
1 answer
43 views

BFS on directed graph with disjointed edges?

There is a graph (directed and unweighted) and a collection of nodes. If I want to find a tree that has all those nodes in it and potentially some other ones as well, would BFS be a good algorithm to ...
Caroline's user avatar
2 votes
1 answer
63 views

Find hierarchical clustering of documents

Given some large set of documents, how would one find a human usable hierarchical clustering to them (ie. place them into a file system such that one can find a document in the minimal time)? My ...
olivarb's user avatar
  • 121
3 votes
1 answer
364 views

Easy/hard NP-hard problems on perfect graphs

Three problems --- Graph coloring, Stable set, and Clique --- are known NP-hard problems (on general graphs) that can be solved in polynomial time, when we know that the given graph is a perfect graph....
Lisa E.'s user avatar
  • 537
0 votes
1 answer
47 views

Convert a Graph to a Good Graph using Maximum Matching in Bipartite Graphs Algorithm

Consider a graph $ G = (V, E) $ where a vertex $ v \in V $ is designated as the center if it is connected to every other vertex $ u \in V $, such that both $ uv $ and $ vu $ are present in $ E $. A ...
Stephen Stone's user avatar
1 vote
2 answers
41 views

Shortest path between two nodes with time-dependent edge weights

I have city traffic data. The roads are represented as a directed graph (a road can have traffic both ways, at most two-lane roads included), vertices being points on a map where two or more road ...
Sgg8's user avatar
  • 111
2 votes
1 answer
29 views

Given a family of 0-1 matrices $M$ find the sum of matrices from $M$ which has minimal rank

Given a family of matrices $M$ with entries in $\mathbb{F}_2$ find the subset $N \subseteq M $ such that the rank of the matrix $$A = \sum_{m \in N}m $$ is minimal. I am wondering if anyone have seen ...
Sander's user avatar
  • 225
1 vote
0 answers
36 views

MSOL framing of max-flow probem

Given a graph $G=(V,E)$ with edge capacities $c_e$ for each $e\in E$, a source $s\in V$ and destination $t\in V$, how do I frame the max-flow problem in MSOL?
Lisa E.'s user avatar
  • 537
-2 votes
1 answer
32 views

Implementation of planar graph max cut

http://comopt.ifi.uni-heidelberg.de/conferences/aussois2009/slides/pardella.pdf Can you simply implement or pseudo code the content of this slide as a whole?
user170509's user avatar
0 votes
1 answer
18 views

True/False: Given an edge $(u,v)$: no path exists from $u$ to $v$ in the residual graph w.r.t a max flow $\iff$ $(u,v)$ crosses some minimum cut

I was asked to show if this is true or false. I believe it is true, but proving it seems difficult. Is it true and how might one show this?
Shay's user avatar
  • 113
2 votes
0 answers
22 views

Tree width given path decomposition

I have a family of graphs whose path decompositions I know. Is it possible to compute the tree-width of these graphs in polynomial time?
Lisa E.'s user avatar
  • 537
3 votes
4 answers
437 views

Undecidable problems in finite graphs

Are there any natural questions in finite graphs (or digraphs) that are undecidable?
Lisa E.'s user avatar
  • 537
2 votes
1 answer
39 views

Why there is no definition of cut vertex in directed graph?

We know cut vertex is an important definition in undirected graph, indicating a vertex which when removed, the number of connected components would increase. And we also have an efficient algorithm ...
27rabbit's user avatar
3 votes
1 answer
47 views

Usage of matrix multiplication for distance products

This is more of a validation question, for the current best known results. On one hand, we have classical matrix multiplication. Its running time is denoted as $n^\omega$. On the other, we have ...
Mařík Savenko's user avatar
0 votes
0 answers
36 views

Graph with an exponential number of paths

I am looking at the language $F$ containing all $G,v_0,v_1$ s.t.: $G$ is undirected $G=(V,E)$ $v_0,v_1\in V$ $|V|=n$ There are $2^n$ paths between $v_0$ and $v_1$ I would like to prove that $F\notin ...
Benicio Agüero's user avatar
5 votes
0 answers
98 views

Minimum cost path connecting exactly K vertices

I came across a situation in real life that maps to this optimization problem: Given a fully connected, undirected, weighted graph with $N \ge K$ vertices, find the simple path connecting exactly $K$ ...
InfiniteSnow's user avatar
1 vote
0 answers
22 views

Global minimum weighted vertext cut for undirected graphs

Given an undirected graph with vertex weights, there any algorithm for finding the global minimum vertex cut that partitions the graph into two components? I can transform the graph to directed one ...
tr244's user avatar
  • 11
0 votes
0 answers
9 views

Managing hashing overlaps (building a heuristic for the edge of a 3x3x3)

I'm trying to build a 3x3x3 solver for a school project. I got inspired by Ben Botto's solver, which you can find here. Such as Ben does with his solver, I'd like to implement Korf's heuristic ...
AlioTheCat's user avatar
0 votes
1 answer
30 views

Finding Common Neighbors between Graph Nodes

I am working on an Application that will generate a graph where each node is either a disease or its symptom. This is an undirected graph, and there is an edge between the disease and its symptoms. ...
Version2's user avatar
1 vote
1 answer
21 views

Pseudo-Traveling Salesman on a colored graph

I have a graph with nodes of various colors and weighted edges between them. I would like to find the least cost path that touches exactly one node of each color. Is this a known problem or reducible ...
Jemmy's user avatar
  • 113
14 votes
3 answers
3k views

Why are search problems assumed to have the structure of "find a path in a graph"?

I have skimmed a few introductions to "search problems", and I have noticed that: Stated informally search problems are defined as "find an object y inside a larger space/object X"...
user56834's user avatar
  • 3,982
5 votes
1 answer
68 views

Algorithm for finding a path factor in a graph

A 1-factor is a perfect matching. A path factor of a graph $G$ is a spanning subgraph, each of whose components is a path with at least two vertices (see the following figure). Since every path with ...
licheng's user avatar
  • 417
1 vote
1 answer
189 views

How to solve a system of XOR equations in a cyclic graph?

I am working on a problem where I need to find values for nodes in a graph of k-nodes. Here an example: The properties are: Each big node (A..H) is connected to at least one blue node Each blue node ...
nowox's user avatar
  • 245
4 votes
2 answers
1k views

Global optimization of state assignments in a directed graph with a tree-based distance cost

I am exploring a general optimization framework to solve problems characterized by the following structure. Any literature references, search terms, or algorithmic strategies would be greatly ...
Rolf Rolles's user avatar
2 votes
1 answer
56 views

Number of graphs that almost contain a $k$-clique

A (loop-free) graph almost contains a $k$-clique if it does not contain a $k$-clique, but adding an edge between any two different vertices that are not already connected by an edge would produce a $k$...
rus9384's user avatar
  • 1,696
0 votes
0 answers
18 views

A specification of all possible languages for representing graphs?

There are a few commonly used markup languages for specifying graph structures. I am interested in discovering alternative graph notations that may be counterintuitive yet more compact or useful in ...
Julius Hamilton's user avatar
1 vote
0 answers
29 views

Minimum expected number of path to cut graph problem

I came up with a problem but was unable to show the hardness of the problem (NP/#P/P-hard). The problem is as follows. Given a directed graph $G=(V, E)$, each edge will have a confidence score $c$. ...
sweet-potato's user avatar
0 votes
1 answer
30 views

breadth first search proof incomplete statement

I'm studying Breadth-First Search (BFS) from the CLRS book and I'm having trouble understanding the proof that each distance from the source node calculated by BFS is the shortest distance from the ...
H.Okan's user avatar
  • 101
3 votes
0 answers
51 views

Algorithm to find minimum number of cuts in DAG based on a rule

I encountered this problem while doing some “graph”ics programming: Take a directed acyclic graph where every vertex is given a non-unique label 1..N You can ‘trim’ the DAG by making a cut that ...
Matt Tytel's user avatar
0 votes
1 answer
28 views

Selecting an Induced Subgraph from a DAG with Specific Conditions

I am working with a Directed Acyclic Graph (DAG), denoted as $G$. The graph has a specific constraint where the out-degree of each vertex in $G$ is at most $2$. My objective is to select an induced ...
Ferran Gonzalez's user avatar
1 vote
1 answer
99 views

Number of unique paths in a grid

Suppose, I have a nxn grid. Now, I want to move from (1,1) to (1,n). How many unique ways are there possible if I can move in left, right, up and down direction. I am trying to solve it using depth ...
Nakib's user avatar
  • 11
-1 votes
1 answer
48 views

Finding negative cycles using the Bellman-Ford algorithm and a source node

I'm exploring the Bellman-Ford algorithm to detect and track negative cycles (a collection of ncycle that we can see in the implementation). I'm wondering if the ...
atos's user avatar
  • 1
1 vote
1 answer
53 views

Graph Coloring Decision Problem Reduction to Prove NP-Complete

I am doing research into NP-Complete problems and more specifically started looking into the Graph Coloring Decision Problem or the k-Coloring problem, as described here: Given a graph $G = (V, E)$ ...
Darien's user avatar
  • 11
0 votes
0 answers
19 views

all pairs shortes path variant [duplicate]

Let $G=(V,E) $ a directed Graph with a coloring function $F:E \to red,blue$ and a weight function $W: E \to R$ I need to find all pairs shortest path s.t. every path visits at least one red edge, or ...
user169819's user avatar
1 vote
1 answer
46 views

Proving that the shortest simple path problem between two vertices 𝑠 and 𝑡 in a graph with given path upperbound be positive is NP-complete

This is the same problem here but with one more condition that the sum of the distance cannot be a negative integer. The full description of the problem is: Is it possible to find a simple path (no ...
Lebecca's user avatar
  • 113
5 votes
1 answer
720 views

What don't I understand in topological sort using DFS?

Wikipedia says: The algorithm loops through each node of the graph, in an arbitrary order, initiating a depth-first search that terminates when it hits any node that has already been visited since ...
porton's user avatar
  • 493
1 vote
2 answers
44 views

Understanding Time Complexity Calculation for Factorial and Exponential Algorithms

I'm trying to wrap my head around how to calculate the time complexity of algorithms that exhibit factorial (𝑛!) or exponential (2^𝑛) growth rates. Specifically, I want to understand the thought ...
Pankaj Verma's user avatar
-1 votes
1 answer
27 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

1
2 3 4 5
99