Questions tagged [graph-theory]
Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
1,373
questions
9
votes
1answer
366 views
Is the following graph optimization problem approximable within a constant factor?
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{pred}_{\pi}(v)$ (respectively $\text{succ}_{\pi}(v)$) the set of ...
9
votes
2answers
125 views
Complexity of finding an edge set yielding specified vertex degrees
I'm trying to figure out if the following two problems are known in general to be in P or NP-complete:
Q1: Given a graph $G=(V,E)$ and integers $d_i,\,1\leq\,i\leq|V|$, does there exist a subset $E'\...
9
votes
2answers
306 views
How long does it take to find a short cycle in a random graph?
Let $G \sim G(n, n^{-1/2})$ be a random graph on $\approx n^{3/2}$ edges. With very high probability, $G$ has many $4$-cycles. Our goal is to output any one of these $4$-cycles as quickly as ...
9
votes
1answer
273 views
Pathwidth of planarized drawing of $K_{3,n}$
The pathwidth of the complete bipartite graph $K_{3,n}$ with partite sets of size $3$ and $n$ is at most $3$. I am interested in planarizing this graph by the following process:
Draw it in the plane ...
9
votes
1answer
606 views
Minimum spanning tree over all vertex matchings
I ran into this matching problem for which I am unable to write down a polynomial time algorithm.
Let $P, Q$ be complete weighted graphs with vertex sets $P_V$ and $Q_V$, respectively, where $|P_V| =...
9
votes
2answers
344 views
A variation on discrepancy involving random graphs
Suppose we have a graph on $n$ nodes. We would like to assign to each node either a $+1$ or a $−1$. Call this a configuration $\sigma \in \{+1,−1\}^n$. The number of $+1$s that we have to assign is ...
9
votes
2answers
700 views
Computing a transitive completion / path existence oracle
There has been a few questions (1, 2, 3) about transitive completion here that made me think if something like this is possible:
Assume we get an input directed graph $G$ and would like to answer ...
9
votes
1answer
226 views
When does a graph admit an orientation in which there is at most one s-t walk?
Consider the following problem:
Input: a simple (undirected) graph $G=(V,E)$.
Question: Is there an orientation of $G$ satisfying the property that for every $s,t \in V$ there is at most one (...
9
votes
1answer
379 views
Parametrized Complexity of Counting Bicliques
In a previous question Parametrized Algorithm for Finding Bicliques, I inquired if there were fast parametrized algorithms for finding a $k\times k$-biclique in an $n$ vertex graph and learnt that it ...
9
votes
1answer
180 views
Graph partitioning, balancing on within subset edge weights
I'm interested in pointers to algorithms (approximation algorithms are fine) that attempt to partition a graph into two subsets such that the sum of the edge weights within each subset is (...
9
votes
1answer
270 views
Directed multigraphs as minimal automata
Given a regular language $L$ on alphabet $A$, its minimal deterministic automaton can be seen as a directed connected multigraph with constant out-degree $|A|$ and a marked initial state (by ...
9
votes
2answers
2k views
Maximizing sum edge weights
I am wondering if the following problem has a name, or any results related to it.
Let $G = (V,w)$ be a weighted graph where $w(u,v)$ denotes the weight of the edge between $u$ and $v$, and for all $u,...
9
votes
1answer
143 views
The source of the modular decomposition graph
When introducing graph modular decomposition, most authors use the 11-vertex graph, which I copy from wikipedia.
The question is who is (are) the original designer of it. (I'm not asking who drew ...
9
votes
1answer
152 views
Tree decompositions of optimal width where every vertex is in a bounded number of bags?
Let $G$ be a graph on $n$ vertices whose maximum degree is at most $\Delta$ and whose treewidth is at most $k$.
Does there exist a function $f(k, \Delta)$, independent of $n$, such that it is possible ...
9
votes
2answers
1k views
Number of cycles in a Graph
How many cycles $C_k$ $(k \geq 3)$ are there in a $n $ vertex graph such that graph doesn't have any cycle $C_m$ $(m>k)$.
For example $n=5$, $k=3$, then graph will have at most two $C_3$'s so that ...
9
votes
1answer
2k views
What's the expected length of the shortest hamiltonian path on a randomly selected points from a planar grid?
$k$ distinct points are selected randomly from a $p\times q$ grid. (Obviously $k\leq p\times q$ and is a given constant number.) A complete weighted graph is built from these $k$ points such that ...
9
votes
2answers
333 views
Are there any 'graphical' algebras that can describe the 'shape' of graphs?
One of the main problems in graph enumeration is determining the 'shape' of a graph, e.g. the isomorphism class of any particular graph. I am fully aware that every graph can be represented as a ...
9
votes
1answer
257 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 $...
9
votes
1answer
366 views
Is the complexity of this covering problem known?
Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called critical if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex ...
9
votes
3answers
1k views
Determining connectivity for a fully dynamic graph with vertex/subgraph insertion and deletion
I am looking for a solution to the following problem and wonder if anyone could point me to some existing research on this topic. I am coming from a real world application of graph so bear with me if ...
9
votes
1answer
412 views
Bipartite matching with degree domination
Given an unweighted bipartite graph $G=(V, E)$. Is it true that there always exists a nonempty matching $M\subseteq E$ (not necessarily maximal), such that for every $(i,j)\in E$ with $i$ matched and $...
9
votes
1answer
162 views
Embedding a graph as a collection of interior-disjoint tetrahedra
Define a mesh in 3D as a connected collection of tetrahedra with disjoint interiors (so tetrahedra share only k-faces, $k \le 2$). Given an arbitrary graph, is there an efficient procedure to test if ...
9
votes
2answers
372 views
Enumerating Planar Graphs of Bounded Treewidth
I am looking for references for the following problem: given integers $n$ and $k$, enumerate all non-isomorphic planar graphs on $n$ vertices and treewidth $\leq k$. I'm interested both in theoretical ...
9
votes
1answer
397 views
Increasing the capacity to maximize the min cut
Consider a graph with all edges having unit capacity.
One can find the min cut in polynomial time.
Suppose I am allowed to increase the capacity of any $k$ edges to infinity
(equivalent to merging ...
9
votes
1answer
223 views
What is known about the hardness of the chromatic index for restricted graph classes?
There is a nice paper from 1991 that contains three diagrams about different graphclass-families showing what is known about the hardness of determining the chromatic index for them.
Are there any ...
9
votes
1answer
1k views
Complexity of finding the maximal number of pair-wise disjoint sets
Assume that I have $P$ sets with elements taken from $r$ possible ones. Each set is of size $n$ ($n<r$), where the sets can overlap. I want to determine whether the following two problems are NP-...
9
votes
1answer
297 views
Bounding the number of edges between star graphs such that graph is planar
I have a graph $G$ which consists only of star graphs. A star graph consists of one central node having edges to every other node in it. Let $H_1, H_2, \ldots, H_n$ be different star graphs of ...
9
votes
1answer
265 views
Lighting up all elements of a poset by toggling upsets
I consider the following game on a finite poset $(P, <)$. At each point of the game, I have a set of elements $S$ of the poset which are "on", and all others are "off". Initially $S = \emptyset$. ...
9
votes
1answer
182 views
Edge-partitioning into rainbow triangles
I'm wondering if the following problem is NP-hard.
Input: $G = (V,E)$ a simple graph, and a coloring $f : E \to \{1,2,3\}$ of the edges
($f$ does not verify any specific property).
Question:...
9
votes
1answer
388 views
Finding optimal parallelization from general weighted undirected graph
I am solving a problem of "blending" sets of overlapping images. These sets can be represented by undirected weighted graph such as this one:
Each node represents an image. Overlapping images are ...
9
votes
0answers
71 views
Forbidden Subgraph Characterization for Graphs with few Maximal Cliques
Consider the following property of undirected graphs. A graph has the $s$-vertex overlap property if every vertex is contained in at most $s$ maximal cliques. I am interested in forbidden induced ...
9
votes
0answers
181 views
Random unbalanced bipartite graphs are good small set expanders
My question is about small set expansion properties of random unbalanced bipartite graphs.
Fix a positive $\delta<1/2$, and a positive integers $n,m,d$. Let us call a bipartite graph $\mathcal{G}$...
9
votes
0answers
337 views
Triangle arrangement problem
Suppose you are given an undirected graph $G$, with each vertex representing an equilateral triangle with sides of unit length. Does there exist an arrangement of these triangles in two dimensions (...
9
votes
0answers
252 views
Advances towards proving the Held-Karp conjecture for TSP
I've only began my research into the Held-Karp conjecture and I was wondering about recent progress in proving the conjecture.
The Held-Karp relaxation is conjectured to have an integrality gap of $\...
9
votes
0answers
498 views
Is it possible to solve perfect matching in linear time
As we know matching can be solve in polynomial time. One classical and famous algorithm is designed by Karp and Hopcroft.
Is it possible to solve perfect matching problem in linear time for given $...
9
votes
0answers
334 views
Maximum local edge connectivity
For a simple graph, the local edge connectivity of vertices $x,y$ where $x\neq y$ is $\lambda(x,y)$ and defined as the maximum number of edge disjoint paths from $x$ to $y$. One can find this by a ...
9
votes
0answers
482 views
Statistical relationship between diameter and density in strongly connected random digraphs
I would like to know if there is any known relation between diameter and density in (connected) simple digraphs. Asymptotic results for n→∞, statistical, conditioned results that would restrict the ...
9
votes
0answers
176 views
Pseudorandom object yielding shrinkage in $\ell_p$ norm?
Extractors have the following property: For a random variable $X$ of min-entropy $k$ and a seed $Y$, denote the output of an $(k,\epsilon)$-extractor by $\mathrm{Ext}(X,Y)$. Then $\|\mathrm{Ext}(X,Y)-...
9
votes
0answers
282 views
Spectral gap for random bipartite regular graphs
For a graph $G$, let its Laplacian be $\Delta =I − D^{−1/2}AD^{−1/2}$, where
$A$ is the adjacency matrix, $I$ is the identity matrix and $D$ is the diagonal matrix with vertex degrees. I'm ...
8
votes
5answers
6k views
What are theoretically sound programming languages for graph problems?
There are numerous graph theoretic tools/packages. Each with its pros and cons. What should be the semantics/syntax of a programming language meant to solve graph theoretic problems?
8
votes
3answers
2k views
What kind of mathematical background is needed for graph theory?
It is going to be the first time for me to learn graph theory. What kind of mathematical background do I need to prepare master theses about this subject in following years?
Which subjects should be ...
8
votes
6answers
632 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 ...
8
votes
4answers
520 views
Is there a P/NP-complete dichotomy theorem for natural interesting properties of cubic graphs?
It is well known result proved by Holyer that deciding 3-edge colorability of cubic graphs is $NP$-complete problem.
By Vizing's theorem, all cubic graphs are edge colorable using $\Delta +1$ colors....
asked Jan 29 '14 at 21:52
Mohammad Al-Turkistany
20.1k4 gold badges55 silver badges138 bronze badges
8
votes
1answer
2k views
Is DAG isomorphism NP-C
Given two directed acyclic graphs $G_1$ and $G_2$, is it NP-Complete to find a one-to-one mapping $f:V(G_1) \rightarrow V(G_2)$ such that $(v_i,v_j) \in D(G_1)$ if and only if $(f(v_i),f(v_j)) \in D(...
8
votes
2answers
2k views
Upper bounds on the length of longest simple path in non-Hamiltonian graph?
Hamiltonian cycle problem is $NP$-complete on cubic planar bipartite graphs. I'm interested in upper bounds on the length of the longest simple path in non-Hamiltonian cubic planar bipartite graphs.
...
asked Nov 15 '10 at 20:07
Mohammad Al-Turkistany
20.1k4 gold badges55 silver badges138 bronze badges
8
votes
2answers
477 views
Dijkstra parallelization
I'd like to know what is the best method to parallelize the Dijkstra algorithm.
Thanks.
8
votes
4answers
2k views
Partitioning graphs while minimizing inter-partition edges
I'm working on trying to partition a triangulated graph into connected subgraphs with some guarantees on the number of inter-partition edges. Here's an example of a triangulated graph that has been ...
8
votes
2answers
576 views
Grid minor in digraphs
Thor Johnson, et al, in their paper: Directed Tree Width, introduced a definition for directed grid $J_k$, and they conjectured:
$(5.1)$ For every integer $k$ there exists an integer $N$ such that ...
8
votes
3answers
401 views
Natural graphs that are not scale free
It is now a well known observation that many graphical structures that arise in natural settings tend to obey scale-free properties, such as the power law of degree distribution.
Are there any good ...
8
votes
1answer
334 views
Are there poly time algorithms to determine if a graph is almost bipartite?
Given an undirected graph G, we can say that G is almost bipartite if deleting k edges (or vertices) would make it bipartite.
Are there poly time algorithms to determine if a graph is exactly or ...
