# Questions tagged [graph-theory]

Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.

1,512 questions
Filter by
Sorted by
Tagged with
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
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
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
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 ...
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
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
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
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
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
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
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
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
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$)...
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
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
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
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 ...
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
556 views

• 11.4k
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
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
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
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
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
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
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 ...
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
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
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
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
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