Questions tagged [graph-theory]
Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
1,512
questions
25
votes
2
answers
1k
views
Why Ramanujan graphs are 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?
- 10.9k
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,820
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
20
votes
6
answers
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 /...
2
votes
1
answer
446
views
Finding islands of vertices in a network of roads containing one-way streets [closed]
I am working on GIS project where we are making use of road maps that may contain one-way streets.
We are writing some debugging tools one of which I want to design to find "Islands". This would ...
- 123
2
votes
1
answer
828
views
Heuristics for the minimum-weight $k$-clique problem
Hello
Does someone have an idea for heuristics for the problem:
Given undirected weighted(weights on edges) complete
graph $G(V,E)[|V|=n,|E| = m]$, find a clique of size $k < n$(k is number of ...
- 189
10
votes
1
answer
2k
views
Pruning a strongly connected digraph
Given a strongly connected digraph G with weighted edges, I would like to identify edges that are provably not part of any minimal strongly connected subgraph (MSCS) of G.
One method for finding such ...
- 285
4
votes
2
answers
2k
views
Diameter of a graph with O(|V|) edges
What's the minimum diameter of a connected undirected graph with |V| vertices and O(|V|) edges?
- 696
7
votes
3
answers
880
views
Non-rooted MST of directed graph
I've found a problem that boils down to this: I need to find the non-rooted MST of a directed weighted graph. In other words, I need to find the minimal set of edges such that from any one node in the ...
- 285
10
votes
1
answer
1k
views
Finding short and fat paths
Motivation: In standard augmenting path maxflow algorithms, the inner loop requires finding paths from source to sink in a directed, weighted graph. Theoretically, it is well-known that in order for ...
- 671
10
votes
2
answers
656
views
Approximating non-trivial graph automorphism?
Graph automorphism is a permutation of graph nodes that induces a bijection on the edge set $E$. Formally, It is a permutation $f$ of nodes such $(u,v)\in E$ iff $(f(u),f(v))\in E$
Define an ...
- 20.7k
13
votes
1
answer
529
views
Is "Is a permutation p an automorphism of a graph in my set?" NP-complete?
Suppose we have a set S of graphs (finite graphs, but an infinite number of them) and a group P of permutations that acts on S.
Instance: A permutation p in P.
Question: Does there exist a graph g in ...
10
votes
4
answers
516
views
Interesting functions on graphs that can be efficiently maximized.
Say that I have a weighted graph $G = (V,E,w)$ such that $w:E\rightarrow [-1,1]$ is the weighting function -- note that negative weights are allowed.
Say that $f:2^V\rightarrow \mathbb{R}$ defines a ...
- 9,820
14
votes
1
answer
350
views
Generating Graphs with Trivial Automorphisms
I'm revising some cryptographic model. To show its inadequacy, I've devised a contrived protocol based on graph isomorphism.
It is "commonplace" (yet controversial!) to assume the existence ...
- 16.3k
10
votes
1
answer
320
views
CSPs with unbounded fractional hypertree width
At SODA 2006, Martin Grohe and D$\acute{\rm a}$niel Marx's paper "Constraint solving via fractional edge covers" (ACM citation) showed that for the class of hypergraphs $H$ with bounded fractional ...
- 5,953
1
vote
0
answers
2k
views
DAG partitioning to subgraphs
Given a DAG with $|V| = n$ and has $s$ sources, we have to present subgraphs such that each subgraph has approximately $k_1=\sqrt{s}$ sources and approximately $k_2=\sqrt{n}$ nodes.
(Note: ...
6
votes
1
answer
5k
views
What is the computational complexity of the PageRank problem?
I was just wondering what the complexity of the PageRank problem is. A description can be found here: http://en.wikipedia.org/wiki/PageRank . (I am referring to the problem that is solved by the ...
user1338
8
votes
1
answer
771
views
Max-clique in line graph of hypergraph
Suppose we have a multigraph (later, a multihypergraph). An edge-clique is a set of edges which all pairwise intersect (have at least one common vertex). Then any edge-clique $C$ in a multigraph ...
- 1,100
11
votes
3
answers
2k
views
Extension to the Stable Marriage Problem ?
This may sound more like a social sciences question more than a TCS one, but it is not. When reading "Randomized Algorithms" which describes the Stable Marriage Problem, one can read the following (...
- 111
4
votes
0
answers
229
views
Follow-up on Nair/Tetali's Correlation Decay Tree for hypergraphs?
I'm wondering if anybody has followed up on Nair/Tetali's correlation decay tree construction for hypergraphs. I didn't find anything relevant in back-citation on google scholar. Interesting question ...
- 4,651
6
votes
0
answers
215
views
Further question on hardness of node partitioning under shortest path constraint
This question first appeared at Hardness of node partitioning under shortest path constraint and I restate it here
Given a direct graph $G=(V,E)$. $\forall (i,j) \in E$, there is a weight $w(i,j) \...
- 283
1
vote
1
answer
3k
views
Pre-order traversal on a search tree
The following is from this year's CS GRE practice test. I've worked through the test and I've been able to understand every question except for this one. Can anyone help me understand what's going on ...
- 113
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.5k
27
votes
3
answers
980
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,651
4
votes
1
answer
632
views
Hardness of node partitioning under shortest path constraint
Given a direct graph $G=(V,E)$. $\forall (i,j) \in E$, there is a weight $w(i,j) \in R$ (negative weight is possible). A label $l(i)$ is associated with each node $i \in V$. How to assign $k$ (or less)...
- 283
15
votes
1
answer
5k
views
What is the correct definition of $k$-tree?
As the title says, what is the correct definition of $k$-tree? There are several papers that talk about $k$-trees and partial $k$-trees as alternative definitions for graphs with bounded treewidth, ...
- 151
5
votes
1
answer
226
views
How can one construct a densest graph with no k-clique?
Given integers $k$ and $n$ with $2 \le k < n$,
how does one construct a graph on $n$ vertices
that contains no $k$-clique and has the maximal
number of edges?
This sounds like basic ...
- 18.8k
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.5k
2
votes
1
answer
274
views
Number of Vertex Covers and Permanent
Is there any relationship between the number of vertex covers of a graph $G$ and the permanent of $G$'s adjacency matrix?
- 6,695
2
votes
2
answers
2k
views
polygonal triangulation and 3-colorability
Lets define polygonal triangulation a triangulation which has a hamiltonian cycle.
It's easy to see that any polygonal triangulation is 3-colorable since any triangulation of a polygon is 3-colorable....
- 43
17
votes
3
answers
1k
views
Properties of Random Directed Graphs with Fixed Out-Degree
I am interested in properties of random directed graphs with fixed out-degree $d$. I am imagining a random graph model where each vertex chooses d neighbors (say, with replacement) u.a.r.
...
- 11.9k
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
966
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,953
-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
5k
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
903
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
503
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.8k
11
votes
1
answer
448
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
859
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
386
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
979
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
718
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.5k
17
votes
1
answer
598
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
724
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.7k
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.7k