# Questions tagged [graph-theory]

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

1,273 questions
Filter by
Sorted by
Tagged with
16 views

### Efficient Graph Affinity Matrix Computation

I need to compute an affinity matrix for an unweighted undirected graph of related musical artists for the purposes of spectral clustering. Now, the most obvious affinity measure to use is shortest ...
167 views

### Complexity of finding the largest induced subgraph with all even degrees

What is the complexity of the following problem? Instance: Simple, undirected graph $G$, and a positive integer $k$. Question: Does $G$ have an induced subgraph on at least $k$ vertices, such that ...
39 views

### Complexity of recognizing unit distance graphs

A Graph is Unit Distance Embeddable (UDE) if it can be embedded in the plane such that every edge has a length of 1. A minor of a UDE graph is also UDE so by the Graph Minor theorem, there must be a ...
36 views

### Scheduling and routing

Given: $k > 1$ sales execs, each specializing in one of 4 lines of business (LOBs), where each exec works (sales and travel) at 7.5 hours / day $n > 1$ client sites. Constraints: Each ...
4k 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, ...
14 views

### Capacitated Vehicle Routing Problem with multiple pickups at some sites but constrained to max 1 pickup per vehicle per site

I am looking for literature or code for a variant of capacitated vehicle routing problem. The variance is that some sites have multiple items for pickup, but there is a constraint such that even if a ...
127 views

### How much does treewidth changes after removal of a path?

Let $G$ be a graph such that $\mathrm{tw}(G)=t$. Let $t' = \min\limits_{u,v \in V(G)} \max\limits_{P \text{ is a path from } u \text{ to } v} \mathrm{tw}(G - P)$. Then how small $t'$ can be? My ...
149 views

### Computing the edge orbits of a graph (and discussing definitions)

A (vertex) automorphism in a graph $G=(V,E)$ is a permutation $\sigma$ of the vertices that preserves adjacency, namely $\sigma(u) \sigma(v) \in E$ if and only if $uv \in E$. The automorphisms of a ...
168 views

### Lighting up all elements of a poset by toggling upsets

I consider the following game on a finite poset $(P, <)$. At each point of the game, I have a set of elements $S$ of the poset which are "on", and all others are "off". Initially $S = \emptyset$. ...
472 views

### Dijkstra parallelization

I'd like to know what is the best method to parallelize the Dijkstra algorithm. Thanks.
97 views

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 ...
114 views

### Breaking cycles in network graph by adding nodes and rerouting edges

I have a quite "common" need : making a directed graph (with one or several cycles) a directed acyclic graph (DAG). But the way I want to achieve it is, I guess, way more specific : I would like to ...
87 views

### How hard is it to determine ex(n,G)?

Define the extremal Turán function $ex(n,G)$ of a graph $G$ as the most edges a graph on $n$ vertices can have without having a subgraph that is isomorphic to $G$. This function is known ...
9k 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 ...
148 views

### Find the shortest s-t trail(edge disjoint path) in a graph with negative weight edges

A walk in a graph is a finite or infinite sequence of edges which joins a sequence of vertices. A trail is a walk in which all edges are distinct. Note that a trial may visit a vertex multiple times ...
86 views

### Finding simple fixed length paths in directed graphs

Is there an efficient algorithm to enumerate unique simple fixed-length paths (of size $k$) in directed graphs? What would be its time complexity?
119 views

### The source of the modular decomposition graph

When introducing graph modular decomposition, most authors use the 11-vertex graph, which I copy from wikipedia. The question is who is (are) the original designer of it. (I'm not asking who drew ...
652 views

### Regularity Lemma for Sparse Graphs

Szemeredi's Regularity Lemma says that every dense graph can be approximated as a union of $O(1)$ many bipartite expander graphs. More accurately, there's a partition of most vertices into $O(1)$ sets ...
101 views

### Network Reliability Problem

Network reliability, in which we are given an undirected graph $G$ with a failure probability $p_e$ for each edge and we are asked to calculate the probability that the network becomes disconnected ...
67 views

84 views

### Which computational framework lies behind the Chinese “Social Credit System”?

BACKGROUND The Social Credit System is a data-driven reputation system which draws on several sources to label various entities, namely businesses and individual citizens, with a trustworthiness ...
67 views

### Unknown gaps in computation models

I'm looking for computatuon models where it is known that there are problems that we can solve in time T1 and T2. where T1 is smaller then T2 and it is unknown if there are problems where their ...
87 views

### finding maximum weight subgraph

My graph is as follows: I need to find a maximum weight subgraph. The problem is as follows: There are n Vectex clusters, and in every Vextex cluster, there are some vertexes. For two vertexes in ...
### Problem of determining if a $4$ connected graph has $k$ Hamiltonian cycles
Definition: Define the $k$-HamiltonianCycles problem as the decision problem that asks if a given graph has at least $k$ distinct Hamiltonian cycles. Question: Is there some constant $k$ so that the \$...