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 vote
0 answers
19 views

Given several $a_i$-$r$ paths in a planar graph how ``balanced" of a tree rooted at $r$ can I make?

Suppose I am given distinct nodes $a_1,a_2,.., a_l, r$ and several $a_i$-$r$ paths $P_i$ in a planar graph $G$. I wish to construct a tree $T$ connecting $a_1,a_2,.., a_l, r$ that minimizes the ...
Hao S's user avatar
  • 237
1 vote
0 answers
37 views

Asking boolean question on the nodes of a DAG to find the target node

We are given a DAG $G=(V, E)$ and an unknown target node $x \in V$ to find. There is a mechanism to probe a node, $y \in V$, to ask question of the form "Given the node $y$, is the target node $x$...
Azam Ikram's user avatar
3 votes
0 answers
87 views

Cover all triangles of a graph with n subgraphs as small as possible

What is the smallest number $s(n,\Delta)$ such that for any undirected simple graph $G=(V,E)$ with $n$ vertices and $\Delta$ triangles, there exist $n$ subgraphs of $G$ covering all triangles where ...
walydna's user avatar
  • 63
0 votes
1 answer
51 views

Finding the shortest cycle containing a vertex in a graph

Given a connected undirected graph with edges $E$ and verticies $V$ and a vertex $v \in V$, find the length of the shortest cycle containing $v$. The best I could do is $O(|E|*deg(v))$, by trying to ...
Sharp Edged's user avatar
4 votes
0 answers
55 views

(Where) in the polynomial hierarchy is determining the mixing time of an implicitly defined graph?

Consider an implicitly defined graph; for example, let $G$ be a finite group generated with $n$ generators as $\langle g_1,g_2,\ldots g_n\rangle$ and let $\Gamma$ be the Cayley graph of $G$ under ...
Mark S's user avatar
  • 947
0 votes
0 answers
34 views

Let $C$ be collection of subsets of $[N]$. Given, $n\in [N]$, what's the terminology for $card\{s\subseteq [N]\mid n\not \in s,\, s \cup\{n\}\in C\}$?

Let $N \ge 1$ be an integer and let $\mathfrak S$ be a nonempty collection of subsets of $[N] := \{1,2,\ldots,N\}$. For any $n \in [N]$, define $\partial_n \mathfrak S := \{S\setminus\{n\} \mid S \in \...
dohmatob's user avatar
  • 291
-1 votes
1 answer
81 views

notation in graph theory [closed]

I was reading a paper, and I found a notation that I don't understand: $\mathbb{E}[| \textbf{S} |] $, where $\textbf{S}$ is a set. Are there any differences with the notation $\mathbb{E}[formula]$ (I ...
Palerme's user avatar
6 votes
0 answers
84 views

Cycle packing with degree condition

Given a directed graph where each vertex has the same in-degree as out-degree, I would like to find the maximum number of edge-disjoint cycles. Is this NP-hard? Without the degree condition, the ...
TZM's user avatar
  • 123
0 votes
0 answers
133 views

What's the connection between branchwidth and treewidth

I understand that treewidth and branchwidth are essentially equivalent for a fixed graph, given that $branchwidth(G) = Θ(treewidth(G))$. However, my question pertains to a specific case involving ...
Jxb's user avatar
  • 21
0 votes
0 answers
57 views

Ensuring the connectivity of an undirected graph through linear programming

I am trying to solve a linear programming problem that deals with finding an optimal subgraph as a function of several parameters. The case is I am trying to model a constraint that ensures that the ...
AdCerros's user avatar
3 votes
1 answer
79 views

END OF THE LINE problem finding a node with in-degree $0$ or out-degree $0$ depending on the initial node

The END OF THE LINE problem is stated as Given two circuits, P and N, a node, v, is balanced if $P(N(v)) = N(P(v)) = v$ or $P(N(v)) \neq N(P(v)) \neq v$. Given that $0^n$ is not balanced, find ...
wavosa's user avatar
  • 135
2 votes
1 answer
103 views

Embedding degree-3 planar graphs as topological minors in wall graphs in polynomial time

For a proof, I need the fact that we can efficiently embed an input planar graph into a representative of a specific family of high-treewidth graphs. Specifically, I need an embedding as a topological ...
a3nm's user avatar
  • 8,234
0 votes
1 answer
42 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^{-...
Zuza's user avatar
  • 141
3 votes
1 answer
172 views

Cover a graph with complete graphs

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)$ ...
walydna's user avatar
  • 63
1 vote
0 answers
36 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), ...
BBK's user avatar
  • 95
6 votes
1 answer
115 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 ...
Michael Lampis's user avatar
6 votes
0 answers
132 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 ...
DeepOak's user avatar
  • 61
0 votes
1 answer
75 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 ...
jpcasti's user avatar
  • 33
3 votes
1 answer
132 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 ...
a3nm's user avatar
  • 8,234
0 votes
0 answers
65 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,...
BBK's user avatar
  • 95
0 votes
1 answer
52 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 ...
K V's user avatar
  • 1
3 votes
1 answer
119 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 ...
John's user avatar
  • 103
1 vote
1 answer
149 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 ...
axizzt's user avatar
  • 11
3 votes
2 answers
219 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)$, ...
tobwin's user avatar
  • 31
1 vote
0 answers
100 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 ...
Andras Farago's user avatar
3 votes
1 answer
157 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<...
Mingzhou Liu's user avatar
2 votes
1 answer
88 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 $\...
Mingzhou Liu's user avatar
1 vote
0 answers
26 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 ...
Gabriel Andrade's user avatar
0 votes
1 answer
130 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$, ...
Dotman's user avatar
  • 79
2 votes
1 answer
67 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)$. ...
Mingzhou Liu's user avatar
0 votes
0 answers
37 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 ...
Hao S's user avatar
  • 237
4 votes
1 answer
176 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 ...
Andras Farago's user avatar
-1 votes
1 answer
63 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 ...
Bernd Strehl's user avatar
2 votes
0 answers
97 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(...
loplo's user avatar
  • 41
1 vote
0 answers
74 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 ...
Chao Xu's user avatar
  • 4,367
2 votes
1 answer
71 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 ...
SamiD's user avatar
  • 2,299
3 votes
0 answers
90 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 ...
theV0ID's user avatar
  • 139
-1 votes
1 answer
80 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=...
NoteMyQuestion's user avatar
1 vote
0 answers
52 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 ...
Julien Codsi's user avatar
2 votes
1 answer
83 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 ...
SagarM's user avatar
  • 706
2 votes
0 answers
84 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 ...
Dmytro Taranovsky's user avatar
1 vote
0 answers
55 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)$...
Karagounis Z's user avatar
0 votes
0 answers
33 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 ...
Vysakh's user avatar
  • 1
2 votes
0 answers
70 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$ ...
bolzep's user avatar
  • 21
0 votes
0 answers
77 views

What's the difference between 'theoretical' and 'applied' runtime complexity?

I recently followed a course on complexity theory and according to the professor I got one particular question wrong. The question involved the runtime complexity of checking the correctness of a ...
Rule's user avatar
  • 1
1 vote
0 answers
60 views

The "branch-depth" parameter and its use in FPT algorithms

Let $P=(v_1,\dots,v_q)$ be an induced path in the undirected graph $G(V,E)$. In [1], the authors define the branch depth of $P$ to be $b(P)=|N_G[\{v_1,\dots,v_{q-1}\}]|-1$. Further, in [1] it is shown ...
BBK's user avatar
  • 95
1 vote
0 answers
58 views

The tree augmentation problem, but with hyperlinks

In the (Weighted) Tree Augmentation Problem, we are given a tree $T = (V,E)$ and a set of additional edges $L$ called links with non-negative costs. Each link $\ell = (u,v)$ covers the tree edges ...
Karagounis Z's user avatar
0 votes
1 answer
91 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 ...
advocateofnone's user avatar
1 vote
0 answers
59 views

Is there an FPT or XP algorithm known for this version of $k$-edge disjoint paths problem?

The shortest $k$-edge disjoint paths problem is defined as follows: Input: An undirected graph $G=(V,E)$ and $k$ pairs of vertices $(s_1,t_1),\ldots,(s_k,t_k)$. Question: Find (if exist) $k$-pairwise ...
advocateofnone's user avatar
1 vote
0 answers
170 views

Cheapest Insertion is $2$-approximation for TSP

Consider the Cheapest Insertion Algorithm on a complete graph with $n$ vertices, where each edge $uv$ has a weight $w(uv)$, and the weights satisfy the triangle inequality $w(xz)\leq w(xy)+w(yz)$ for ...
Ioana Roman's user avatar

1
2 3 4 5
31