Questions tagged [graph-algorithms]
Algorithms on graphs, excluding heuristics.
1,032
questions
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 ...
- 2,247
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. ...
- 11.3k
35
votes
4
answers
3k
views
Why is "topological sorting" topological?
Why is "topological sorting" called "topological"? Is it just because it determines an order without altering any vertices or edges -- like a doughnut and coffee cup are topologically equivalent? Why ...
- 453
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 ...
- 421
32
votes
4
answers
2k
views
What is simplest polynomial algorithm for PLANARITY?
There are several algorithms that decide in polynomial time whether a graph can be drawn in the plane or not, even many with a linear running time. However, I could not find a very simple algorithm ...
- 13.9k
30
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) ...
27
votes
5
answers
13k
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 ...
- 301
27
votes
3
answers
937
views
The complexity of determining if a fixed graph is a minor of another
The result by Robertson and Seymour demonstrates an $O(n^3)$ algorithm for testing whether a fixed graph $G$ is a minor of $H$. I have two and a half questions on this topic:
1) It appears that there ...
- 779
27
votes
1
answer
685
views
Is there a problem that is easy for cubic graphs but hard for graphs with maximum degree 3?
Cubic graphs are graphs where every vertex has degree 3. They have been extensively studied and I'm aware that several NP-hard problems remain NP-hard even restricted to subclasses of cubic graphs, ...
- 1,868
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 ...
- 6,013
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 ...
- 11.3k
26
votes
4
answers
748
views
How to find the cycles which, together, involve the biggest number of non-shared edges in a directed graph?
I am not a computer science theorist, but think this real world problem belongs here.
The problem
My company have several units accross the country.
We offered to employees the possibility to work ...
- 363
26
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 ...
- 2,786
25
votes
5
answers
10k
views
What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?
Stable Marriage Problem: http://en.wikipedia.org/wiki/Stable_marriage_problem
I am aware that for an instance of a SMP, many other stable marriages are possible apart from the one returned by the ...
- 353
25
votes
7
answers
3k
views
Finding twin vertices in graphs
Let $G=(V,E)$ be a graph. For a vertex $x\in V$, define $N(x)$ to be the (open) neighbourhood of $x$ in $G$. That is, $N(x)=\{y\in V \,\vert\, \{x,y\}\in E\}$. Define two vertices $u,v$ in $G$ to be ...
- 1,394
25
votes
3
answers
557
views
Complexity of "is a graph a product"
This question arises out of pure curiosity (it came up while thinking about unshuffling a string, but I'm not sure if it's actually related) so I hope it's appropriate.
There are various graph ...
- 1,561
25
votes
5
answers
953
views
Minimum Flip Connectivity Problem
I formulated the following problem today while playing with my GPS. Here it is :
Let $G(V,E)$ be a directed graph such that if $e=(u,v) \in E$ then $(v,u) \notin E$, i.e., $G$ is an orientation of ...
- 10.6k
24
votes
5
answers
4k
views
Approximation algorithms for Maximum Independent Set on special classes of graphs
We know that Maximum Independent Set (MIS) is hard to approximate within a factor of $n^{1-\epsilon}$ for any $\epsilon > 0$ unless P = NP. What are some special classes of graphs for which better ...
- 1,591
24
votes
2
answers
1k
views
What is the best exact algorithm to compute the core of a graph?
A graph H is a core if any homomorphism from H to itself is a bijection. A subgraph H of G is a core of G if H is a core and there is a homomorphism from G to H.
http://en.wikipedia.org/wiki/Core_%...
- 901
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), ...
- 11.3k
23
votes
1
answer
609
views
The randomized query complexity of the conjoined trees problem
An important 2003 paper by Childs et al. introduced the "conjoined trees problem": a problem admitting an exponential quantum speedup that's unlike just about any other such problem that we know of. ...
- 13.6k
22
votes
5
answers
3k
views
Program for computing Tree decomposition of a graph
Does anybody know of an open-source program for computing Tree decomposition of graphs for a fixed "k"(width)? I know that the problem of finding Tree-Decomposition is NP-Hard for variable "k", but my ...
user4654
22
votes
1
answer
1k
views
Generating a tower defense maze, aka Finding the K most vital nodes ("nodewise interdiction") in an unweighted grid-graph
In a tower defense game, you have an NxM grid with a start, a finish, and a number of walls.
Enemies take the shortest path from start to finish without passing through any walls (they aren't usually ...
21
votes
3
answers
2k
views
Graphs in which every minimal separator is an independent set
Background:
Let $u, v$ be two vertices of an undirected graph $G=(V,E)$.
A vertex set $S\subseteq V$ is a $u,v$-separator if $u$ and $v$
belong to different connected components of $G-S$. If no proper
...
- 398
21
votes
2
answers
1k
views
Finding a 5-cycle in a sparse graph efficiently.
(crossposted from MathOverflow)
Hi,
I was reading this thread: https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length
I want to find a 5-cycle in a graph. Actually, what I really ...
- 1,573
21
votes
2
answers
522
views
Is it necessary to call matrix multiplication $n$ times to find a claw
A claw is a $K_{1,3}$. A trivial algorithm will detect a claw in $O(n^4)$ time. It can be done in $O(n^{\omega+1})$, where $\omega$ is the exponent of fast matrix multiplication, as follows: take the ...
- 2,560
21
votes
2
answers
987
views
Max-Cut algorithm that shouldn't work, unclear why
OK, this might seem like a homework question and, in a sense, it is. As a homework assignment in an undergraduate algorithms class, I gave the following classic:
Given an undirected graph $G=(V,E)$, ...
- 794
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 ...
- 368
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$-...
- 2,477
21
votes
2
answers
2k
views
Computing the Cheeger constant: feasible for which classes?
Computing the Cheeger constant of a graph, also known as the isoperimetric constant
(because it is essentially a minimum area/volume ratio), is known to be NP-complete.
Generally it is approximated. ...
- 3,743
21
votes
2
answers
874
views
maintaining a balanced spanning tree of a growing undirected graph
I am looking for ways to maintain a relatively balanced spanning tree of a graph, as I add new nodes/edges to the graph.
I have an undirected graph that starts as a single node, the "root".
At each ...
- 341
20
votes
5
answers
2k
views
Deterministic Parallel algorithm for perfect matching in general graphs?
In complexity class $\mathsf{P}$, there are some problems conjectured NOT to be in the class $\mathsf{NC}$, i.e. problems with deterministic parallel algorithms. Maximum Flow problem is one example. ...
- 7,638
20
votes
5
answers
468
views
Reducing space usage of st-connectivity with multiple passes?
Suppose a graph $G$ with $n$ vertices is presented as a stream of $m$ edges, but multiple passes are allowed over the stream.
Monika Rauch Henzinger, Prabhakar Raghavan, and Sridar
Rajagopalan ...
- 18.9k
20
votes
2
answers
2k
views
Data structure for shortest paths
Let $G$ be an unweighted undirected graph with $n$ vertices and $m$ edges. Is it possible to preprocess $G$ and produce a data structure of size $m \cdot \mathrm{polylog}(n)$ so that it can answer ...
- 1,559
20
votes
1
answer
964
views
How fast can we compute the set inclusion poset of a set family?
Given a set family $\mathcal{F}$ of subsets of a universe $U$.
Let $S_1,S_2 \in \mathcal F$ and we want to answer is $S_1 \subseteq S_2$.
I am looking for a data-structure that will allow me to ...
- 1,339
20
votes
0
answers
585
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 ...
- 50.9k
19
votes
5
answers
2k
views
Fast treewidth algorithms
I would like to compute the treewidth of a graph. There are really good heuristics for other NP-hard graph problems such as VF2 for subgraph isomorphism, with code available in igraph for example. I ...
- 3,950
19
votes
3
answers
665
views
What separates easy global problems from hard global problems on graphs of bounded treewidth?
Plenty of hard graph problems are solvable in polynomial time on graphs of bounded treewidth. Indeed, textbooks typically use e.g. independet set as an example, which is a local problem. Roughly, a ...
- 3,160
19
votes
1
answer
984
views
Count the number of spanning trees fast
Let $t(G)$ denote the number of spanning trees in a graph $G$ with $n$ vertices. There is an algorithm that computes $t(G)$ in $O(n^3)$ arithmetic operations. This algorithm is to compute $\frac{1}{n^...
- 605
19
votes
2
answers
875
views
Axioms for Shortest Paths
Suppose we have an undirected weighted graph $G = (V, E, w)$ (with non-negative weights). Let us assume that all shortest paths in $G$ are unique. Suppose we have these $\binom{n}{2}$ paths (sequences ...
- 1,559
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 ...
- 11.7k
18
votes
2
answers
2k
views
Time complexity of counting triangles in planar graphs
Counting triangles in general graphs can be done trivially in $O(n^3)$ time and I think that doing much faster is hard (references welcome). What about planar graphs? The following straightforward ...
- 2,299
18
votes
4
answers
906
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{...
- 3,254
18
votes
2
answers
1k
views
Maximum number of internally vertex-disjoint odd length s-t paths
Let $G$ be an undirected simple graph and let $s,t \in V(G)$ be distinct vertices. Let the length of a simple s-t path be the number of edges on the path. I am interested in computing the maximum size ...
- 5,255
18
votes
1
answer
873
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 ...
- 519
18
votes
2
answers
491
views
Reconstructing a tree from separator queries
Suppose $T$ is an constant-degree tree whose structure we do not know. The problem is to output the tree $T$ by asking queries of the form: "Does the node $x$ lie on the path from node $a$ to node $b$?...
- 1,945
18
votes
1
answer
283
views
A good Library for testing whether a minors exists in a graph?
I would like to know if there are any free graph libraries for testing whether a specific set of minors exists in a given graph?
- 289
18
votes
1
answer
2k
views
DAG reachability with O(n log n) space and O(log n)-time queries?
For a directed acyclic graph ${\langle}V,E{\rangle}$, is there a data structure that allows for reachability queries without requiring quadratic space or linear time? Ideally I seek an algorithm ...
- 281
18
votes
1
answer
785
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 ...
- 22.6k
18
votes
1
answer
1k
views
Reference for mixed graph acyclicity testing algorithm?
A mixed graph is a graph that may have both directed and undirected edges. Its underlying undirected graph is obtained by forgetting the orientations of the directed edges, and in the other direction ...
- 50.9k