Questions tagged [graph-theory]

Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.

1,544 questions
Filter by
Sorted by
Tagged with
35 views

1 vote
134 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 ...
556 views

Connectivity of a random regular graph of degree $d$

An Erdős–Rényi graph over $n$ vertices and average degree $d$ is not connected w.h.p. iff $d < \log n$. I was wondering for what the degree $d$ would a random regular graph of degree $d$ be ...
196 views

Are there any implementations of a graph crossing algorithm?

This is much more focused version of this question: Are there good implementations for easy subclasses of NP-hard graph problems Computing the graph-crossing number $cr(G)$ for a simple graph is ...
97 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 ...
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) ...
217 views

77 views

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 $... 4 votes 0 answers 76 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 ... 1 vote 0 answers 250 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 vote 1 answer 625 views Generate TSP instances with known optimal Is there a known (polynomial in number of nodes) algorithm to generate TSP instances with known optimal value? The idea is to be able to generating arbitrary large instances with known optimal value,... 0 votes 1 answer 75 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 ... 0 votes 0 answers 65 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 ... 1 vote 0 answers 80 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 ... 1 vote 0 answers 88 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 ... 2 votes 4 answers 6k views Complexity of greedy coloring I was looking at some heuristics for coloring and found this book on Google books: Graph Colorings By Marek Kubale They describe the Greedy algorithm as follows: ... 0 votes 0 answers 83 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$. 2 votes 1 answer 66 views Upper Bound for distance-two chromatic number in terms of maximum degree Let us consider simple,finite, undirected graphs. A distance-two colouring of a graph$G$is a function$f:V(G)\to\{1,2,\dots\}$such that$f(u)\neq f(v)$whenever$dist_G(u,v)\leq 2$. A distance-two ... 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 ... 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 ... 1 vote 1 answer 50 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 ... 0 votes 1 answer 205 views Transitive reduction not provably minimal [closed] Working on finding minimal equivalent graphs, which unlike transitive reductions only allows for edge removals from the original graph. I was under the impression that if you allow for new edges to be ... 0 votes 1 answer 73 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 ... 3 votes 1 answer 138 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 ... 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 ... 1 vote 0 answers 46 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 ... 0 votes 0 answers 61 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 ... 3 votes 1 answer 104 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 "... 8 votes 0 answers 171 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 ... 5 votes 0 answers 84 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 ... 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 ... 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 \...
1 vote
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. ...
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 ...