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
0 votes
0 answers
35 views

What work on multicost connectivity problems has there been?

For instance has multicost spanning/steiner/prize-collecting tree been studied. i.e. each edge $e$ has costs $c_{v,e}$ of each resource $i$. And we wish to find a spanning tree minimizing the maximum ...
Hao S's user avatar
  • 228
0 votes
0 answers
53 views

Has multiobjective prize collecting steiner tree or TSP been studied?

Suppose we have a graph $G$ a root $r$ and each node $v$ has some amount of $c_{v,i}$ of each resource $i$. I connect a set of nodes to the root that maximizes the minimum amount of any resource using ...
Hao S's user avatar
  • 228
0 votes
0 answers
79 views

Induced subgraphs with interface

I am interested in hypergraphs with interfaces, I'll call them simply "graphs" in the following. Formally, a graph of sort $k$ is a tuple $(V,E,i)$ with $E\subseteq V^+$ is the set of edges, ...
Denis's user avatar
  • 8,843
0 votes
0 answers
42 views

On a modular inverse graph construction

Given a balanced bipartite graph $G_1$ on $2n$ vertices on the condition $PM(G_1)\equiv1\bmod2$, an integer $i$ of size $\Omega(n\log n)$, can we find a balanced bipartite graph $G_2$ on $poly(n)$ ...
Turbo's user avatar
  • 12.9k
1 vote
0 answers
62 views

Is there any augmenting graph algorithm available for finding maximum independent set problem in K1,4-free graph in polynomial time

$K_{1,4}$-free graph is the graph with no induced subgraph of the form $K_{1,4}$ An augmenting graph $H$ for $S$ (which is an independent set) is an induced bipartite subgraph of $G$, where $H = (B, ...
user72110's user avatar
0 votes
1 answer
79 views

Polynomial time algorihtms for two variants of the decision version of longest walk problem

I want to know if the following variants of the longest path problem over directed graphs have polynomial time algorithm. As I understand it, the longest path problem doesn't allow repetition of edges....
user1868607's user avatar
  • 1,017
1 vote
1 answer
60 views

Shorter than target vector path algorithm

Consider a generalisation of the shortest path problem on directed graphs with weights in $\mathbb{Q}^k$. Formally, the input is a graph, a source state $s$, a target state $t$, and an objective ...
user1868607's user avatar
  • 1,017
1 vote
1 answer
170 views

Is (Restricted) Bigraph Isomorphism Weaker than Graph Isomorphism?

I am investigating a paper from Dominik Grezlak and and Uwe Aßmann: “A Canonical String Encoding for Pure Bigraphs.” On page 2, they define the notion of a bigraph, which is roughly a forest and ...
Oscar Bender-Stone's user avatar
0 votes
0 answers
116 views

Given $a_i$ -$r$ paths $P_i$ in a planar graph construct a tree spanning $a_i$ such that each root to leaf path intersects few $P_i$

Suppose I am given distinct nodes $a_1,a_2,.., a_l, r$ and edge disjoint $a_i$-$r$ paths $P_i$ for each $i$ in a planar graph $G$. I wish to construct a tree $T$ connecting $a_1,a_2,.., a_l, r$ ...
Hao S's user avatar
  • 228
0 votes
1 answer
53 views

Question about claw-free graphs

Let $G$ be a claw-free graph, and let $x,y,z,u$ be distinct vertices of $G$. Is the following possible in $G$ ? There are three induced paths through $u$: between $y$ and $z$ (i.e., $y \...
BBK's user avatar
  • 103
0 votes
0 answers
64 views

Is every 4-claw-free graph a bounded degree graph?

I am looking of some graph properties of 4-claw free graph, where neighborhood of every vertex has independent set of size at most 3. As per my observations, this type of independent set size ...
user72110's user avatar
2 votes
2 answers
170 views

property of minimal triangulations

A graph is chordal if every cycle on four or more vertices contains a chord i.e. an edge between non-adjacent vertices of the cycle. A triangulation (or chordalization) of a graph $G=(V,E)$ is the ...
CuriousChordalizer's user avatar
0 votes
0 answers
132 views

Error in TAOCP 4a on the bipartite graph constructed from a hypergraph

The first sentence on page 33 of Donald Knuth's The Art of Computer Programming (TAOCP) Vol. 4a reads: Furthermore, a hypergraph is equivalent to a bipartite graph with vertex set $V \cup E$ and ...
Dominic van der Zypen's user avatar
1 vote
0 answers
123 views

Upper bound on the number of maximal paths in rooted intransitive DAGs

Let $D(V, A)$ be a DAG. Definition 0: We name a path between two nodes $i$ and $j$ as an $i$-$j$-path. Definition 1: Let $p$ be a path, we call $|p|$ the path length, representing the number of arcs ...
Matheus Diógenes Andrade's user avatar
0 votes
0 answers
47 views

Is hypergraph reachability definable in MSO?

Let $(A,E)$ be a directed 2-uniform hypergraph and $E$ the corresponding binary relation such that $(X,Y) \in E$ iff there is a hyperedge from $X$ to $Y$. We say that there is a path from $X_1$ to $...
user7680141's user avatar
5 votes
0 answers
126 views

What is the smallest graph of treewidth $k$ having less edges than the $(k+1)$-clique?

Treewidth is a graph parameter measuring how close a graph is to being a tree. I am interested in what is the minimal number of edges required for a graph to have treewidth $k$. A natural family of ...
a3nm's user avatar
  • 9,269
3 votes
2 answers
164 views

Given a weighted graph with $pk$ nodes find a min weight forest with $p$ components each containing exactly $k$ nodes

Given a weighted graph with $pk$ nodes find a min weight forest with $p$ components each containing exactly $k$ nodes. Does this have a constant approximation? ($p,k$ and the graph are all part of the ...
Hao S's user avatar
  • 228
3 votes
1 answer
74 views

What is the fastest algorithm for computing exact network reliability?

In the network reliability problem, we are given an undirected graph $G$ on $n$ vertices and a parameter $p\in (0,1)$, and are tasked with determining the probability that $G$ becomes disconnected (i....
Naysh's user avatar
  • 606
3 votes
0 answers
99 views

maximum independent set in graphs with small number of edges

For the classic maximum independent set problem, a hardness of approximation result of $n^{1-\varepsilon}$ is known by [Hastad, 1996] assuming $\textsf{NP} \not \subseteq \textsf{ZPP}$, where $n$ is ...
John's user avatar
  • 392
5 votes
0 answers
56 views

How to prove that all pairwise independent hashing circuits are superconcentrators?

It is mentioned in Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates, A. Gal et al. that "it is also not hard to show that (pairwise-independent) ...
Kagura Hitoha's user avatar
7 votes
1 answer
217 views

Counting the different subsets of nodes seen when iterating a subset through a directed graph

For a given directed graph $G = (V, E)$ (possibly with loops), and some $S\subseteq V$ define the operation $G(S) = \{ v\mid (u,v)\in E\text{ for some } u\in S \}$. Now consider the infinite sequence $...
alsips-cl's user avatar
  • 158
0 votes
0 answers
17 views

Any value in a formula that calculates (not look up) the 'order' of a 'Independent Edge Set' OR a 'I.E.S.' given an 'order' on complete graphs?

Any value or interest in a formula that calculates (not look up) the 'integer order' of a given 'Independent Edge Set' OR given an 'Independent Set' calculates the 'integer order' on Complete Graphs? ...
Tim's user avatar
  • 1
4 votes
0 answers
77 views

Name for a cyclic path in a graph that visits every vertex while minimizing the maximum number of times a given vertex is revisited?

Me and my colleague are interested in whether anyone has looked into a generalization of Hamiltonian cycles where vertices can be revisited, but we want to minimize the maximum number of times a given ...
aellab's user avatar
  • 429
-1 votes
1 answer
81 views

Representation of binary strings by graphs and hypergraphs

Let $\Sigma$ be the set $\{ 0, 1 \}$, then the set of all finite binary strings of length $n$ is written as $\Sigma^{\star}_{n}$. Question: Which further ways of representing binary strings of length $...
Samdney's user avatar
1 vote
3 answers
123 views

Stable/Robust Traveling Salesman Approximation Methods

I was wondering if there are TSP approximations that are "stable". More specifically, consider the set $G = x_1, ..., x_n$ and the set $G^* = G \cup x_{n+1}$, where $x_i$ are points in $R^d$....
Winky's user avatar
  • 11
0 votes
1 answer
76 views

A variation of the longest path problem

What about finding a path of maximum length in a given graph which may contain cycles, with the constraint that a vertex (or an edge) can be visited at most X (say 2 or 3) times ? EDIT: X would be ...
user1454590's user avatar
-1 votes
2 answers
190 views

Bottom up TSP solution?

I'm not sure if this is something new or if I'm just not getting previous efforts. TSP can be thought of as a list of weighted links and nodes. If one takes the Nearest Neighbor (NN) of every node and ...
Maub Nesor's user avatar
0 votes
0 answers
67 views

How to reduce a code down to its configuration

I have built a system where from atomic information of a UI code I could generate a framework specific code. Here is the concept https://github.com/imvetri/ui-editor. For example, the user of this ...
Vetrivel's user avatar
1 vote
1 answer
116 views

Tractability of computing generalized hypertreewidth on bounded arity hypergraphs

Generalized hypertreewidth is a generalization of treewidth to hypergraphs. Unlike treewidth, it is not tractable, for a fixed width $k \in \mathbb{N}$, given a hypergraph $H$, to determine if $H$ has ...
a3nm's user avatar
  • 9,269
1 vote
0 answers
90 views

Generalization of the Hamiltonian path problem on Grid Graphs

Fix a cost to each of these actions: move up, move down, move left, move right. I.e. fix some function $f: \{\text{move up, move down, move left, move right}\} \to \mathbb N$. Define the following ...
TRP's user avatar
  • 31
0 votes
0 answers
84 views

5-color graph and minor

We have a 5-color graph G without 5-clique. The question is: is there a minor H of G that is a 5-clique? Here the minor definition. With "5-color graph G" I mean $\chi (G)=5$.
Mario Giambarioli's user avatar
1 vote
1 answer
138 views

Efficient Algorithm for Partitioning a Directed Acyclic Graph into Short Paths

I am working on a problem involving partitioning a directed acyclic graph into distinct multiple paths, each with a maximum length constraint. The goal is to minimize the number of paths (this should ...
user69908's user avatar
1 vote
0 answers
33 views

Application LCL definition to vertex coloration

I'm reading the article "What can be computed locally?" by Naor & Stockmeyer and I struggle to understand the definition of an LCL they gave. Here is an extract: (page 2) An Locally ...
Qise's user avatar
  • 111
1 vote
1 answer
52 views

What is known about the complexity of Network Diversion?

In the Network Diversion problem, we are given an undirected graph $G$ on $n$ vertices, with specified nodes $s$ and $t$ and specified edge $e$, and a positive integer $k$, and are tasked with ...
Naysh's user avatar
  • 606
4 votes
1 answer
88 views

Independent set queries with preprocessing

Suppose we have a sparse undirected graph $G = (V, E)$ with $|E| = O(|V|)$, and we want to process it and then answer queries of the following type: given a set $A$, is it an independent set in the ...
Command Master's user avatar
0 votes
1 answer
76 views

What's the exact complexity of a DFS if we revisit nodes?

By "revisit nodes," I mean if we didn't maintain a set of nodes we have visited. So the sum I'm examining is just the number of paths from a root to a node, across all roots and nodes. We'll ...
Adam Jamil's user avatar
3 votes
1 answer
194 views

What is the treewidth of the 3D-grid (mesh or lattice) with sidelength n?

Here, by 3D-grid of sidelength $n$ I mean the graph $G=(V,E)$ with $V= \{1,\ldots,n\}^3$ and $E=\{( (a,b,c) ,(x,y,z) ) \mid |a-x|+|b-y|+|c-z|=1 \}$. I known how to get the treewidth of $n*n$ grid is ...
Jxb's user avatar
  • 316
1 vote
0 answers
47 views

Notion between connected and strongly connected graphs

Let $G$ be a directed graph without loops (or even better an oriented graph). Let us assume that $G$ is finite. The graph $G$ is connected if its underlying graph $G^*$ is connected (i.e., for every ...
Cyriac Antony's user avatar
0 votes
0 answers
64 views

What is a combinatorial embedding?

I got a reviewer comment saying that I should consider using combinatorial embeddings rather than idk what I should call what I was doing topological embeddings?. But I'm confused because as far as ...
Hao S's user avatar
  • 228
3 votes
1 answer
106 views

Maximum cardinality matching on DAGs

A question on computational complexity and graph theory. The problem of finding maximum cardinality matchings of undirected graphs (the largest selection of edges such that each vertex is "...
Marco Pegoraro's user avatar
4 votes
0 answers
123 views

Exploding number of homomorphisms

I'm trying to tackle the following problem: given two graphs $A$ and $B$, if there exists a graph $D$ such that $\hom(A, D) > \hom(B, D)$ (i.e. there is more homomorphisms from $A$ to $D$ than from ...
Franciszek Malinka's user avatar
1 vote
0 answers
49 views

Bound on the treewidth of a graph from modular contraction

I cannot find a reference for this easy to prove result concerning the treewidth of a graph with respect to the treewidth of a modular contraction of it. Let $G=(V,E)$ be a graph. A module $M \...
holf's user avatar
  • 2,174
1 vote
0 answers
64 views

Graphs such that every rotation system admits an embedding on a surface of small genus

Let $G$ be a finite, simple, undirected graph. What conditions on $G$ ensure that every rotation system of $G$ corresponds to a cellular embedding of $G$ on an oriented surface of small genus? (e.g. ...
Cyriac Antony's user avatar
1 vote
0 answers
51 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
  • 228
1 vote
0 answers
39 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
113 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
169 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
5 votes
0 answers
88 views

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

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
  • 1,083
-1 votes
1 answer
86 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
102 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
  • 133

1
2 3 4 5
32