Questions tagged [graph-theory]
Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
1,512
questions
8
votes
1
answer
282
views
Diameter Constrained Minimum Spanning Graph
The idea of a diameter constrained MST is that you keep all vertices connected and within a certain distance of each other. But all papers I've seen keep the requirement that you produce a tree, when ...
- 183
6
votes
1
answer
465
views
From edge-disjoint paths to independent paths
Let $\mathcal{G}_k$ denote the set of all graphs that contain two vertices $x,y$
and $k$ edge-disjoint $x-y$ paths.
Define $f(k)$ to be the maximum such that for every graph $G\in \mathcal{G}_k$
...
- 5,026
7
votes
1
answer
395
views
multi-commodity flow acyclic digraphs
I am faced with the following question on max. integer multiflow:
INSTANCE: An acyclic directed graph G=(V,E), a capacity function c:E→N, k pairs of vertices (si,ti) and a demand function d:{1,…,k}→N....
- 149
2
votes
1
answer
156
views
Edge labeling in $K_{m,n}$
Background: I have been working on the following problem and was curious if this has come up before, what is it called in the literature, and what are previously tried methods? The motivation for ...
- 746
2
votes
1
answer
161
views
Inferring Cartesian position from a set of nodes where only distance is known
I am attempting to resolve a problem of inferring Cartesian position from distance. I have a set of nodes arbitrarily but statically positioned on a 2-D plane. Every node is aware of its position ...
- 123
3
votes
1
answer
338
views
reduction of maximum independet set to minimum distance of code
Is there a reference for direct reduction of computing maximum independent set of a suitably constructed graph to computing minimum distance of a linear code when the code is specified by its parity ...
- 2,208
7
votes
3
answers
535
views
Algebraic formulation for packing problem
My question is regarding the algebraic formulation for packing problems in graphs.
Taking an example, suppose I am interested in the problem of finding if there is a packing of k edge disjoint ...
- 664
8
votes
2
answers
2k
views
Edge-weight updates in all pair shortest path problem
I want to calculate all-pairs shortest paths on a graph with roughly 50,000 nodes representing a city-wide road network. An answer to my previous question led me to Hiroki Yanagisawa's paper "A multi-...
- 175
8
votes
3
answers
2k
views
Finding triangles in a graph: other approaches besides property testing?
We're working on a paper that presents some algorithms for finding triangles and network motifs (constant size subgraphs, also known as graphlets) in a distributed setting. We characterize the ...
- 711
12
votes
4
answers
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/...
- 3,430
13
votes
1
answer
295
views
Graph embedding which maximizes minimum angle
Given a planar graph, one can embed it in linear time crossing free into an $n \times n$ grid.
I am interested whether any efficient algorithms are known to straight line embed a planar graph ...
- 133
13
votes
1
answer
268
views
The complexity of the dominating set problem in specific subclasses of chordal graphs
I am interested in the complexity of the dominating set problem (DSP) in some specific graph classes which are subclasses of chordal graphs.
A graph is an undirected path graph if it is the vertex-...
- 2,113
6
votes
1
answer
897
views
Tree width of a particular graph
What is the tree-width of the graph $G = (V_1 \cup V_2 \cup \dotsb V_n, E)$ where the connected components of an induced subgraph of any neighboring set of vertices (i.e. $G[V_i \cup V_j], i = j - 1$)...
- 746
0
votes
3
answers
272
views
representing code path as graph walks.. a provable graph walk?
I am looking into some security analysis of arbitrary code which is represented as a graph
Are there any papers on whcih graphs walks are valid code paths ?
Or a provable graph walk which is shorter ...
- 19
4
votes
1
answer
289
views
On planarity in two related graphs
Let $A$ be an $(n\times n)$-matrix with entries from $\{0,1\}$ and $B$ its biadjacency matrix $B = \begin{pmatrix} 0 & A\\ A^t & 0 \end{pmatrix}$.
My simple question is: Is there a ...
- 615
6
votes
0
answers
105
views
Evaluate polynomial involving nearly-minimal graph cuts
So you want to evaluate the polynomial
$$
p(x) = \sum_{C} x^{|C|}
$$
where $C$ ranges over all nearly-minimum cuts in a graph (say, all minimal cuts of size $\alpha c$ where $c$ is the edge ...
- 3,478
3
votes
0
answers
297
views
Graph connectivity related game [closed]
I was considering the following game on an undirected unweighted graph $G=(V,E)$ (not necessarily simple). Two players, Police and Runaway, take moves in turn. Police can cut an arbitrary subset of ...
- 629
-3
votes
1
answer
136
views
Semi-supervised learning on graphs
What is semi-supervised learning on graphs? We have been told that if we just have a function which has an input graph, or a given graph with labeled nodes, we should be able to predict labels on ...
- 135
6
votes
1
answer
556
views
On the faces of the multicommodity flow polytope
Consider the multicommodity flow problem on an undirected graph with k source-destination pairs and specified capacity constraints on the edges. The set of concurrently achievable flows $(R_1,R_2,...,...
- 453
18
votes
3
answers
1k
views
Solving Superstring Exactly
What is known about exact complexity of the shortest superstring problem? Can it be solved faster than $O^*(2^n)$? Are there known algorithms that solve shortest superstring without reducing to TSP?
...
- 2,163
7
votes
1
answer
603
views
SDP and chromatic number upper bounds
Are there any references for finding non-trivial upper bounds to chromatic number using semidefinite programming?
- 2,208
-1
votes
1
answer
196
views
Invariance in Property Testing
A property is said to be invariant under a permutation $\pi$ if permuting the data points by this permutation leaves the property unchanged.
Invariance under permutations seems to help with property ...
- 4,001
0
votes
0
answers
326
views
On Vertex Coloring of Permutation Graph and Comparability Graph and 2-SAT
I have 2 questions.
Firstly, I am not sure about differences between Permutaion Graphs and Comparability Graphs. The latter graph class includes the other class. Is there a specific example of graph ...
- 1
2
votes
1
answer
1k
views
TSP in bounded tree-width (or bounded branch width) graphs
I see there are some papers/thesis which says TSP is solvable in $O(n)$ in bounded tree-width graphs and some of them implicitly refer to Cook and Seymour (not exact paper just said that they solve it)...
- 3,430
10
votes
2
answers
557
views
Amplitude of Random Cubic Graphs
Consider a connected random cubic graph $G=(V,E)$ of $n =|V|$ vertices, drawn from $G(n, 3$-reg$)$ (as defined here, i.e. $3n$ is even and any two graphs have the same probability).
Of course there ...
- 6,695
17
votes
1
answer
556
views
Connectivity of graphs by edge and vertex removal
Let us say that a graph $G$ is $(a,b)$-connected if the removal of any $a$ vertices and any $b$ edges from $G$ leaves always a connected graph. For example, a $k$-connected graph, according to the ...
- 1,414
17
votes
2
answers
4k
views
Finding k shortest Paths with Eppstein's Algorithm
I'm trying to figure out how the Path Graph $P(G)$ according to Eppstein's Algorithm in this paper works
and how I can reconstruct the $k$ shortest paths from $s$ to $t$ with the corresponding heap ...
- 273
10
votes
1
answer
719
views
Voronoi diagram in a graph
Let $G$ be a graph with (positively) weighted edges.
I want to define the Voronoi diagram for a set of nodes/sites $S$, to
associate with a
node $v \in S$
the subgraph $R(v)$ of $G$ induced by all the ...
- 3,703
16
votes
1
answer
770
views
Making a minimum-width tree decomposition lean in polynomial time
As is well known, a tree decomposition of a graph $G$ consists of a tree $T$ with an associated bag $T_v \subseteq V(G)$ for each vertex $v \in V(T)$, which satisfies the following conditions:
Every ...
- 5,245
5
votes
1
answer
541
views
Bipartite maximum matching size from eigenvalues
Supposing we know the adjacency matrix $\mathcal{A}_{G}$ of a given regular (or irregular) bipartite graph $G$. Are there good lower and upper bounds to the size of maximum matching from the graph's ...
- 2,208
19
votes
2
answers
870
views
Axioms for Shortest Paths
Suppose we have an undirected weighted graph $G = (V, E, w)$ (with non-negative weights). Let us assume that all shortest paths in $G$ are unique. Suppose we have these $\binom{n}{2}$ paths (sequences ...
- 1,559
7
votes
2
answers
589
views
Capacitated multiple vehicle routing problem with handovers
I'm looking for literature about a variant of the capacitated vehicle/fleet routing problem (a.k.a. VRP, CVRP, etc.) that takes into account the possibility of handovers between multiple vehicles, i.e....
- 121
7
votes
2
answers
728
views
Variants of Cluster-Vertex-Deletion problem
The Unweighted Cluster-Vertex-Deletion problem is the following:
Input: An undirected graph G = (V, E) and a nonnegative number k
Output: Is there a subset X ⊆ V with |X| ≤ k such that deleting all ...
- 531
10
votes
1
answer
351
views
Connecting cells by line and column permutations in a finite grid
I'd like to know whether the following simple problem has been studied before and if any solution is known.
Let G be a finite (MxN) grid, S a subset of G's cells (the "crumbs"). Two crumbs are said ...
- 103
17
votes
2
answers
1k
views
Forbidden minors for bounded treewidth graphs
This question is similar to one of my previous questions. It is known that $K_{t+2}$ is a forbidden minor for graphs of treewidth at most $t$.
Is there a nicely-constructed, parameterized, ...
- 10.5k
1
vote
1
answer
335
views
2D grid placement problem
Data for the problem:
2D grid(lattice) of size NxN
n nodes placed on the grid:node_1,node_2,…node_n
Each of nodes contain some data:
a. node_i is presented by 3 parameters (x_i,y_i,t_i)
b. ...
- 189
10
votes
1
answer
356
views
Regular high-girth graph with a "locally uniform" total order on nodes
Definitions
Let $\epsilon > 0$ and let $d$, $r$, and $g$ be positive integers (with $g > 2r+1$).
Let $G = (V,E)$ be a simple, $d$-regular, undirected, finite graph with girth at least $g$.
Let $\...
- 11.4k
6
votes
1
answer
265
views
Self-intersecting walk in expander graphs
Consider a random walk in an expander graph.
How much time it typically takes to visit the same vertex twice.
It seems to me that it should be something between $\sqrt{n}$ to $\sqrt{n}\log n$.
Is ...
- 759
14
votes
4
answers
730
views
P-complete problems on trees
This question is related to one of my previous questions, NP-hard problems on trees.
I am looking for problems that are P-complete on trees.
- 10.5k
10
votes
1
answer
594
views
Can such a matrix exist?
During my work i came up with the following problem:
I am trying to find an $n \times n$ $(0,1)$-matrix $M$, for any $n > 3$, with the following properties:
The determinant of $M$ is even.
For ...
- 615
17
votes
1
answer
2k
views
Forbidden minors for bounded genus graphs
It is well known that $K_5$ and $K_{3,3}$ are forbidden minors for planar graphs. There are hundreds of forbidden minors for graphs embeddable on a torus. The number of forbidden minors for graphs ...
- 10.5k
3
votes
1
answer
2k
views
How to determine whether there is exactly one simple path between two nodes in a graph
Given an undirected sparse graph G and a list of queries (each query consisting of two nodes), how to determine if there exists exactly one simple path between them (for each query) ? I have a (...
- 79
10
votes
1
answer
457
views
Hardness of approximating fractional chromatic number on bounded degree graphs
Is it apx-hard to approximate fractional chromatic number on bounded degree graphs?
- 1,574
1
vote
2
answers
261
views
Any Graph is a Model (! or ?)
I know this could be considered a pointless question. However despite I am quite convinced that any possible model (i.e. UML, SysML, natural language, math, etc.) can be defined by means of a graph I ...
- 123
20
votes
2
answers
2k
views
Data structure for shortest paths
Let $G$ be an unweighted undirected graph with $n$ vertices and $m$ edges. Is it possible to preprocess $G$ and produce a data structure of size $m \cdot \mathrm{polylog}(n)$ so that it can answer ...
- 1,559
17
votes
2
answers
640
views
Is there any problem in $\mathsf{\Sigma^P_2}$ which is solvable in bounded tree width graphs?
I'm looking for a problem which belongs to $\mathsf{\Sigma^P_2}$ in general graphs but is in $\mathsf{P}$ in bounded tree width graphs, In fact I think this problems are harder than using normal ...
- 3,430
7
votes
2
answers
425
views
Are there nice generalizations of SPQR trees to k-connected components for k>3?
I'm curious how one should best understand the connections between the k-connected components when $G$ has minimum cuts of size $k>3$, or perhaps approximate minimum cuts produced by Karger's ...
- 1,196
20
votes
1
answer
7k
views
Partition a graph into node-disjoint cycles
Related problem: Veblen’s Theorem states that "A graph admits a cycle decomposition if and only if it is even". The cycles are edge disjoint, but not necessarily node disjoint. Put another way, "The ...
- 1,433
10
votes
1
answer
441
views
Finding spanning spiders
Is there a polynomial-time algorithm to find—if one exists—a spanning spider
of a given graph $G$? A spider is a tree with at most one node with degree greater than 2:
&...
- 3,703
4
votes
3
answers
3k
views
Maximum-clique practical applications
The question is: what are examples of clique problem applications? I mean, what problems can be solved by reducing to clique problem (sorry for tautology)?
All I came with is finding social cliques: ...
- 41