Questions tagged [graph-theory]

Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.

Filter by
Sorted by
Tagged with
2 votes
3 answers

Best bounds for the longest path optimization problem in cubic Hamiltonian graph?

optimization problem Input: cubic Hamiltonian graph feasible solution: A simple path measure to optimize: length of the simple path Design a polynomial-time algorithm that outputs the longest path ...
3 votes
2 answers

What is the complexity of computing a compatible 3-coloring of a complete graph?

Given a complete graph whose edges are colored by 3 colors, a compatible 3-coloring is a coloring of nodes such that no edge of the graph has the same color as its end-points. The best algorithm I ...
2 votes
1 answer

What is the most efficient algorithm to sample graphs with trivial automorphism groups ?

Let us call a graph "asymmetric" if it has no nontrivial automorphism group. I'm looking for an efficient way to compute a random asymmetric graph on a ...
7 votes
4 answers

What are the best known upper bounds and lower bounds for computing O(log n)-Clique?

Input: a graph with n nodes, Output: A clique of size $O(\log n)$, Providing links to references would be great
24 votes
2 answers

Space efficient "industrial" unbalanced expanders

I am looking for unbalanced expanders that are "good" and "space-efficient". Specifically, a bipartite left-regular graph $G=(A,B,E)$, $|A|=n$, $|B|=m$, with left degree $d$ is a $(k,\epsilon)$-...
  • 971
28 votes
3 answers

How to produce a random graph that does not have a Hamiltonian cycle?

Let class A denote all the graphs of size $n$ which have a Hamiltonian cycle. It is easy to produce a random graph from this class--take $n$ isolated nodes, add a random Hamiltonian cycle and then add ...
  • 1,945
23 votes
3 answers

What bounds can be put on counting reachable nodes in a dag?

Given is a dag. You want to label each node by how many nodes are reachable from it. $O(V(V+E))$ is a trivial upper bound; $\Omega(V+E)$ is a lower bound (I think). Is there a better algorithm? Is ...
  • 4,776
25 votes
6 answers

Graph families which have polynomial time algorithms for computing the chromatic number

Post updated on 31st of August: I added a summary of the current answers below the original question. Thanks for all the interesting answers! Of course, everyone can continue posting any new findings. ...
11 votes
2 answers

Any fast algorithm for minimum cost feedback arc set problem?

In a directed graph, $G=(V,E)$, $F\subset E$, if $G\setminus F$ is a DAG(directed acyclic graph), $F$ is called a feedback arc set. If each edge is associated with a weight $w$, the minimum cost ...
  • 161
13 votes
1 answer

Finding odd holes in circulant Paley graphs

The Paley graphs Pq are those whose vertex-set is given by the finite field GF(q), for prime powers q≡1 (mod 4), and where two vertices are adjacent if and only if they differ by a2 ...
23 votes
1 answer

Cliquewidth of Almost Cographs

(I posted this question to MathOverflow two weeks ago, but so far without a rigorous answer) I have a question about graph width measures of undirected simple graphs. It is well-known that cographs (...
  • 5,245
17 votes
2 answers

H-free cut problem

Suppose you are given a connected, simple, undirected graph H. The H-free cut problem is defined as follows: Given a simple, undirected graph G, is there a cut (partition of vertices into two ...
  • 1,855
20 votes
2 answers

Succinct circuit representation of graphs

The complexity class PPAD (e.g. computing various Nash equilibria) can be defined as the set of total search problems polytime reducible to END OF THE LINE: END OF THE LINE: Given circuits S and P ...
  • 5,953
17 votes
1 answer

Online transitive closure better than O(N^2) per edge addition

I'm looking for an online algorithm to maintain the transitive closure of a directed acyclic graph with a time complexity less than O(N^2) per edge addition. My current algorithm is like this: ...
  • 696

27 28 29 30