Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

Filter by
Sorted by
Tagged with
17 votes
1 answer
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 ...
jleahy's user avatar
  • 273
46 votes
4 answers
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 ...
Alex Golovnev's user avatar
38 votes
4 answers
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. ...
Andras Farago's user avatar
12 votes
3 answers
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$, ...
Lior Kogan's user avatar
6 votes
1 answer
373 views

Is this edge orientation optimization problem NP-hard?

Is the following optimization problem NP-hard? Problem. For a given undirected graph $G=(V,E)$, find an orientation of the edges that minimizes the objective value $\sum_\limits{v\in V} ~d_{out}(v)\...
maxdan94's user avatar
  • 563
2 votes
1 answer
575 views

techniques or examples of analyzing a series of graphs

Let there be a sequence of graphs $G_1, G_2, G_3, ...$ constructed using some particular approach or algorithm. in this particular case $G_n$ is constructed by modifying $G_{n-1}$ in some "...
vzn's user avatar
  • 11k
27 votes
3 answers
1k views

Reverse Graph Spectra Problem?

Usually one constructs a graph and then asks questions about the adjacency matrix's (or some close relative like the Laplacian) eigenvalue decomposition (also called the spectra of a graph). But what ...
user834's user avatar
  • 2,806
21 votes
2 answers
1k views

Is feedback vertex set problem solvable in polynomial time for 3-degree bounded graphs?

Feedback Vertex Set (FVS) is NP-complete for general graphs. It is known to be NP-complete for degree-$8$ bounded graphs due to a reduction from vertex cover. The Wikipedia article says that it is ...
Davis Issac's user avatar
16 votes
2 answers
1k views

Complexity of counting the number of edge covers of a graph

An edge cover is a subset of edges of a graph such that every vertex of the graph is adjacent to at least one edge of the cover. The following two papers say that counting edge covers is #P-complete: ...
a3nm's user avatar
  • 9,449
16 votes
6 answers
3k views

When are two algorithms said to be "similar"?

I do not work in theory, but my work requires reading (and understanding) theory papers every once in a while. Once I understand a (set of) results, I discuss these results with people I work with, ...
Rachit's user avatar
  • 838
15 votes
5 answers
911 views

References for Modular Decomposition

What are good papers/books to better understand the power of Modular Decomposition and its properties? I'm particularly interested in algorithmic aspects of Modular Decomposition. I have heard that ...
Vinicius dos Santos's user avatar
13 votes
2 answers
937 views

What's the correlation between treewidth and instance hardness for random 3-SAT?

This recent paper from FOCS2013, Strong Backdoors to Bounded Treewidth SAT by Gaspers and Szeider talks about the link between the treewidth of the SAT clause graph and instance hardness. For ...
vzn's user avatar
  • 11k
12 votes
2 answers
851 views

Number of vertices present in all maximum matchings

Given a graph $G$, we need to find the cardinality of the largest set of vertices so that each of them are present in every maximum matching possible. Is there a solution beside the obvious remove ...
Hououin Kyouma's user avatar
12 votes
2 answers
1k views

How to generate graphs with known optimal vertex cover

I'm looking for a way to generate graphs so that the optimal vertex cover is known. There are no restrictions on the number of nodes or edges, only that the graph is completely connected. the idea is ...
AndresQ's user avatar
  • 199
12 votes
4 answers
4k views

Incremental Maximum Flow in Dynamic graphs

I'm looking for a fast algorithm to compute maximum flow in dynamic graphs. i.e given a graph $G=(V,E)$ and $s,t\in V$ we have maximum flow $F$ in $G$ from $s$ to the $t$. Then new/old node $u$ added/...
Saeed's user avatar
  • 3,440
11 votes
4 answers
747 views

Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs

Crossposted from MO. Let $C$ be a graph class defined by a finite number of forbidden induced subgraphs, all of which are cyclic (contain at least one cycle). Are there NP-hard graph problems that ...
joro's user avatar
  • 1,955
11 votes
2 answers
1k views

For which families of graphs is Generalized Geography in $P$?

As @Marzio mentioned, the following game is known as Generalized Geography. Given a graph $G=(V,E)$ and a starting vertex $v \in V$, the game is defined as follows: At each turn (two players ...
R B's user avatar
  • 9,458
9 votes
2 answers
565 views

The ODD EVEN DELTA problem

Let $G = ( V, E )$ be a graph. Let $k \leq |V|$ be an integer. Let $O_k$ be the number of edge induced subgraphs of $G$ having $k$ vertices and an odd number of edges. Let $E_k$ be the number of edge ...
Giorgio Camerani's user avatar
8 votes
4 answers
2k 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'$ -...
Lior Kogan's user avatar
8 votes
3 answers
784 views

Is that edge orientation optimization problem NP-hard?

Is the following optimization problem NP-hard? Problem. For a given undirected graph $G=(V,E)$, find an orientation of the edges that minimizes the objective value $\sum_\limits{u\in V} ~\left( d_{...
maxdan94's user avatar
  • 563
8 votes
2 answers
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 ...
Chang's user avatar
  • 253
5 votes
1 answer
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 \}$ ...
Giorgio Camerani's user avatar
5 votes
1 answer
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 ...
Matthieu Latapy's user avatar
4 votes
2 answers
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$-...
R B's user avatar
  • 9,458
32 votes
3 answers
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 ...
Rob Lachlan's user avatar
31 votes
16 answers
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) ...
28 votes
5 answers
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 ...
scatman's user avatar
  • 311
27 votes
0 answers
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 ...
Gil Kalai's user avatar
  • 6,053
26 votes
3 answers
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 ...
Andras Farago's user avatar
23 votes
10 answers
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), ...
Andras Farago's user avatar
21 votes
2 answers
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$-...
user13136's user avatar
  • 2,477
20 votes
0 answers
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 ...
David Eppstein's user avatar
19 votes
0 answers
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 ...
D.W.'s user avatar
  • 12.1k
18 votes
0 answers
424 views

Complexity of the homomorphism problem parameterized by treewidth

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 $...
a3nm's user avatar
  • 9,449
18 votes
1 answer
898 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 ...
wei wang's user avatar
  • 519
18 votes
4 answers
911 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{...
Andreas Björklund's user avatar
18 votes
1 answer
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 ...
Marzio De Biasi's user avatar
17 votes
1 answer
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 ...
bbejot's user avatar
  • 1,099
17 votes
4 answers
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” ...
R B's user avatar
  • 9,458
16 votes
0 answers
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 ...
wei wang's user avatar
  • 519
16 votes
1 answer
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? (...
DurgaDatta's user avatar
  • 1,281
14 votes
1 answer
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, ...
Jasper's user avatar
  • 143
14 votes
2 answers
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 ...
Dai Le's user avatar
  • 3,664
13 votes
5 answers
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?
marc's user avatar
  • 133
13 votes
1 answer
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 ...
Vinayak Pathak's user avatar
13 votes
0 answers
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 ...
Riko Jacob's user avatar
13 votes
1 answer
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 ...
Vinayak Pathak's user avatar
12 votes
2 answers
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?...
Andras Farago's user avatar
12 votes
4 answers
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 ...
Seamus's user avatar
  • 223
11 votes
3 answers
348 views

Computing distances with approximation less than 2 in general graphs?

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 ...
Siddhartha's user avatar