Questions tagged [graph-theory]
Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
175
questions
40
votes
10answers
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, ...
36
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 ...
20
votes
3answers
11k 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 ...
8
votes
3answers
811 views
Is this vertex ordering optimization NP-Hard?
Could you help me to prove that the following problem is NP-hard?
Problem. Given an undirected graph $G=(V,E)$, find an ordering of the nodes such that $\sum\limits_{v\in V}|succ(v)|\times|pred(v)|$ ...
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 ...
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 ...
5
votes
1answer
260 views
Is this edge orientation optimization problem NP-hard?
Is the following optimization problem NP-hard?
Problem. For a given undirected graph $G=(V,E)$, find an orientation of the edges that minimizes the objective value $\sum_\limits{v\in V} ~d_{out}(v)\...
2
votes
1answer
550 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 ...
25
votes
3answers
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 ...
32
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\}$.
(...
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 $...
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 ...
9
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 ...
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 ...
21
votes
2answers
1k views
Is feedback vertex set problem solvable in polynomial time for 3-degree bounded graphs?
Feedback Vertex Set (FVS) 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 ...
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
884 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 ...
35
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 ...
31
votes
1answer
788 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
4k 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
492 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 ...
14
votes
3answers
4k views
Is there an online-algorithm to keep track of components in a changing undirected graph?
Problem
I have an undirected graph (with multi-edges), which will change over time, nodes and edges may be inserted and deleted. On each modification of the graph, I have to update the connected ...
11
votes
2answers
905 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 ...
7
votes
4answers
969 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
27
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 ...
24
votes
3answers
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 ...
11
votes
4answers
713 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 ...
11
votes
3answers
426 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 ...
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
20.5k4 gold badges57 silver badges144 bronze badges
1
vote
1answer
322 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" ...
19
votes
1answer
3k 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 ...
12
votes
2answers
751 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 ...
8
votes
1answer
597 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? ...
7
votes
3answers
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 ...
7
votes
2answers
2k views
Partition a graph into 2 connected subgraphs
I'm stumped on a sub problem that I'm working on for my thesis. I need to be able to partition a graph into 2 connected subgraphs of almost equal size. So if there are $m$ vertices in $G$, subgraphs $...
13
votes
1answer
524 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 ...
12
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
536 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
738 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-...
6
votes
2answers
397 views
Is that edge orientation optimization problem NP-hard?
Is the following optimization problem NP-hard?
Problem. For a given undirected graph $G=(V,E)$, find an orientation of the edges that minimizes the objective value $\sum_\limits{u\in V} ~\left( d_{...
5
votes
1answer
703 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
207 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 ...
4
votes
1answer
302 views
Pagerank in directed *acyclic* graphs (DAG)
I deal with pagerank computations on large directed acyclic graphs (DAG).
I found no reference to work on this specific case, only some work on pagerank in more specific cases, e.g., PageRank of Scale ...
3
votes
1answer
343 views
Does faster exact algorithm for counting independent sets in comparability graphs than general graph exisits?
Sorry for not-precise question. :-(
There are several papers concerning exact counting (maximum) independent sets in general graphs. Actually, they concerns counting of solutions of 2SAT. The best of ...