Questions tagged [graph-theory]
Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
1,513
questions
68
votes
5
answers
6k
views
The origin of the notion of treewidth
My question today is (as usual) a bit silly; but I would request you to kindly consider it.
I wanted to know about the genesis and/or motivation behind the treewidth concept. I sure understand that ...
- 1,953
43
votes
3
answers
3k
views
Consequences of a quasi-polynomial time algorithm for the graph isomorphism problem
The Graph Isomorphism problem (GI) is arguably
the best known candidate for an NP-intermediate problem.
The best known algorithm is sub-exponential algorithm
with run-time $2^{O(\sqrt{n \log n})}$. ...
- 20.8k
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
39
votes
2
answers
1k
views
How many distinct colors are needed to lower-bound the choosability of a graph?
A graph is $k$-choosable (also known as $k$-list-colorable) if, for every function $f$ that maps vertices to sets of $k$ colors, there is a color assignment $c$ such that, for all vertices $v$, $c(v)\...
- 50.6k
38
votes
17
answers
5k
views
Conjectures implying Four Color Theorem
Four Color Theorem (4CT) states that every planar graph is four colorable. There are two proofs given by [Appel,Haken 1976] and [Robertson,Sanders,Seymour,Thomas 1997]. Both these proofs are computer-...
- 10.6k
36
votes
3
answers
5k
views
Max-cut with negative weight edges
Let $G = (V, E, w)$ be a graph with weight function $w:E\rightarrow \mathbb{R}$. The max-cut problem is to find:
$$\arg\max_{S \subset V} \sum_{(u,v) \in E : u \in S, v \not \in S}w(u,v)$$
If the ...
- 9,830
35
votes
4
answers
2k
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
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
32
votes
0
answers
6k
views
Combinatorics of Bellman-Ford or how to make cyclic graphs acyclic?
Roughly speaking, my question is:
How costly is to make a cyclic graph
acyclic while preserving all simple $s$-$t$ paths?
Let $K_n$ be a complete undirected graph on vertices $\{0,1,\ldots,n+1\}$.
(...
- 6,655
31
votes
5
answers
1k
views
what is easy for minor-excluded graphs?
Approximating number of colorings seems to be easy on minor-excluded graphs using algorithm by Jung/Shah. What are other examples of problems that are hard on general graphs but easy on minor-excluded ...
- 4,661
31
votes
1
answer
900
views
Treewidth and the NL vs L Problem
ST-Connectivity is the problem of determining whether there exists a directed path between two distinguished vertices $s$ and $t$ in a directed graph $G(V,E)$. Whether this problem can be solved in ...
- 10.6k
31
votes
1
answer
807
views
Can graph isomorphism be decided with square root bounded nondeterminism?
Bounded nondeterminism associates a function $g(n)$ with a class $C$ of languages accepted by resource-bounded deterministic Turing machines, to form a new class $g$-$C$. This class consists of those ...
- 18.9k
29
votes
4
answers
914
views
Proofs obtained only through spectral graph theory
I have an increasing interest in spectral graph theory, which I find fascinating, and I've started collecting a few documents that I have yet to read more thoroughly than what I so far have.
However, ...
- 3,254
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,945
28
votes
4
answers
1k
views
Maximal classes for which largest independent set can be found in polynomial time?
The ISGCI lists over 1100 classes of graphs. For many of these we know whether INDEPENDENT SET can be decided in polynomial time; these are sometimes called IS-easy classes. I would like to compile ...
- 18.9k
28
votes
2
answers
1k
views
Maximal/maximum independent sets
Is there something known about the class of graphs with the property that all maximal independent sets have the same cardinality and are therefore maximum ISs?
For example, take a set of points in ...
- 1,306
28
votes
1
answer
869
views
Are there subexponential algorithms for PLANAR SAT known?
Some NP-hard problems which are exponential on general
graphs are subexponential on planar graphs because the
treewidth is at most $4.9 \sqrt{|V(G)|}$ and they are exponential
in the treewidth.
...
- 1,955
27
votes
2
answers
2k
views
Why are Ramanujan graphs named after Ramanujan?
I recently taught expanders, and introduced the notion of Ramanujan graphs.
Michael Forbes asked why they are called this way, and I had to admit I don't know.
Anyone?
- 11k
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
908
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
669
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,798
27
votes
3
answers
983
views
When is relaxed counting hard?
Suppose we relax the problem of counting proper colorings by counting weighted colorings as follows: every proper coloring gets weight 1 and every improper coloring gets weight $c^v$ where $c$ is some ...
- 4,661
27
votes
2
answers
794
views
Papers to credit for spectral partitioning of graphs
If $G=(V,E)$ is an undirected $d$-regular graph and $S$ is a subset of the vertices of cardinality $\leq |V|/2$, call the edge expansion of $S$ the quantity
$\phi(S) := \frac {Edges(S,V-S)}{d\cdot |S|...
- 4,902
27
votes
1
answer
918
views
Coloring complexity of graphs
Suppose $G$ is a graph with coloring number $d = \chi(G)$. Consider the following game between Alice and Bob. At each round, Alice picks a vertex, and Bob answers with a color in $\{1,\ldots,d-1\}$ ...
- 14.2k
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 ...
- 5,983
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,776
26
votes
2
answers
3k
views
Hamiltonicity of k-regular graphs
It is known that it is NP-complete to test whether a Hamiltonian cycle exists in a 3-regular graph, even if it is planar (Garey, Johnson, and Tarjan, SIAM J. Comput. 1976) or bipartite (Akiyama, ...
- 50.6k
26
votes
2
answers
5k
views
Natural CLIQUE to k-Color reduction
There is clearly a reduction from CLIQUE to k-Color because they're both NP-Complete. In fact, I can construct one by composing a reduction from CLIQUE to 3-SAT with a reduction from 3-SAT to k-Color. ...
- 448
25
votes
6
answers
3k
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
25
votes
1
answer
965
views
Is it still open to determine the complexity of computing the treewidth of planar graphs?
For a constant $k \in \mathbb{N}$, one can determine in linear time, given an input graph $G$, whether its treewidth is $\leq k$. However, when both $k$ and $G$ are given as input, the problem is NP-...
- 8,234
25
votes
1
answer
798
views
Regularity Lemma for Sparse Graphs
Szemeredi's Regularity Lemma says that every dense graph can be approximated as a union of $O(1)$ many bipartite expander graphs. More accurately, there's a partition of most vertices into $O(1)$ sets ...
- 11k
25
votes
1
answer
1k
views
An edge partitioning problem on cubic graphs
Has the complexity of the following problem been studied?
Input: a cubic (or $3$-regular) graph $G=(V,E)$, a natural upper bound $t$
Question: is there a partition of $E$ into $|E|/3$ parts of size $...
- 3,254
24
votes
5
answers
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 ...
- 1,581
24
votes
2
answers
570
views
Relation between hardness of recognition of a graph class and forbidden subgraph characterization
I'm considering graph classes that can be characterized by forbidden subgraphs.
If a graph class has a finite set of forbidden subgraphs, then there is a trivial polynomial time recognition algorithm ...
- 1,798
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
24
votes
3
answers
1k
views
NP complete graph problems about structural properties
(This question is a bit of a "survey".)
I'm currently working on a problem where I'm trying to partition the edges of a tournament into two sets, both of which are required to fulfill some ...
- 431
24
votes
2
answers
946
views
Is there a direct/natural reduction to count non-bipartite perfect matchings using the permanent?
Counting the number of perfect matchings in a bipartite graph is immediately reducible to computing the permanent. Since finding a perfect matching in a non-bipartite graph is in NP, there exists ...
- 2,024
24
votes
1
answer
882
views
Logspace algorithms on graphs with bounded tree width
Tree width measures how close a graph is to a tree. It is NP-hard to compute tree width. The best known approximation algorithm achieves $O(\sqrt{{\log}n})$ factor.
Courcelle's theorem states that ...
- 10.6k
24
votes
2
answers
898
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
24
votes
2
answers
1k
views
Is the Cheeger constant $\mathsf{NP}$-hard?
I have read in uncountably many articles that determining the Cheeger constant of a graph is $\mathsf{NP}$-hard. It seems to be a folk theorem, but I have never found either a quote or a proof for ...
- 343
24
votes
1
answer
599
views
Reconstruction Conjecture and Partial 2-trees
Reconstruction conjecture says that graphs (with at least three vertices) are determined uniquely by their vertex deleted subgraphs. This conjecture is five decades old.
Searching relevant literature,...
- 10.6k
23
votes
8
answers
3k
views
graphs from real-life problems
Where can I find graphs relevant to real-life problems?
Two repositories I know of are:
University of Florida's Sparse Matrix Collection
Bodlaender's TreewidthLib
- 4,661
23
votes
5
answers
2k
views
Good seating arrangements for sequence of meals and tables of size k for a group of people
Given a set $S$ of people I'd like to sit them for a sequence of meals at tables of size $k$. (Of course, there are enough tables to sit all $|S|$ for each meal.) I'd like to arrange this such that ...
- 333
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,786
23
votes
2
answers
678
views
Which graph parameters are NOT concentrated on random graphs?
It is well known that many important graph parameters show (strong) concentration on random graphs, at least in some range of the edge probability. Some typical examples are the chromatic number, ...
- 11.1k
23
votes
1
answer
536
views
How big is the variance of the treewidth of a random graph in G(n,p)?
I am trying to find how close $tw(G)$ and $E[tw(G)]$ really are, when $G \in G(n,p=c/n)$
and $c>1$ is a constant not depending on n (so $E[tw(G)] = \Theta(n)$). My estimate is that $tw(G) \leq E[tw(...
- 331
23
votes
1
answer
380
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,245
23
votes
0
answers
2k
views
$\Delta = 57, d=2$ Moore Graph
I am looking into the last open question regarding the existence of Moore Graphs of diameter 2. A problem that has been open in combinatorics for more than 55 years.
You may recall that Hoffman and ...
22
votes
8
answers
4k
views
NP-hard problems on paths
everybody knows there exist many decision problems which are NP-hard on general graphs, but I'm interested in problems that are even NP-hard when the underlying graph is a path. So, can you help me to ...
- 345
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