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
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 ...
user avatar
  • 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}$, ...
user avatar
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$ (...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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$-...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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'\...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
-4 votes
1 answer
129 views

conversion to DAG

Can we reverse directions instead?
user avatar
  • 7
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$. ...
user avatar
  • 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 ...
user avatar
  • 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?
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 $\...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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”. (...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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). ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 $ |...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 $...
user avatar
  • 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 ...
user avatar
  • 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}$ ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar

1
3 4
5
6 7
30