Questions tagged [graphs]

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

565 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
26
votes
0answers
738 views

Graph problem known to be $NP$-complete only under Cook reduction

The theory of NP-completeness was initially built on Cook (polynomial-time Turing) reductions. Later, Karp introduced polynomial-time many-to-one reductions. A Cook reduction is more powerful than a ...
21
votes
0answers
452 views

Approximate minimum-weighted tree decomposition on complete graphs

Say I have a weighted undirected complete graph $G = (V, E)$. Each edge $e = (u, v, w)$ is assigned with a positive weight $w$. I want to calculate the minimum-weighted $(d, h)$-tree-decomposition. By ...
18
votes
1answer
920 views

Could min cut be easier than network flow?

Thanks to the max-flow min-cut theorem, we know that we can use any algorithm to compute a maximum flow in a network graph to compute a $(s,t)$-min-cut. Therefore, the complexity of computing a ...
13
votes
1answer
328 views

Steps that guarantee exiting a maze

Given a 2-dimensional maze where you can give 4 commands "move up/down/right/left". Knowing the maze but not where the person is, how to find the minimum sequence of commands that guarantees exiting ...
11
votes
0answers
288 views

How fast can we compute the size of maximum matching in an unweighted bipartite graph?

Is there a way to compute the size of a maximum matching in an unweighted bipartite graph more efficiently (e.g. faster) than computing a maximum matching? It is a long shot but it is often an ...
11
votes
0answers
246 views

Change in the distances in a graph after removal of a node

Given an undirected unweighted graph $G=(V,E)$ and a node $s \in V$, we are looking for a vector $\operatorname{diff}[]$, such that, $$\operatorname{diff}[v] = \sum_{u \in V \setminus \{v\}}{(d^{G \...
10
votes
0answers
206 views

Minimum edge deletion partitioning of a planar graph

I'm interested in the time complexity of the following problem: Given an undirected planar graph $G=(V,E)$ and a weight function $w:E \rightarrow \mathbb{Z}$ (so weights can be negative, too), color ...
9
votes
0answers
130 views

Covering a complete graph with n copies of an arbitrary graph: NP-complete?

Given a complete graph $G$, an arbitrary graph $H$, and a positive integer $n$, are there subgraphs $A_1,\dots,A_n$ of $G$ (not necessarily disjoint) such that their union is $G$, and each of them ...
8
votes
0answers
123 views

Problem with manipulation of colored graph

Consider a finite set of colors and a given an unweighted graph with the following properties: 1) Graph is connected. 2) All vertices of the graph has a color in the given set of colors. 3) No two ...
8
votes
0answers
142 views

What is the best algorithm to compute ALL homomorphisms between two rooted labeled trees?

Lets consider two node-labeled rooted trees Q and D. According to wikipedia definition ( https://en.wikipedia.org/wiki/Tree_homomorphism ) a mapping m from the nodes of Q to the nodes of D is a tree ...
8
votes
0answers
151 views

Practical algorithms for the disjoint paths problem

Given an undirected graph $G$ and two pairs of vertices $(s_1, t_1), (s_2, t_2)$, the disjoint paths problem (DPP) asks for two vertex-disjoint paths, one from $s_1$ to $t_1$ and the other from $...
8
votes
0answers
178 views

Optimizing order of graph reduction to minimize memory usage

Having extracted the data-flow in some rather large programs as directed, acyclic graphs, I'd now like to optimize the order of evaluation to minimze the maximum amount of memory used. That is, given ...
7
votes
0answers
102 views

Constructing a connected graph with given degree sequence

I am interested in constructing simple connected graphs where each vertex has a fixed number of edges (degree) ahead of time. I had originally assume I could use some modification of the Havel-Hakimi ...
7
votes
0answers
181 views

Computing the “at least k friends in common” graph

Suppose we have the graph of a social network with symmetric connections (e.g. Facebook or LinkedIn). Suppose we would like to find all pairs of people who have at least k friends in common, in order ...
7
votes
1answer
249 views

Building cycle in rectangle

I have to build a cycle with fixed length $n$ that includes exactly $k$ corners inside $w$ x $h$ rectangle. For example: $w = 5\\h=3$ $n = 12\\k = 6$ I have already found out that I need at least $...
6
votes
0answers
343 views

Trying to find a human-usable method to figure out optimal round 1 openings for this game

I'm trying to figure out optimal round 1 openings for this game: http://generals.io/. For the purposes of this question, I've simplified some of the rules and mechanics of the game, and I assume that ...
6
votes
0answers
56 views

Is there any field that studies the equivalent of cellular automata, but for arbitrary graphs rather than 1D cells?

A cellular automaton consists of a sequence of cells, each with a state, and a globally symmetric transition rule based on the neighbors of a cell. They can be interpreted as graphs where each cell is ...
6
votes
0answers
109 views

Guided mining of common substructures in large set of graphs

Disclaimer: I'm not a CS so I basically have no idea what I'm talking about I have a large (>1000) set of directed acyclic graphs with a large (>1000) set of vertices each; the vertices are labeled. ...
6
votes
0answers
482 views

Parallel algorithm to find if a set of nodes is on an elememtry cycle in a directed/undirected graph

I'm looking to find / develop a simple parallel algorithm that does this: Input: vs: list of root vertices max_length: max cycle length max_dist: max distance to root Variants one variant of ...
6
votes
0answers
965 views

Suurballe's Algorithm: Proof of Correctness

I was reading about Suurballe's algorithm on Wikipedia, for the shortest edge-disjoint paths problem, i.e. given nodes $s$ and $t$ finding a pair of paths between these nodes, whose accumulated weight ...
6
votes
0answers
317 views

Are there Some Pairs Shortest Paths Algorithms?

I know that there are All Pairs Shortest Paths algorithms. But I am not sure if they are effective if I am trying to solve the Pairs-Shortest-Path problem for a subset of my vertexes. The properties ...
6
votes
0answers
1k views

Stopping condition for goal-directed bidirectional search for shortest path

So I have a graph and need to find shortest path between two points in it. I need1 to do it it using bidirectional search. The bidirectional search should be goal-directed, i.e. A*. So let $l(u,v)$ ...
6
votes
1answer
407 views

Finding Shortest Paths of weighted graph using stacks

I will be given some kind of this graph as in the picture below. I've searched some algorithms but it seams as if it is something impossible for me to figure them out. In fact using Floyd–Warshall ...
6
votes
0answers
414 views

Shortest path in graph - upgrade an algorithm

We are given a graph with $n$ vertices, $m$ edges, and path edge costs of $x$. For vertices without a direct path that are distant exactly one neighbor, we can add new edge with edge cost $y$. Our ...
5
votes
0answers
78 views

Minimum Number of Edges Added to a DAG to get Unique Topological Order

The question is simple: Given an unweighted directed acyclic graph, $G = (V, E)$, what is the minimum number of directed edges we need to add to $E$ such that the resulting graph $G = (V, E')$ has ...
5
votes
0answers
148 views

What is the current fastest algorithm for finding the maximum common subgraph?

First of all, it's my first time in #ComputerScience at StackExchange so, my apologies if I'm making some newbie mistake when asking this question. So, I'm currently researching algorithms for ...
5
votes
0answers
228 views

How to convert a dependency graph to series-parallel representation?

I'm given a finite partial order, in the form of a dependency graph between items, and I'd like to have it in series-parallel form (Wikipedia). So formally, given a finite partial order $\le$ on a ...
5
votes
0answers
407 views

How to apply ant colony optimization to the TSP but repeating nodes and edges

I'm learning the Ant Colony Optimization Algorithm and I would like to apply it to a variation of the TSP problem (find the path that start from a node, crosses all nodes and finish in the initial ...
5
votes
0answers
395 views

Why are the conditions for optimality different for A* tree and graph search?

I am unclear as to why the conditions for optimality for A* search are different for graph search and tree search. When discussing conditions for optimality for A* search in Russell and Norvig's ...
5
votes
0answers
128 views

Has this graph-theoretic problem got a known name? Is it NP-hard?

I am considering the following problem. We are given a Directed Acyclic Graph. In general, there would be some number of subgraphs that, contracted into one node, would make it a tree. For example, ...
5
votes
0answers
168 views

Upper bound on the number of hamiltonian cycles on a $n \times n $ grid graph

What is the best upper bound that is known for the number of hamiltonian cycles on a $n \times n $ grid graph? I did some searching and found that the number of hamiltonian cycles on a planar graph ...
5
votes
1answer
469 views

Shortest path in a known room for a Roomba

I had an interview question once which asked for an algorithm to ensure a Roomba vacuum cleaner visited/vacuumed every "cell" in an unknown shape/size room with unknown obstacles. Depth first search ...
4
votes
0answers
51 views

How to generate a random reducible flow graph?

Is there any known algorithm to generate a random reducible flow graph (single root, single sink) with a given maximum cardinality $N$? Ideally, the distribution should be uniform over the set of ...
4
votes
0answers
107 views

Is Hamiltonian cycle problem on graphs with out-degree at most 3 NP hard?

I am trying to show a different form of Hamiltonian cycle problem is NP Hard. The problem is as follows. We have a directed graph and each node can have at most 3 outgoing edges. Determine if this ...
4
votes
2answers
92 views

Find maximal subgraph containing only nodes of degree 2 and 3

I'm trying to implement a (Unweighted) Feedback Vertex Set approximation algorithm from the following paper: FVS-Approximation-Paper. One of the steps of the algorithm (described on page 4) is to ...
4
votes
3answers
210 views

Are edges in a minimum spanning tree not heavier than respective edges in another spanning tree?

Let $G$ be an undirected connected weighted graph, and let $T$ be a minimum spanning tree of $G$ with edge weights: $w_1 \le w_2 \le ... \le w_{n-1}$. Now let $T'$ be some other spanning tree of $G$ (...
4
votes
0answers
30 views

Finding the “most modular” subset of graph vertices, i.e. that minimize disagreement inside and outside

Let $G = (V, E)$ be a graph. I want to find the subset of vertices of $G$ that minimizes a certain modularity cost. In our setting, the modularity cost of a subset $X$ is defined as the number of ...
4
votes
0answers
46 views

Inferring ranking functions in a general code graph with partial information

Let me define the notion of call graph: A program consists on a set of functions $f,g,h,\ldots$ where each function $n$ is as a mapping $n: D^l \to D^m$. Here $D$ is the datatype representing ...
4
votes
0answers
25 views

Simple proof that finding a combinatorial map of a planar graph given as an incidence matrix can be done in polynomial time?

Suppose that I have a graph $G = (V,E)$, given as an incidence matrix of edges and vertices. Suppose that $G$ is planar, that is, it can be embedded in the plane without edge crossings. I would like ...
4
votes
0answers
42 views

Recalculating dominance after changing the entry node

I'm working with a control-flow graph, which is simply a directed (usually cyclic) graph with an entry (initial) node, and I have calculated all the dominators on the graph. It's noteworth that every ...
4
votes
0answers
77 views

Intuition for vertex/set cover approximation algorithms

The best approximation algorithm for vertex cover is randomly choosing an edge and removing its vertices (picking the largest degree vertex actually is a worse approximation), but the best ...
4
votes
0answers
61 views

Metrics for image/visual complexity in computer vision/graphics?

Could anyone kindly point me to revenant literature in computer vision/graphics that detail on metrics for image/visual complexity and how to regularize that? More specifically, I am trying to design ...
4
votes
1answer
926 views

How is the (local) clustering coefficient defined for vertices with degree 1

We want to compute the clustering coefficient $C$ for an undirected graph $G = (V, E)$. The clustering coefficient $C$ for a graph $G$ is the average over all local clustering coefficients $C_i$, ...
4
votes
0answers
98 views

Parallel bubble sorting on arbitrary graphs

Are there bubblesort-esque algorithms for sorting on arbitrary graphs? I'm working on a problem in which $k$ robots are placed randomly on a graph and have to reach their respective goals as quickly ...
4
votes
0answers
130 views

MST that contains a shortest $s,t$-path

Consider the problem in which we have an (undirected) graph $G=(V,E)$, weight function $w:E\to\mathbb N$ and a pair of vertices $s,t\in V$, and are required to determine whether there exists an MST $T$...
4
votes
0answers
121 views

Successive Shortest Paths vs Ford–Fulkerson

Can someone explain how exactly Successive Shortest Paths (SSP) is a generalization of the Ford–Fulkerson algorithm? I've found this stated in a few papers and websites as well as the Wikipedia page ...
4
votes
0answers
101 views

Optimal schedule for broadcasting a file in a complete graph with overheads

I am trying to solve the following problem and despite having performed quite extensive literature review, I do not seem to find any similar problem or technique that would be useful here. PROBLEM ...
4
votes
0answers
187 views

Voronoi Diagrams with L∞ Metric

I've recently become interested in randomly generating Voronoi diagrams to create "territory" maps (similar to this) for a project I've been working on. Traditional Voronoi diagrams using an ...
4
votes
0answers
3k views

Fastest algorithm for shortest path with atmost k edges on a DAG with non-negative edge weights?

(Please note, this is not a duplicate to Shortest path with exactly $k$ edges OR Shortest path with a fixed number of edges. What I want is a better algorithm) The problem under consideration is to ...
4
votes
0answers
347 views

Is there a relationship between graph entropy and node entropy?

Eagle, et al [1] discuss the notion of node entropy and this is captured in igraph via the diversity metric. I was wondering if there was any relationship between these node entropies and the idea of ...