Questions tagged [graph-theory]
Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
1,481
questions
1
vote
1
answer
1k
views
Removing all but a few cycles in a graph
Let problem $S$ be defined as
Given undirected graph $G$ and a set
of cycles $C_1,C_2, \ldots, C_n$ in G,
find minimum number of vertices that
need to be deleted to remove all
cycles in the ...
- 467
7
votes
1
answer
960
views
Graph Theory Fun Problem
Show that in any graph $G$ with min-degree $k$ ($k \geq 1$ duh!) you can find as its subgraph any tree on $k+1$ vertices.
I have not been able to solve the question so far. However, I would like if ...
- 1,933
-2
votes
1
answer
2k
views
How do I formally describe a rooted, directed, acyclic graph?
I need a formalism to describe the following requirements:
I have a graph comprised of nodes and transitions between nodes
Nodes maybe one of three types, all are sub-classes of a base abstract node ...
- 153
1
vote
3
answers
4k
views
Is it possible to have a 4-coloring for a non-planar graph ? [closed]
I have been working on this thread Grid $k$-coloring without monochromatic rectangles, and I am aware that the four color theorem implies that all planar graphs are four colorable.
The question is ...
7
votes
3
answers
5k
views
Polynomial Time Algorithm for Graph Isomorphism Testing [closed]
"Michael I. Trofimov" claims that he has found a poly-time algorithm for graph isomorphism, which works for all graphs.
The paper is given in arXiv. The companion website gives a proof-of-concept ...
- 16.3k
7
votes
4
answers
887
views
A relaxed Steiner Tree Problem
Given a weighted graph $G(V,E,w)$ where $w$ is the weight function on edges and a subset of vertices $S\subseteq Q$ called terminals, a Steiner Tree is a connected subgraph which connects all vertices ...
- 73
15
votes
6
answers
498
views
Global properties of hereditary classes?
A hereditary class of structures (e.g. graphs) is one that is closed under induced substructures, or equivalently, is closed under vertex removal.
Classes of graphs that exclude a minor have nice ...
- 18.7k
11
votes
1
answer
441
views
Computation of max H-free sets
In a graph, an independent set is a vertex subset which doesn't contain an edge as an induced subgraph. The problem of finding largest independent sets in a graph is a fundamental algorithmic question,...
- 1,952
6
votes
3
answers
832
views
In Strongly connected tournament T.Is it NP-hard to find a minimum number of vertices(V1) which make T\V1 as non strongly connected tournament.
Given strongly connected tournament T.find a minimum number of vertices(V1) which make T\V1 as non strongly connected tournament.
I have doubt whether the problem mentioned can be solved in polynomial ...
- 467
13
votes
2
answers
378
views
H-free partition
This is a question inspired by the H-free cut problem. Given a graph, a partition of its vertex set $V$ into $r$ parts $V_1, V_2, \ldots, V_r$ is $H$-free if $G[V_i]$ does not induce a copy of $H$ for ...
- 599
1
vote
2
answers
901
views
Does this notation have a special meaning?
I am currently reading a paper and I don't know how to interpret this notation you can see on the screenshot.
http://moxn.brainex.de/pub/dfg.png
Do the pointy angle brackets have a special meaning ...
- 121
19
votes
1
answer
709
views
Rapidly mixing Markov chains on 3-colorings of a cycle
The Glauber dynamics is a Markov chain on the colorings of a graph in which at each step one attempts to recolor a randomly chosen vertex with a random color. It does not mix for the 3-colorings of a ...
- 50.2k
17
votes
1
answer
589
views
Sensitivity of Graph Properties
In [1], Turan shows that the sensitivity (called "critical complexity" in the paper) of a graph property is strictly greater than $\lfloor {1\over 4} m \rfloor$ where $m$ is the number of vertices in ...
- 171
8
votes
6
answers
666
views
Have any generalizations of maximum weight matching been studied?
For example, one way to view maximum weight matching is that each vertex $v$ gets a utility $f_v= w(e_v)$ that equals the weight of the edge it's matched on, and zero otherwise.
accordingly, a ...
19
votes
1
answer
1k
views
Construction of graphs where every pair of vertices have an unique common neighbor
Let $G$ be a simple graph on $n$ vertices $(n > 3)$ with no vertex of degree $n − 1$. Suppose that for any two vertices of $G$, there is a unique vertex adjacent to both of them. It is an exercise ...
- 599
40
votes
10
answers
13k
views
Data for testing graph algorithms
I am looking for a source of huge data sets to test some graph algorithm implemention. Please also provide some information about the type/distribution (e.g. directed/undirected, simple/not simple, ...
Chris
35
votes
3
answers
2k
views
Given a weighted dag, is there an O(V+E) algorithm to replace each weight with the sum of its ancestor weights?
The problem, of course, is double counting. It's easy enough to do for certain classes of DAGs = a tree, or even a serial-parallel tree. The only algorithm I have found which works on general DAGs in ...
- 562
2
votes
3
answers
1k
views
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 ...
- 20.5k
3
votes
2
answers
327
views
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 ...
- 20.5k
2
votes
1
answer
343
views
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. http://en.wikipedia.org/wiki/Asymmetric_graph
I'm looking for an efficient way to compute a random asymmetric graph on a ...
- 20.5k
7
votes
4
answers
990
views
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
- 20.5k
24
votes
2
answers
884
views
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
1k
views
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,925
23
votes
3
answers
2k
views
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,746
25
votes
6
answers
2k
views
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.
...
- 503
11
votes
2
answers
5k
views
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
345
views
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 ...
- 8,821
23
votes
1
answer
374
views
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,225
17
votes
2
answers
671
views
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
1k
views
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,963
17
votes
1
answer
1k
views
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