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
-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 (...
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)$ ...
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^{-...
-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 ...
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 ...
-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), ...
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 ...
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 ...
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 ...
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 ...
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 ...
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_{...
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 ...
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,...
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 ...
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 ...
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, ...
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)$, ...
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 $\...
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<...
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$, ...
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 ...
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)$. ...
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(...
-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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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/...
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 ...
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 ...
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 ...
-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=...
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 ...
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 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 ...
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 $...
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)$...
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 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$ ...
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 ...
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?

1
2 3 4 5
31