Questions tagged [graph-theory]

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

Filter by
Sorted by
Tagged with
-3
votes
1answer
42 views

Converting a directed graph to a DAG by flipping edges

I have directed graph which is a complete graph if we disregard the directions of edges and obviously there are exactly nC2 directed edges. My goal is to convert this graph into a DAG, with minimum ...
5
votes
0answers
67 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$. ...
2
votes
0answers
66 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 ...
1
vote
1answer
69 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?
0
votes
1answer
84 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 ...
1
vote
1answer
95 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 ...
-4
votes
0answers
23 views

What is minimum cost perfect matching problem for general graph?

It does make sense when we talk about perfect matching in bipartite graphs because there are two sets of points, for example, one set may be jobs and another set may contain different machines. But ...
9
votes
1answer
116 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 ...
0
votes
1answer
65 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 $\...
0
votes
0answers
99 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 ...
9
votes
2answers
250 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 ...
-1
votes
0answers
53 views

Total number of trees where non-leaf nodes have at least 2 children

Given $N$ leaves, how many trees can be constructed if every non-leaf node has at least 2 children? Below are the 30 trees given $N=5$: Additionally, if we account for the order of $X_1,X_2,X_3,X_4,...
10
votes
2answers
170 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
88 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
105 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 ...
0
votes
0answers
58 views

Generalization of k-Coloring: maximizing the number of vertices with no neighbours of same color

One can consider the following generalization of the $k$-Coloring problem: Let be given a graph $G$ and an two integers $k$ and $p$. A vertex $v$ of $G$ is properly colored if $v$ has no neighbour ...
7
votes
2answers
186 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
77 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
48 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
106 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
59 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
67 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
43 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 ...
0
votes
0answers
59 views

s,t-Graphs representing infinite number of addition chains

I am looking at directed acyclic multi-graphs $G=(V,E)$ with a single source and sink with integer labeled arcs. Each vertex has exactly two inputs except $s$. Each vertex has at least one output ...
1
vote
0answers
50 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
73 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
207 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
68 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
73 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
329 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
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 ...
0
votes
0answers
66 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 ...
0
votes
1answer
80 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
46 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
48 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
56 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
163 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
0answers
19 views

The set of weight functions for which the assignment problem has non-trivial solutions

The standard assignment problem is specified with a square matrix ${\bf W}$ of weights (values, costs): $$ V_{\cal P} = \sum_i w(i, b(i)) = \sum_{(i, j) \in {\cal P}} w_{ij}, $$ where $\cal P$ is a ...
0
votes
1answer
33 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
61 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
108 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
79 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
82 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 ...
3
votes
0answers
88 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$...
0
votes
1answer
282 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
153 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
150 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 ...
0
votes
0answers
39 views

Reference on generalization of plane graph duality between bonds and simple cycles

I've also asked this question on Mathoverflow, but it hasn't gotten an answer after several months: https://mathoverflow.net/questions/316132/reference-on-generalization-of-plane-graph-duality-between-...
2
votes
0answers
120 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
278 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 ...