Questions tagged [graph-theory]
Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
1,510
questions
-1
votes
0
answers
9
views
Complexity of fault-tolerant K-median problem on an undirected graph
We know that the K-median problem is proved to be NP-Hard. In fault-tolerant K-median problem on an undirected graph $G=(V, E)$:
We are given a set of facilities $F\subseteq V$ and a set of demands (...
- 1
2
votes
1
answer
110
views
Cover a graph with complete subgraphs
I want to find the smallest possible function $k(n,m)$ such that for any graph $G$ with $n$ vertices and $m$ edges, there exists $n$ vertex sets $S_1,S_2,...,S_n\subseteq V$ each with size $k(n,m)$ ...
- 9,258
0
votes
1
answer
31
views
Entries of the Inverse Laplacian
Let $L$ be a graph Laplacian. What is the meaning of the entries of its (pseudo)inverse $L^{-1}$? In other words, are there any interpretations which might help with understanding the entries of $L^{-...
- 141
-2
votes
0
answers
42
views
Robacker s-t path Theorem
Robacker theorem states that
The minimum length of an s-t path is equal to the maximum number of pairwise disjoint s-t cuts
But in the definition of s-t cut we ...
- 97
1
vote
1
answer
104
views
Graph partitioning to minimize sum of intra-partition edge weights
I've seen a lot of graph partitioning algorithms w/ the objective of minimizing the weight of inter-partition edges, (e.g. k-way partitioning) but haven't quite found anything on minimizing the total ...
- 1
-2
votes
0
answers
28
views
Extracting one induced subgraph of a given graph
Given an undirected graph $G$ composed by $N$ vertices. It is known that there may be at most $2^N$ possible induced subgraphs in $G$. In my case, I just need to find (at each iteration of my ...
0
votes
0
answers
25
views
Minimum vertex-separators under edge addition
I am trying to prove the following claim.
Let $T$ be a minimum $st$-separator in an undirected graph $G$, and let $x \in T$.
Let $S\neq T$ be a minimal $st$-separator (i.e., not necessarily minimum), ...
- 85
0
votes
1
answer
295
views
Fractional but not integer multi-commodity minimum cost flow
I'm searching for an example digraph for the multi-commodity minimum cost flow problem with integer demand. There shouldn't be an integer but fractional optimal solution. I found here a similar ...
6
votes
1
answer
100
views
Complexity of induced Steiner Tree problem
Consider the following problem: we are given an undirected graph $G=(V,E)$ and three terminal vertices $t_1,t_2,t_3\in V$. We are asked whether there exists a set of vertices $S\subseteq V$ such that ...
- 1,537
6
votes
0
answers
110
views
Two graphs indistinguishable by 4-WL
There are pairs of non-isomorphic graphs that are indistinguishable by the k-WL (but distinguishable by (k+1)-WL) [1]. For example 4x4 rook’s graph and the Shrikhande graph are non-isomorphic but the ...
- 61
0
votes
1
answer
72
views
increasing minimum graph degree by adding edges
My problem: Given a graph $G=(V, E)$ and an integer $\ell$,add a minimum number of edges to $G$ so that in the resulting graph every vertex has degree at least $\ell$.
Is there a polynomial-time ...
- 9,258
0
votes
2
answers
344
views
Partition a graph into two clusters
Suppose given a complete weighted graph $G=(V,E)$, Is there an algorithm that partition $G$ into two clusters $C_1,C_2$ such that sum of heaviest edges in $C_1,C_2$ minimized?
Note that, heaviest edge ...
- 194
3
votes
1
answer
124
views
Treewidth for hypergraphs that specify connectedness requirements
This question is about an alternative definition of treewidth, called weak treewidth. It is defined on hypergraphs where hyperedges intuitively require that the connected subtrees of occurrences of ...
- 7,942
8
votes
3
answers
602
views
Is that edge orientation optimization problem NP-hard?
Is the following optimization problem NP-hard?
Problem. For a given undirected graph $G=(V,E)$, find an orientation of the edges that minimizes the objective value $\sum_\limits{u\in V} ~\left( d_{...
- 9,258
3
votes
1
answer
281
views
Is this node permutation optimization NP-Hard?
Let $G=(V,E)$ be an undirected graph and let $\pi$ be a permutation of the vertices in $V$. For a node $v\in V$, we denote by $\text{succ}_{\pi}(v)$ the set of neighbors of $v$ that occur after $v$ in ...
- 121
0
votes
0
answers
63
views
Maintaining a $K_{3,3}$-minor-free graph
Suppose we are given that an undirected, connected graph $G$ is $K_{3,3}$-minor-free.
Let $a,b\in V(G)$ be non-adjacent vertices.
Under what conditions is the graph that results by adding the edge $(a,...
- 85
0
votes
1
answer
47
views
Spectral sparsification of graphs with negative edge weights
I am reading the following well-known paper on spectral sparsification of weighted graphs: https://arxiv.org/pdf/0808.4134.pdf. Page 2 contains most of the definitions relevant to this question.
It is ...
- 111
3
votes
1
answer
101
views
Hardness of Maximum Independent Set in 3-Colorable Graphs
Let $G = (V,E)$ be an undirected graph such that there is a proper coloring of the vertices of $G$ in three colors.
Question: In such graphs, are there known results for the hardness of finding a ...
- 9,258
15
votes
1
answer
5k
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, ...
- 10.1k
3
votes
2
answers
213
views
What is this graph problem, and how hard is it?
My problem is quite simple to state, so it surely must have a name:
Given a graph $G=(V,E)$ with edge weights $w(e) \in \mathbb{Z}$, find a $V' \subseteq V$ that maximizes $\sum_{e \in E' } w(e)$, ...
- 50.5k
2
votes
1
answer
67
views
Number of vertices that a connected dominating set can reach in densely connected graphs
Consider a undirected densely connected (every vertex has $>\Theta(1)$ incident edges) graph $G$. Denote its vertices set as $\mathbf{V}$, number of vertices as $n$.
A connected dominating set $\...
- 9,258
3
votes
1
answer
143
views
Connected dominating set in bipartite graphs
Let $G$ a bipartite graph with two disjoint set of vertices $\mathbf{A}$ and $\mathbf{B}$.
Denote $n_a:=|\mathbf{A}|$, $n_b:=|\mathbf{B}|$. Suppose the following conditions hold:
$\Theta(1)<n_b<...
- 9,258
0
votes
1
answer
128
views
2xn grid graphs from ring graphs via local complementations
(Local complementation) A local complementation $\tau_v$ is a graph operation specified by a vertex $v$, taking a graph $G$ to $\tau_v(G)$ by replacing the induced subgraph on the neighborhood of $v$, ...
- 79
1
vote
0
answers
97
views
On the borderline between natural and artificial problems
While there is no formal definition of what constitutes a natural algorithmic problem,
in most cases there is pretty good consensus whether a specific problem is natural or artificial. Natural usually ...
- 10.8k
1
vote
0
answers
25
views
Can input-output matrices optimize bidirectional search?
Given a bidirectional search on a weigthed digraph, could a modified input-output matrix guess what nodes are more likely to belong to the shortest path and the search be done through these nodes ...
2
votes
1
answer
65
views
Spanning Tree that Preserves the Number of Branch Vertices
Suppose a undirected connected graph $G$, denote the number of vertices in $G$ as $n$, number of branch vertices (i.e., vertices with degree $\geq 3$) as $n_{\geq 3}$. Suppose $n_{\geq 3}>\log(n)$.
...
- 9,258
2
votes
0
answers
86
views
Small set expansion and expanders
Given a graph $G=(V,E)$ on $n$ vertices and $0 \leq \delta \leq 1/2$, we can define the expansion of $G$ over small sets:
$$
h(G,\delta)= \min_{\vert S\vert \leq \delta n } \phi(S) \ ,
$$
with
$$\phi(...
- 41
-1
votes
1
answer
53
views
Solution for a bipartite demand and supply graph
Given a set of distinct nodes ($A \cup B$) one set represents nodes with a supply ($supply(a), a \in A$) and the other represents nodes with a demand ($supply(b), b \in B$). In a bipartite graph I am ...
- 98
0
votes
0
answers
35
views
Is there a version of Klein-Plotkin-Rao (KPR) Theorem that yields components of small diameter rather than weak diameter?
The Klein-Plotkin-Rao (KPR) Theorem says we can find either a $K_{r,r}$ minor or an
edge-cut of size $O(|E|r/\delta)$ whose removal yields components of weak diameter $O(r^2 \delta)$, that is, any two ...
- 227
4
votes
1
answer
171
views
Finding a "typical" path
Consider an undirected graph with two distinguished nodes $u\neq v$. How hard is it to find an $u-v$ path, such that its length is as close to the average $u-v$ path length as possible?
Formally, for ...
- 9,258
40
votes
10
answers
13k
views
Data for testing graph algorithms
I am looking for a source of huge data sets to test some graph algorithm implemention. Please also provide some information about the type/distribution (e.g. directed/undirected, simple/not simple, ...
- 357
7
votes
0
answers
134
views
Can one find good distance-2-separators in planar graphs?
It is known that planar graphs admit "good" separators, allowing to design PTASes for specific problems such as MINIMUM INDEPENDENT SET by recursive separation of the graph.
However, it ...
- 357
8
votes
6
answers
716
views
Have any generalizations of maximum weight matching been studied?
For example, one way to view maximum weight matching is that each vertex $v$ gets a utility $f_v= w(e_v)$ that equals the weight of the edge it's matched on, and zero otherwise.
accordingly, a ...
- 137
1
vote
0
answers
70
views
Packing k vertex trees
Consider a graph $G=(V,E)$ with $n$ vertices.
What do we know about packing of $k$ vertex trees, Both integral and fractional packing are interesting.
$k=2$, it is just the number of edges, hence ...
- 4,306
2
votes
1
answer
70
views
Dual of cut of embedded graph disconnects surface
Let $G$ be a graph that embedded on a surface of genus $g$, moreover the embedding is triangulated. Let $C$ be a collection of edges that forms a minimal edge cut for $G$. Let $C^*$ consist of the ...
- 617
12
votes
4
answers
4k
views
Incremental Maximum Flow in Dynamic graphs
I'm looking for a fast algorithm to compute maximum flow in dynamic graphs. i.e given a graph $G=(V,E)$ and $s,t\in V$ we have maximum flow $F$ in $G$ from $s$ to the $t$. Then new/old node $u$ added/...
- 357
8
votes
1
answer
196
views
Monotone circuit representations of paths in a graph?
Consider a directed graph $G = (V, E)$ with a source $s \in V$ and sink $t \in V$. From $G$, I can define a monotone Boolean function $\phi_G$ on the set of variables $E$, in the following way: every ...
- 7,942
13
votes
4
answers
4k
views
The number of cliques in a graph: the Moon and Moser 1965 result
I'm looking for the full text of the Moon and Moser 1965 clique result On Cliques in Graphs (there exist graphs with a number of maximal cliques exponential in $n$). My university's paywall doesn't ...
- 357
3
votes
0
answers
89
views
Approximative counting of matchings in a graph
The work by Jerrum & Sinclair (1989) describes an approximative approach to determining the number of matchings $|M_\ast(G)|$ in a graph $G=(V,E)$. The fundamental ingredient of the approximation ...
- 139
-1
votes
1
answer
67
views
Unweighted bipartite $b$-Matching
Consider the following problem, of which I am pretty certain that it is polynomially solvable.
Given some arbitrary bipartite Graph $G=(L\cup R,E)$ and some vector $b\in\mathbb{N}^{|L|}$ with $\sum_{i=...
- 424
1
vote
0
answers
48
views
Are there good analogues to Sparsest Cut/Balanced cut for vertex separators instead of edges cuts?
Most problems about cutting graphs into roughly equal parts such as Sparsest cut, Graph partition, Balanced Cut, etc are based on minimizing the size of an edge cut. Even if all of those problems are ...
- 11
2
votes
1
answer
78
views
Regularity Lemma for Multi-Relational Graphs?
Is there an analogous to Szemerédi regularity lemma in the setting, where I have multi relational graph i.e. I have $n$ nodes, but instead of having edges to be in $\{0,1\}$ i.e. there is an edge or ...
- 2,333
2
votes
0
answers
78
views
Finding Hamilton cycles in random graphs
For a random graph $G$ of minimum degree 3, can we find a Hamilton cycle in linear time (with high probability for every edge density)?
If this is an open problem, I will also accept an empirically ...
- 2,402
10
votes
2
answers
350
views
Complexity of digraph homomorphism to an oriented cycle
Given a fixed directed graph (digraph) $D$, the $D$-COLORING decision problem asks whether an input digraph $G$ has a homomorphism to $D$. (A homomorphism of $G$ to $D$ is a mapping $f$ of $V(G)$ to $...
- 2,113
0
votes
1
answer
89
views
Is there FPT or XP algorithms known for Shortest Steiner cycle and $(a,b)$-Steiner path problem
Shortest Steiner cycle and $(a,b)$-Steiner path problem are generalizations of optimization versions of Hamiltonian cycle and Hamiltonian path problems.
The Shortest Steiner cycle problem is defined ...
1
vote
0
answers
54
views
Find the minimum cost spider joining a root to some leaves
A spider is a tree with at most one vertex of degree greater than 2. This vertex is called the head of the spider.
I am interested in the following problem: We are given an undirected graph $G = (V,E)$...
- 577
16
votes
1
answer
505
views
How expensive may it be to destroy all long s-t paths in a DAG?
We consider DAGs (directed acyclic graphs) with one source node $s$ and one target node $t$; parallel edges joining the same pair of vertices are allowed. A $k$-cut is a set of edges whose removal ...
- 2,693
2
votes
0
answers
69
views
Origin of Berge's (Weak) Perfect Graph Conjecture
In an account of his thought process (refer p. 3) leading up to the perfect graph conjecture (which I'm preparing a seminar talk on), C. Berge states what seems to be a crucial step:
(1) a graph $G$ ...
- 2,693
0
votes
0
answers
29
views
How to maximize flow through a graph based on edge orientation (in 3D Cartesian Coordinate Space)?
Problem Stmt:
Suppose you have a graph $G$ with edges $E$ and nodes $V$. The nodes have ${x,y,z}$ coordinates in 3D Cartesian space. Assuming each node contains an $x$ amount of material, the idea is ...
- 1
5
votes
2
answers
1k
views
Algorithms for online clique detection
Are there any algorithms which let you detect cliques when adding/deleting edges based on previously detected cliques? What would be the time/memory complexity of this approach?
- 357