Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

96 questions
Filter by
Sorted by
Tagged with
15k views

### Finding the shortest path in the presence of negative cycles

Given a directed cyclic graph where the weight of each edge may be negative the concept of a "shortest path" only makes sense if there are no negative cycles, and in that case you can apply the ...
• 273
14k views

### Approximation algorithms for Metric TSP

It is known that metric TSP can be approximated within $1.5$ and cannot be approximated better than $123\over 122$ in polynomial time. Is anything known about finding approximation solutions in ...
• 2,247
2k views

### Examples where the uniqueness of the solution makes it easier to find

The complexity class $\mathsf{UP}$ consists of those $\mathsf{NP}$-problems that can be decided by a polynomial time nondeterministic Turing machine which has at most one accepting computational path. ...
• 11.4k
2k views

### Subgraph containing all nodes and edges that are part of length-limited simple s-t paths in an undirected graph

Quite similar to my previously posted question. This time however, the graph is undirected. Given An undirected graph $G$ with no multiple-edges or loops, A source vertex $s$, A target vertex $t$, ...
• 509
373 views

• 563
6k views

### Finding a minimum "node" weight path

Suppose a graph with node weights only (no edge weights). For a given source-sink pair, how can I find a path with the minimal sum of node weights? Does this problem have a name? Is it possible to ...
• 253
755 views

### Number of subgraphs with a given number of nodes

Let $G = ( V_G, E_G )$ be a graph. Let $E_H \subseteq E_G$. The subgraph of $G$ edge-induced by $E_H$ is $H = ( V_H, E_H)$, where $V_H = \{ v \in V_G : \exists ( u, w ) \in E_H\ v = u \lor v = w \}$ ...
• 6,852
629 views

### Pagerank in directed *acyclic* graphs (DAG)

I deal with pagerank computations on large directed acyclic graphs (DAG). I found no reference to work on this specific case, only some work on pagerank in more specific cases, e.g., PageRank of Scale ...
987 views

### For which values of $k$ is the $k$-disjoint paths problem in $\mathcal{P}$?

The $k$-Vertex-Disjoint Paths Problem ($k$-$\text{DPP}$) is defined as follows: Input: A graph $G=(V,E)$ and $k$ pairs of vertices $(s_1,t_1),\ldots,(s_k,t_k)$. Question: Does there exist $k$-...
• 9,458
3k views

### Are any of the state of the art Maximum Flow algorithms practical?

For the maximum flow problem, there seem to be a number of very sophisticated algorithms, with at least one developed as recently as last year. Orlin's Max flows in O(mn) time or better gives an ...
• 421
5k views

### Hard-looking algorithmic problems made easy by theorems

I am looking for nice examples, where the following phenomenon occurs: (1) An algorithmic problem looks hard, if you want to solve it working from the definitions and using standard results only. (2) ...
14k views

### Vertex Cover applications in the real world

What applications does the Vertex Cover Problem have in the real world? Which industry or research projects use actually implemented software that is based on theoretical results for the Vertex Cover ...
• 311
1k views

### Counting Isomorphism Types of Graphs

Polya's counting theorem leads to an algorithm for counting (precisely) the number of isomorphism types of graphs with $n$ vertices in $\exp (\sqrt n )$ steps. From Polya theorem you get a formula ...
• 6,053
1k views

### Optimization problems with minimax characterization, but no polynomial-time algorithm

Consider optimization problems of the following form. Let $f(x)$ be a polynomial-time computable function that maps a string $x$ into a rational number. The optimization problem is this: what is the ...
• 11.4k
2k views

### Problems that are easy on unweighted graphs, but hard for weighted graphs

Many algorithmic graph problems can be solved in polynomial time both on unweighted and weighted graphs. Some examples are shortest path, min spanning tree, longest path (in directed acyclic graphs), ...
• 11.4k
3k views

### Recognizing line graphs of hypergraphs

The line graph of a hypergraph $H$ is the (simple) graph $G$ having edges of $H$ as vertices with two edges of $H$ are adjacent in $G$ if they have nonempty intersection. A hypergraph is an $r$-...
• 2,477
590 views

### Complexity of finding the smallest well-covered completion

This is related to an earlier question on which graphs have the property that all maximal independent sets are maximum — such graphs turn out to be known as the well-covered graphs. Any graph $G$ is ...
1k views

### Lower bounds on single-source shortest paths in directed graphs

Are there any non-trivial lower bounds on the complexity of single-source shortest paths (SSSP) in a directed graph, where all edges have non-negative edge weights? Can we rule out the possibility of ...
• 12.1k
424 views

• 3,264
787 views

### Complexity of a switch network problem

A switch network (the name is invented) is made with three types of nodes: one Start node one End node one or more Switch nodes The switch node has 3 exits: Left, Up, Right; has two states L and R ...
639 views

### Approximation for counting the number of simple $s$-$t$ paths in a general graph

I have been told that there are some good polynomial time algorithms for approximating the number of simple paths in an directed graph from given starting vertex $s$ to given ending vertex $t$. Does ...
• 1,099
2k views

### Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs

I'm looking for problems which are known to be NPC for directed graphs but has a polynomial algorithm for undirected graphs. I've seen the question regarding the other way around here “Directed” ...
• 9,458
2k views

### What is the fastest deterministic algorithm for incremental DAG reachability?

As the title. The incremental algorithm maintains the reachability information of a DAG when it undergoes a series of edge insertions (but no deletions). And the algorithm supports constant query (if ...
• 519
448 views

### Strongly Regular Graph and GI-Completeness

It is not known if graph isomorphism (GI) for strongly regular graphs (SRGs) is in P. Are there any hints that it might or might not be GI-Complete? Are there any strong consequences in such cases? (...
• 1,281
4k views

### Is the longest trail problem easier than the longest path problem?

The longest path problem is NP-hard. The (typical?) proof relies on a reduction of the Hamiltonian path problem (which is NP-complete). Note that here the path is taken to be (node-)simple. That is, ...
• 143
2k views

### Generalization of the Hungarian algorithm to general undirected graphs?

The Hungarian algorithm is a combinatorial optimization algorithm which solves the maximum weight bipartite matching problem in polynomial time and anticipated the later development of the important ...
• 3,664
2k views

### Is the feedback vertex set problem on planar bounded degree graphs hard?

Is it known whether the feedback vertex set problem on undirected planar graphs of bounded degree is $\mathsf{NP}$-hard?
• 133
561 views

### Given a graph, decide if its edge connectivity is at least n/2 or not

Chapter 1 of the book The Probabilistic Method, by Alon and Spencer mentions the following problem: Given a graph $G$, decide if its edge connectivity is at least $n/2$ or not. The author mentions ...
• 1,631
1k views

### What is the currently best known algorithm for the transportation problem?

Consider the well known transportation problem: There are $m$ supply nodes, $n$ demand nodes and $k$ feasible arcs. Every node has a integer supply or demand, and the arcs have integer costs, used ...
• 990
853 views

### Largest common subgraph of two maximal planar graphs

Consider the following problem - Given maximal planar graphs $G_1$ and $G_2$, find the graph $G$ with maximum number of edges such that there is a subgraph (not necessarily induced) in both $G_1$ and ...
• 1,631
820 views

### What is the complexity of this path problem?

Instance: An undirected graph $G$ with two distinguished vertices $s\neq t$, and an integer $k\geq 2$. Question: Does there exist an $s-t$ path in $G$, such that the path touches at most $k$ vertices?...
• 11.4k
16k views

### What is the computational complexity of "solving" chess?

The basic idea of backwards induction is to start with all the possible final positions of a game in which player X wins. So for chess, look at all the ways White can checkmate Black. Now work ...
• 223
Given a weighted undirected graph with $m = o(n^2)$ edges, I would like to compute distances of approximation less than 2 between any given pair of vertices. Of course, I would like to use ...