Questions tagged [graph-theory]
Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
1,479
questions
5
votes
1
answer
166
views
Known property? Maximum radius of connected induced subgraph
I was wondering if the following graph property has a name and has been researched:
Consider any connected induced subgraph $H \subseteq G$.
Then $r(G)$ denotes the maximum radius of any such $H$.
I ...
- 238
-2
votes
1
answer
268
views
Minimum vertex cover and odd cycles
Suppose we have a graph G without odd cycles. Consider the minimum vertex cover problem of G formulated as a linear programming problem, that is for each vertex $v_{i}$ we have the variable $x_{i}$, ...
1
vote
1
answer
514
views
Fast Computation of First k Eigenvectors of Graph Laplacian
I'm looking for references for the following; Given the unnormalized Laplacian matrix of a graph $L = D - A, ~ L \in \mathbb{R}^{n\times n}$
Algorithm(s) to efficiently estimate the first $k$ (...
3
votes
0
answers
112
views
Isomorphic subforest problem
I recently read that the following problem is NP-Complete:
Given a tree $T$, and a forest $F$, is there a subgraph of $T$ isomorphic to $F$?
The reference provide was to the textbook “Computers and ...
- 507
2
votes
0
answers
198
views
How to approach the "traveling salesman problem" with cost changing every time salesman reaches a new city
Let's say instead of finding the shortest path we have to maximize the profit in a year of the salesman under the following constraints.
Salesman can go to a different city only on weekends, all ...
- 121
0
votes
1
answer
70
views
Reduction graph to planar bounded treewidth and bounded diameter graph
We got reduction graph to planar bounded treewidth graph,
but this is unlikely to be true.
Let $H$, the planarizing gadget, be planar graph with four
distinguished vertices $u,u',v,v'$ on the outer ...
- 1,955
4
votes
1
answer
147
views
Hardness of finding if a vertex lies on a simple directed path between two vertices
Given a directed graph $G = (V, E)$ and three vertices $u, v, w \in V$. Is it NP-Hard to find whether there is a simple path from $u$ to $v$ passing through $w$?
I found a couple of hardness ...
- 241
2
votes
1
answer
65
views
Maximum subgraph problem with unknown complexity
Let $Q$ be a polynomial time decidable graph property. In a graph let us call a subgraph $S$ a $Q$-subgraph, if $S$ has the property $Q$. Consider the following optimization problem:
Maximum $Q$-...
- 10.7k
5
votes
1
answer
203
views
Is this a known problem, and is it #P-complete?
Let $G=(V,E)$ be an undirected graph. What I call a selection function of $G$ is a partial function $f:V \to E$ such that for every node $v$, if $f(v)$ is defined then it is one of the adjacent edges ...
- 1,095
1
vote
1
answer
80
views
Existence of graphs of every order related to Barnette’s conjecture
Consider the class C3CBP of $3$-connected cubic bipartite planar graphs. They form the class on which the (in)famous Barnette’s conjecture is based. My interest in C3CBP graphs is somewhat orthogonal ...
- 2,267
9
votes
2
answers
134
views
Complexity of finding an edge set yielding specified vertex degrees
I'm trying to figure out if the following two problems are known in general to be in P or NP-complete:
Q1: Given a graph $G=(V,E)$ and integers $d_i,\,1\leq\,i\leq|V|$, does there exist a subset $E'\...
- 285
6
votes
2
answers
160
views
$NP$-Completeness of $\epsilon$-balanced graph partitioning for fixed $\epsilon$
Consider this graph partitioning problem: Let $G = (V, E)$ be a simple undirected graph and $0 \leq \epsilon \leq 1, M \geq 0$ be constants. Are there disjoint subsets $V_1, V_2$ with $V = V_1 \cup ...
- 71
14
votes
0
answers
171
views
NP-Hardness of 4-cycle packing problem in complete bipartite digraph?
A directed complete bipartite graph is a bipartite graph where there is exactly one directed edge between any two vertices from its two different parts. In other words, it's an orientation of a ...
- 451
7
votes
0
answers
159
views
Algebraic methods for testing planarity
Mac Lane's planarity criterion states that a graph is planar if and only if it has a cycle basis such that each edge is contained in at most two cycles, we call such a basis a 2-basis. A 2-basis of a ...
- 215
6
votes
1
answer
371
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 ...
- 10.7k
5
votes
0
answers
145
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 ...
- 309
8
votes
2
answers
917
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 ...
- 324
-4
votes
1
answer
129
views
10
votes
1
answer
318
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$. ...
- 7,455
2
votes
0
answers
97
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 ...
- 13.5k
1
vote
1
answer
259
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?
- 189
0
votes
1
answer
355
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 ...
- 451
1
vote
1
answer
463
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 ...
- 119
9
votes
1
answer
149
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 ...
- 2,530
0
votes
1
answer
166
views
Dividing a complete graph into two cliques with maximal sum of edge weights
Problem: Considering a complete weighted graph $G$ with $n$ vertices, where $n\in2\mathbb Z$ is an even number, remove edges in such a way that you end up with two cliques of graph $G$, each having $\...
- 11
0
votes
0
answers
130
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 ...
- 11
9
votes
2
answers
325
views
How long does it take to find a short cycle in a random graph?
Let $G \sim G(n, n^{-1/2})$ be a random graph on $\approx n^{3/2}$ edges. With very high probability, $G$ has many $4$-cycles. Our goal is to output any one of these $4$-cycles as quickly as ...
- 2,293
10
votes
2
answers
346
views
"Relatives" of the shortest path problem
Consider a connected undirected graph with non-negative edge weights, and two distinguished vertices $s,t$. Below are some path problems that are all of the following form: find an $s-t$ path, such ...
- 10.7k
3
votes
0
answers
220
views
Enumerating Minimal (a,b) vertex separators in a DAG
A vertex subset $S \subseteq V$ is an $(a,b)$ separator for nonadjacent vertices $a$ and $b$ if the removal of $S$ from a graph $G$ separates $a$ and $b$ into distinct connected components.
$S$ is a ...
- 33
2
votes
1
answer
138
views
Relationship between $O(\log n)$ (bounded) treewidth and H-minor-free
What is the relationship between graphs which have $O(\log n)$ treewidth and $\mathcal{H}$-minor-free graphs? Are graphs which have $O(\log n)$ treewidth $\mathcal{H}$-minor-free? I know that graphs ...
- 87
8
votes
2
answers
264
views
Lower bound on pebbling numbers
Out of curiosity, I tried finding the original paper showing that there are graphs that require $n/\log n$ pebbles in the sense of Hopcroft, Paul, and Valiant’s seminal paper “On Time Versus Space”. (...
- 633
0
votes
0
answers
85
views
Expected value of a random experiment in a graph
I need to find the expected value of R in the random experiment below.
$$
R = \frac{1}{K} \sum_{C \in \mathcal{H} } \ [\frac{1}{2} |V(C)| * (|V(C)| - 1) - |C|]
$$
$\mathcal{H}$ is a partition on ...
2
votes
0
answers
63
views
Is minimal cover under symmetric 3-deduction NP-complete?
Forgive me if this problem is known by another name, I do not know any references for it.
Symmetric deduction. An equation $e \in E$ is a subset of variables $V$ such that knowing $|e| - 1$ of the ...
- 690
3
votes
0
answers
110
views
Earliest forbidden subgraph characterisation
I wonder, what was the first non-trivial graph class for which there was a forbidden (induced) subgraph characterisation ?
Of course, bipartite graph is one example but I am considering it as trivial ...
- 1,006
1
vote
1
answer
67
views
Are there digraphs such that any two arborescences are arc-disjoint?
Let $D=(V,A)$ be a directed graph with root $r$.
An $r$-arborescence of $D$ is a subgraph such that for any $v\in V-r$, there is exactly one directed path from $r$ to $v$.
Hence an $r$-arborescence is ...
- 183
2
votes
0
answers
86
views
Algorithm for computing the smallest subset of nodes to remove from a graph to make it a tree
I have encountered an interesting problem that I couldn't find any references to solve:
Determine the smallest subset of nodes that
need to be removed from an undirected graph to make it a tree.
...
- 241
0
votes
0
answers
91
views
Matching of two weighted graphs allowing one-to-many mapping
I am looking for a heuristic for a graph matching problem as follows.
Given two graphs: $A$ (consisting of nodes $a_i$) and $B$ (consisting of nodes $b_i$). Typically the size of $B$ is larger than ...
- 1
1
vote
0
answers
57
views
Directed Acyclic Graph partition into minimum subgraphs with a constraint
I have this problem, not sure there is a name for it, wherein a Directed Acyclic Graph has different colored nodes. The idea is to partition it into minimum number of subgraphs with the following 2 ...
- 111
2
votes
0
answers
113
views
Common techniques for the acyclic orientation problem under some special constraint?
An acyclic orientation of an undirected graph is an assignment of a direction to each edge(an orientation) that does not form any directed cycle and therefore generates a directed acyclic graph(DAG). ...
- 451
10
votes
1
answer
267
views
Efficient graph isomorphism for similar graph queries
Given the graph G1, G2 and G3, we want to perform isomorphism test F between G1 and G2 as well as G1 and G3. If G2 and G3 are very similar such that G3 is formed by deleting one node and inserting one ...
2
votes
1
answer
78
views
Computing the existence of a path in a code execution graph
I have a need for an algorithm which I can express as a reachability problem in a graph.
Note that I'd appreciate any advices with respect to better wording this question. Also please tell me if this ...
- 121
3
votes
0
answers
77
views
Embed graph in $\ell_2$ space so that edge and non-edge distances are separated by a constant factor
Suppose I have an undirected unweighted graph $G = (V,E)$. Is there a way to compute points $x_v \in \mathbb{R}^d$ for each vertex $v \in V$ such that $||x_v - x_u|| = 1$ whenever $(u,v) \in E$ and $ |...
11
votes
0
answers
343
views
A dynamic data structure to list triangles
Consider an undirected graph with $n$ nodes. Is there an efficient data structure that supports the following operations?
Insert an edge into the graph
Delete an edge from the graph
Given a query ...
user15587
2
votes
0
answers
89
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 ...
- 149
0
votes
1
answer
215
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 ...
- 57
3
votes
0
answers
61
views
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 $...
- 1,429
-1
votes
1
answer
194
views
Min Cut with Vertices
I have an undirected graph G with a set of vertices and edges. Each vertex has a weight w. Let's assume we have all vertices connected with some paths. I'm looking ...
- 101
1
vote
0
answers
75
views
Graph automorphism with prescribed values
Consider a graph $G$ with vertices labeled $1,...,n$ and edge weights $w_{ij}$. Recall an automorphism of G is a permutation $\sigma$ of the vertex labels such that $w_{\sigma(i),\sigma(j)}=w_{ij}$ ...
- 111
2
votes
1
answer
174
views
How many samples are needed to reconstruct a path?
Consider an input set of vertices $V$ and vertices $s,t\in V$.
The goal is to learn some unknown shortest path from $s$ to $t$; the set of edges of the graph is hidden at first and there may be ...
- 9,378
0
votes
1
answer
38
views
Graph path problem [duplicate]
I am trying to solve one graph traversing problem which might be classical to guys who are familiar with the topic. However, I am not. I have directed graph where nodes are cities and plane can fly ...
- 103