Questions tagged [graph-theory]
Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
151
questions
36
votes
9answers
12k 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, ...
19
votes
3answers
9k views
Counting the Number of Simple Paths in Undirected Graph
How can I go about determining the number of unique simple paths within an undirected graph? Either for a certain length, or a range of acceptable lengths.
Recall that a simple path is a path with no ...
23
votes
8answers
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
20
votes
6answers
3k views
Network / Social network analysis visualization tools?
I was using Jung ( http://jung.sourceforge.net/ ) to visualize page rank and found it a little slow and difficult to scale it beyond 100 nodes. I was wondering what other tools people use for network /...
28
votes
4answers
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 ...
9
votes
5answers
2k views
Transitivity check vs. Transitive Closure
Is checking transitivity of a digraph not easier than (in terms of asymptotic complexity) taking the transitive closure of the digraph? Do we know any lower bound better than $\Omega(n^2)$ to ...
2
votes
1answer
534 views
techniques or examples of analyzing a series of graphs
Let there be a sequence of graphs $G_1, G_2, G_3, ...$ constructed using some particular approach or algorithm. in this particular case $G_n$ is constructed by modifying $G_{n-1}$ in some "...
31
votes
5answers
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 ...
31
votes
0answers
5k 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\}$.
(...
35
votes
3answers
4k 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 ...
25
votes
1answer
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 $...
28
votes
3answers
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 ...
20
votes
2answers
1k 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 ...
20
votes
2answers
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 ...
15
votes
5answers
869 views
References for Modular Decomposition
What are good papers/books to better understand the power of Modular Decomposition and its properties?
I'm particularly interested in algorithmic aspects of Modular Decomposition. I have heard that ...
8
votes
3answers
2k views
What kind of mathematical background is needed for graph theory?
It is going to be the first time for me to learn graph theory. What kind of mathematical background do I need to prepare master theses about this subject in following years?
Which subjects should be ...
34
votes
3answers
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 ...
30
votes
1answer
742 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 ...
22
votes
8answers
3k 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 ...
17
votes
2answers
2k views
Gentle introduction to graph isomorphism for bounded valance graphs
I am reading about classes of graphs for which Graph Isomorphism ($GI$) is in $P$. One of such case is graphs of bounded valence (maximum over degree of each vertex) as explained here. But I found it ...
12
votes
4answers
3k views
Incremental Maximum Flow in Dynamic graphs
I'm looking for a fast algorithm to compute maximum flow in dynamic graphs. i.e given a graph $G=(V,E)$ and $s,t\in V$ we have maximum flow $F$ in $G$ from $s$ to the $t$. Then new/old node $u$ added/...
15
votes
6answers
487 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 ...
11
votes
2answers
811 views
For which families of graphs is Generalized Geography in $P$?
As @Marzio mentioned, the following game is known as Generalized Geography.
Given a graph $G=(V,E)$ and a starting vertex $v \in V$, the game is defined as follows:
At each turn (two players ...
6
votes
4answers
801 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
26
votes
2answers
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 ...
12
votes
2answers
655 views
Number of vertices present in all maximum matchings
Given a graph $G$, we need to find the cardinality of the largest set of vertices so that each of them are present in every maximum matching possible.
Is there a solution beside the obvious remove ...
11
votes
3answers
415 views
Does $\delta^+(G)+\delta^-(G) \geq n$ imply strong connectivity?
Denote by $\delta^+(G)$ the minimal out degree in $G$, and by $\delta^-(G)$ the minimal in-degree.
In a related question, I've mentioned the Ghouila-Houri extension of Dirac's theorem on Hamiltonian ...
11
votes
4answers
687 views
Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs
Crossposted from MO.
Let $C$ be a graph class defined by a finite
number of forbidden induced subgraphs, all
of which are cyclic (contain at least one cycle).
Are there NP-hard graph problems that ...
8
votes
2answers
2k views
Upper bounds on the length of longest simple path in non-Hamiltonian graph?
Hamiltonian cycle problem is $NP$-complete on cubic planar bipartite graphs. I'm interested in upper bounds on the length of the longest simple path in non-Hamiltonian cubic planar bipartite graphs.
...
asked Nov 15 '10 at 20:07
Mohammad Al-Turkistany
19.8k4 gold badges53 silver badges136 bronze badges
1
vote
1answer
314 views
in SAT resolution proofs, are all DAGs possible? [closed]
these are some probably very hard but possibly significant and deep questions related to an unusual but intriguing possible "recursive" construction/formulation in SAT, with some important "structure" ...
23
votes
3answers
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 ...
19
votes
1answer
2k views
Is the dominating set problem restricted to planar bipartite graphs of maximum degree 3 NP-complete?
Does anyone know about an NP-completeness result for the DOMINATING SET problem in graphs, restricted to the class of planar bipartite graphs of maximum degree 3?
I know it is NP-complete for the ...
8
votes
1answer
584 views
An interesting variant of maximum matching problem
Given a graph $G(V,E)$, the classic maximum matching problem is choosing the maximum subset of edges $M$ s.t., for each edge $(u,v) \in M$, $d(u)=d(v)=1$.
Has anybody studied the following variant? ...
13
votes
1answer
515 views
Partition into interval graphs
Suppose there is a graph $G=(V,E)$. I want to test if $V$ can be partitioned into two disjoint sets $V_1$ and $V_2$ such that the subgraphs induced by $V_1$ and $V_2$ are unit interval graphs.
I know ...
11
votes
2answers
1k views
How to generate graphs with known optimal vertex cover
I'm looking for a way to generate graphs so that the optimal vertex cover is known. There are no restrictions on the number of nodes or edges, only that the graph is completely connected.
the idea is ...
9
votes
2answers
518 views
The ODD EVEN DELTA problem
Let $G = ( V, E )$ be a graph. Let $k \leq |V|$ be an integer. Let $O_k$ be the number of edge induced subgraphs of $G$ having $k$ vertices and an odd number of edges. Let $E_k$ be the number of edge ...
8
votes
1answer
691 views
What is complexity of this max-edge subgraph problem?
While discussing the question I had asked here, @NealYoung and I encounter another problem, which is to judge complexity of the problem below:
Given a connected undirected graph, finding a maximum-...
5
votes
1answer
667 views
Number of subgraphs with a given number of nodes
Let $G = ( V_G, E_G )$ be a graph. Let $E_H \subseteq E_G$.
The subgraph of $G$ edge-induced by $E_H$ is $H = ( V_H, E_H)$, where
$V_H = \{ v \in V_G : \exists ( u, w ) \in E_H\ v = u \lor v = w \}$
...
5
votes
1answer
201 views
Finding a simple dual of a simple graph in some surface
Given a cellular embedding of a graph on a surface (by 'surface' I mean here a sphere with some $n\geq 0$ handles), one can define a dual multigraph by treating the faces of the original graph ...
62
votes
5answers
5k 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 ...
25
votes
3answers
975 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 ...
24
votes
6answers
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. ...
41
votes
3answers
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})}$. ...
asked Nov 25 '13 at 12:00
Mohammad Al-Turkistany
19.8k4 gold badges53 silver badges136 bronze badges
24
votes
2answers
853 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)$-...
24
votes
5answers
10k 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 ...
17
votes
2answers
1k views
Cover Time of Directed Graphs
Given a random walk on a graph the cover time is the first time (expected number of steps) that every vertex has been hit (covered) by the walk. For connected undirected graphs, the cover time is ...
10
votes
4answers
682 views
What are the root difficulties in going from graphs to hypergraphs?
There are many examples in combinatorics and computer science where we can analyze a graph-theoretic problem but for the problem's hypergraph analog, our tools are lacking. Why do you think problems ...
25
votes
2answers
4k 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. ...
16
votes
4answers
2k views
Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs
I'm looking for problems which are known to be NPC for directed graphs but has a polynomial algorithm for undirected graphs.
I've seen the question regarding the other way around here “Directed” ...
15
votes
2answers
673 views
GI-hard graph problem not known to be $NP$-complete
Graph Isomorphism ($GI$) is good candidate for $NP$-intermediate problem. $NP$-intermediate problems exist unless $P=NP$. I'm looking for natural problem that is hard for $GI$ under Karp reduction (A ...
