Skip to main content

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
101 views

Is Gnag's proof of Graceful Tree Conjecture correct?

Gallian's dynamic survey on graph labeling mentions Gnang's preprints which claim to resolve the graceful tree conjecture. The latest version of this preprint dates 2023 August. Another related ...
Cyriac Antony's user avatar
0 votes
0 answers
18 views

On the Relationship Between Graph Isomorphism and Equivalence in ETL Workflow Dependency Graphs

Let $G = (V, E)$ and $G' = (V', E')$ be two DAGs representing dependency graphs of ETL workflows. Each node $v \in V$ (or $v' \in V'$) represents a task, which is a tuple $t_v = (q_v, d_v, s_v)$, ...
Zoom's user avatar
  • 1
0 votes
1 answer
96 views

Deciding whether there are directed paths between two vertices of all possible lengths

I recently read a paper The presence of a zero in an integer linear recurrent sequence is NP-hard to decide by Blondel and Portier, in which they prove the statement The problem of determining for a ...
user918212's user avatar
0 votes
0 answers
33 views

Enhancing a bipartite perfect matching solution with 1-to-2 matchings

We're doing hobby events where people list their items followed by a wishlist of what they would like to receive in exchange for each one of their items, then the current algorithm finds the biggest ...
Juan Ignacio Suarez's user avatar
0 votes
0 answers
79 views

Channel Capacity & Dependency Graph

A single-input-single-output communication channel is to be used repetitively. Denote by $X_i \in \mathcal X$ the input at time $i$ and by $Y_i \in \mathcal Y$ the output at time $i$. Assume the ...
Euclid's user avatar
  • 101
0 votes
1 answer
121 views

Is the protocol perfect zero knowledge?

Consider such protocol for $GI$ (Graph-isomorphism problem). $P$ randomly chooses permutations $\sigma_1, \sigma_2, ..., \sigma_k$ and sends $H_1 = \sigma_1(G_0), ..., H_k = \sigma_n(G_0)\ (k > 1)$;...
GeoArt's user avatar
  • 9
1 vote
0 answers
84 views

Development details of the Hungarian algorithm for Maximum Perfect Bipartite Matching

There are two realization forms of Hungarian algorithm. One is the original dynamic matrix, and the other is via equality subgraph. I just checked the original paper of Hungarian method by Kuhn, which ...
Shawxing Kwok's user avatar
0 votes
0 answers
70 views

What work on min max connectivity problems has there been?

For instance has min max 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
65 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
1 vote
0 answers
95 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,903
0 votes
0 answers
47 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
  • 13k
1 vote
0 answers
69 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
83 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,049
1 vote
1 answer
64 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,049
1 vote
1 answer
179 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
117 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
56 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
69 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
189 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
137 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
126 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
51 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
9 votes
1 answer
216 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,547
3 votes
2 answers
169 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
77 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
  • 686
3 votes
0 answers
103 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
  • 412
5 votes
0 answers
59 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
219 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
18 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
78 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
  • 439
-1 votes
1 answer
90 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
125 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
84 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
198 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
68 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
121 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,547
1 vote
0 answers
92 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
85 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
143 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
34 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
59 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
  • 686
4 votes
1 answer
91 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
80 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
204 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
50 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
71 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
114 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
127 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
50 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
67 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
2 3 4 5
32