Questions tagged [graph-theory]
Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
1,451
questions
10
votes
2answers
325 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 ...
3
votes
0answers
199 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 ...
2
votes
1answer
136 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 ...
8
votes
2answers
252 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”. (...
0
votes
0answers
84 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
0answers
61 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 ...
3
votes
0answers
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
vote
1answer
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 ...
2
votes
0answers
85 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.
...
0
votes
0answers
85 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
vote
0answers
55 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 ...
2
votes
0answers
111 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). ...
10
votes
1answer
264 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
1answer
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 ...
3
votes
0answers
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
0answers
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 ...
2
votes
0answers
88 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 ...
0
votes
1answer
202 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 ...
3
votes
0answers
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
votes
1answer
178 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 ...
1
vote
0answers
73 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}$ ...
2
votes
1answer
172 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 ...
0
votes
1answer
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 ...
0
votes
1answer
545 views
Finding a Hamiltonian cycle from perfect matching of a bipartite graph
A disjoint vertex cycle cover of G can be found by a perfect matching on the bipartite graph, H, constructed from the original graph, G, by forming two parts G (L) and its copy G(R) with original ...
-3
votes
1answer
126 views
Finding the maximum no. of people who get along in a group [closed]
Suppose that there are 15 people in a room. Assume that each person gets along with other people in the room (but not everyone). (Note that the "feeling is mutual" between any two people who are ...
1
vote
0answers
97 views
Minimum cut with nonlinear objective function
Let $G$ be an undirected graph. The classic minimum (cardinality) cut problem asks for a cut $C\subseteq E(G)$, such that $|C|$ is minimum.
Let us generalize it the following way: let $f$ be a ...
0
votes
1answer
94 views
Densest k subgraph problem for outerplanar graphs?
The densest k subgraph problem aims to find a subgraph $H$ of a graph $G$ with exactly $k$ vertices that maximizes the number of edges $|E(H)|$.
Does anyone know if there exists a polynomial-time ...
4
votes
0answers
98 views
Counting quotient graphs, but not exactly
All graphs considered will be directed graphs $G=(V,E)$, with $E \subseteq V \times V$ (so possibly with self-loops). For $k \in \mathbb{N}_{\geq 1}$, I will write $[k]$ the set $\{1,\ldots,k\}$. A $k$...
1
vote
1answer
2k views
Number of simple paths between two vertices in a DAG
Let $G = (N, A)$ be a connected acyclic digraph (DAG). Furthermore, let $s \in N$ and $t \in N$ be two vertices on this graph, such that $t$ is reachable from $s$.
My problem is: how many simple $s-t$...
5
votes
1answer
205 views
Minimum cost cut with discount - what is the complexity?
Consider an undirected graph $G=(V,E)$ with non-negative edge costs. Given an integer $k$ with $0\leq k\leq |E|$, let us call an edge set $C\subseteq E$ a $k$-discounted cut, if the following hold:
$...
1
vote
1answer
196 views
Does Hadwiger conjecture imply that NP = coNP?
(Disclaimer: I suspect the answer is no, but I fail to see why)
Here is a nice picture by David Epstein (taken from Wikipedia) illustrating Hadwiger's conjecture:
The point is that if in a given ...
2
votes
0answers
178 views
Shortest s-t path when is allowed to ignore k weights
Given an undirected graph $G$ with $n$ vertices and $m$ edges, with non-negative weights on the edges, what's the best algorithm that computes the shortest path from $s$ to $t$, where you are allowed ...
6
votes
1answer
340 views
Naive definition of treewidth
Treewidth has arguably pretty involved definition. Recently I was thinking about a problem and turns out it easy to solve it for graphs with small ``naive treewidth''.
Naive treewidth is defined as ...
4
votes
0answers
145 views
Is there a standard name for this way of modifying graphs?
Let $G = (V, E)$ be an undirected graph. Let me take an edge $\{x, y\}$ (in blue in the drawing) such that $x$ and $y$ have other incident edges. Among the incident edges we choose one edge $e_x = \{...
0
votes
1answer
71 views
Counting sum of parities of cycle covers in cubic, planar, bipartite graphs
Let $G$ be a cubic (i.e. every degree exactly three), planar, bipartite graph. By Hall's theorem its edges can be partitioned into three perfect matchings. Take any such partition $M_0,M_1,M_2$ and ...
4
votes
0answers
750 views
Generating a random connected bipartite graph
A (n, m, k)-bipartite graph is a bipartite graphs with:
independent sets of size $\{n, m\}$
a total of $k \geq n+m-1$ edges
We want an algorithm to generate a (n, m, k)-bipartite selected uniformly ...
4
votes
0answers
179 views
What's the fastest known algorithm for finding the diameter of a graph?
Given a positively weighted graph what's the fastest algorithm for finding the diameter for that graph?
5
votes
1answer
165 views
Viola's Reduction of 3XOR to listing triangles
Apparently this was due to Pătraşcu, but in this report on the ECCC server, Viola states that 3XOR can be reduced to listing triangles.
Assume that given a graph in adjacency list format, with $m$ ...
1
vote
0answers
129 views
Star seperators to explain computational complexity of algorithms on a class of graphs?
A lot of NP-hard optimization problems on graphs which are perfect become solvable in polynomial time. Unfortunately, the class of graphs that arise in my problem are not perfect. The graphs can be ...
1
vote
1answer
263 views
maximize edges minus vertices in a weighted graph
for a given weighted vertices and edges graph, we want to find the maximum subgraph. the maximum subgraph is made of some vertices and some edges of the given graph which sum of the edges minus sum of ...
6
votes
1answer
173 views
Separating words and graph isomorphism
I wonder if there are any known implications of Babai's recent quasi-polynomial time algorithm for Graph Isomorphism to separating words by DFA's.
In both cases the ultimate goal is to differentiate ...
1
vote
0answers
58 views
Is there an efficient way to reduce a set of graphs under isomorphism?
Suppose we have a set $S$ of (fixed-size) graphs, many of which are isomorphic to each other. How do you find a minimum-size set $M$ of graphs such that every $g\in S$ is isomorphic to some graph in $...
2
votes
1answer
169 views
Is balanced Hamiltonian cycle NP complete on maximal plane graphs?
I know that the Hamiltonian cycle is NP complete on the class of maximal plane graphs.
If we instead ask about balanced Hamiltonian cycles (i.e. same number of faces on both sides) on maximal plane ...
1
vote
1answer
87 views
Pulling a graph across a partition
I am looking for the name for a particular graph property, if it has been studied, and efficient algorithms for computing it, if they exist. I realise that this may be a well known property that I am ...
1
vote
1answer
91 views
Cryptography protocols using graph problem instances
I personally am only aware of basic examples of public key cryptography and I haven't studied cryptography yet. I'm curious if there are circumstances in cryptography where using problem instances ...
2
votes
0answers
152 views
Crime prevention using graph theory and machine learning
I am looking for a way to the model the incidence of crime among a network of individuals. Part of it will use machine learning, and part of it will have to resort to some graph theoretic ...
9
votes
1answer
414 views
Is there an algorithm that finds the forbidden minors?
The Robertson–Seymour theorem says that any minor-closed family $\mathcal G$ of graphs can be characterized by finitely many forbidden minors.
Is there an algorithm that for an input $\mathcal G$ ...
9
votes
0answers
217 views
Random unbalanced bipartite graphs are good small set expanders
My question is about small set expansion properties of random unbalanced bipartite graphs.
Fix a positive $\delta<1/2$, and a positive integers $n,m,d$. Let us call a bipartite graph $\mathcal{G}$...
4
votes
1answer
187 views
Complexity of finding Exact Size Cut-Sets in Bipartite Graphs
I am interested in the problem of deciding if a cut-set of a given size $k$ (i.e. the number of edges crossing the partitions is $k$) exists in a given bipartite graph (both the graph and $k$ are part ...
1
vote
1answer
58 views
Problem property name where an optimal solution in a graph can be used as a solution in any subgraph
Suppose one is given a graph optimization problem where the optimal solution $S$ for the problem on graph $G$ can be used as a solution for any subgraph of $G$. In other words, given $S$ is an optimal ...