# Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

91 questions
Filter by
Sorted by
Tagged with
11k 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 ...
13k 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 ...
1k 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. ...
231 views

1k views

### Subgraph containing all nodes and edges that are part of length-limited simple s-t paths in a digraph

Note: I posted a similar question regarding undirected graph. Given A digraph $G$ with no multiple-edges or loops A source node $s$ A target node $t$ Maximal path length $l$ I am looking for $G'$ -...
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 ...
688 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 \}$ ...
627 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$-...
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) ...
2k 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 ...
11k 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 ...
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” ...
550 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 ...
3k 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, ...
748 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 ...
13k 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 ...
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$-...
712 views

### What is the fastest deterministic algorithm for dynamic digraph reachability with no edge deletion?

What is the best deterministic result for maintaining the dynamic transitive closure in a directed graph with only edge insertion? I read some papers on the dynamic transitive closure problem with ...
404 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? (...
The homomorphism problem $\text{Hom}(\mathcal{G}, \mathcal{H})$ for two classes $\mathcal{G}$ and $\mathcal{H}$ of graphs is defined as follows: Input: a graph $G$ in $\mathcal{G}$, a graph $H$ in $... 0answers 1k 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 ... 0answers 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 ... 3answers 1k views ### Optimization problems with good 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 ... 0answers 889 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 ... 2answers 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 ... 1answer 2k views ### Counting the number of distinct s-t cuts in a oriented graph I am trying to find the number of distinct s-t cuts in a oriented unweighed graph. In an article Enumeration in Graphs p. 45 I found good way how to enumerate those cuts (section 7.3). Is there a ... 3answers 2k views ### All pair shortest path problem for large number of nodes I am having a small problem. I have the complete city's data which has over 100,000 nodes and 40,000 paths in my database. Now I need to calculate the all pair shortest path between all of them. ... 0answers 612 views ### K-shortest path in large sparse graph I am an engineer and looking for a reference to find k-shortest path's in a large sparse graph. In the search for it, I came acorss Yen's ranking loopless algorithm and an improved implementation of ... 1answer 338 views ### Are there good implementations for easy subclasses of NP-hard graph problems Given graph G = (V,E) I need to solve some problems that are NP-Complete on G. However it could be that G belongs to some class where these problems has polynomial solutions (here is a great resource ... 1answer 5k views ### Reducing a minimum cost edge-cover problem to minimum cost weighted bipartie perfect matching I have a set of edges [m,n] of a bipartie graph U, V with a cost assigned to each edge and I need to find the minimum cost edge-cover covering all nodes in U, V. There is one additional constraint is ... 4answers 830 views ### Turing-complete computation models on graphs There are many Turing complete computation models and new ones are devised all the time. I am looking for Turing-complete computation models based on graphs? 10answers 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), ... 0answers 580 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 ... 4answers 881 views ### Parametrized Algorithm for Finding Bicliques Given an$n$vertex undirected graph, what is the best known runtime bound for finding a subgraph which is a$k\times k$-biclique? Are there faster parametrized algorithms than the$\binom{n}{k}\mbox{...
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 ...