Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

44
votes
4answers
12k 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 ...
37
votes
4answers
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. ...
30
votes
3answers
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 ...
28
votes
4answers
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 ...
27
votes
16answers
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
2answers
1k 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 ...
26
votes
4answers
699 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 ...
25
votes
3answers
473 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 ...
25
votes
3answers
933 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 ...
25
votes
2answers
616 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 ...
24
votes
5answers
5k 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 ...
24
votes
5answers
742 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 ...
24
votes
2answers
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_%...
24
votes
0answers
954 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 ...
23
votes
3answers
891 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 ...
23
votes
5answers
3k 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 ...
23
votes
1answer
514 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. ...
22
votes
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), ...
22
votes
7answers
2k 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 ...
22
votes
4answers
8k 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 ...
22
votes
1answer
539 views

Is there a problem that is easy for cubic graph 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, ...
22
votes
1answer
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
3answers
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 ...
21
votes
5answers
2k 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 ...
21
votes
2answers
871 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 ...
21
votes
2answers
793 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)$, ...
20
votes
5answers
1k 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. ...
20
votes
2answers
467 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 ...
20
votes
5answers
420 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 ...
20
votes
2answers
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$-...
20
votes
1answer
822 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 ...
20
votes
0answers
571 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 ...
19
votes
2answers
904 views

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

Feedback Vertex Set 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 poly-time ...
19
votes
2answers
1k 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. ...
19
votes
2answers
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 ...
19
votes
1answer
739 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^...
19
votes
2answers
775 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 ...
19
votes
2answers
699 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 ...
18
votes
5answers
1k 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 ...
18
votes
3answers
507 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 ...
18
votes
2answers
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 ...
18
votes
2answers
450 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$?...
18
votes
1answer
256 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?
17
votes
2answers
465 views

Parameterized complexity of graph intersection number

What if anything is known about the parameterized complexity of computing the intersection number of a graph (the smallest number of cliques needed to cover all its edges)? It has long been known to ...
17
votes
2answers
594 views

Does an algorithm exist to efficiently maintain connectedness information for a DAG in presence of inserts/deletes?

Given a directed acyclic graph, $G(V,E)$, is it possible to efficiently support the following operations? $isConnected(G,a,b)$: Determines if there is a path in $G$ from node $a$ to node $b$ $link(G,...
17
votes
1answer
523 views

Connectivity of graphs by edge and vertex removal

Let us say that a graph $G$ is $(a,b)$-connected if the removal of any $a$ vertices and any $b$ edges from $G$ leaves always a connected graph. For example, a $k$-connected graph, according to the ...
17
votes
1answer
731 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 ...
17
votes
1answer
458 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 ...
16
votes
6answers
1k 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, ...
16
votes
3answers
1k views

Are vertex colourings--in a sense--edge colourings?

We know that edge colourings of a graph $G$ are vertex colourings of a special graph, namely of the line graph $L(G)$ of $G$. Is there a graph operator $\Phi$ such that vertex colourings of a graph ...