Questions tagged [graph-theory]
Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
1,513
questions
1
vote
0
answers
43
views
Cycle double covers of cubic graphs using only a few cycles
This is a reference request question. Let $G$ be an arbitrary cubic graph.
Is the problem of finding a cycle double cover $D$ of $G$ with minimum number of cycles in $D$ studied in the literature?
I ...
- 1,633
4
votes
0
answers
299
views
Computational Complexity of cycle double cover
Let $\mathcal{G}$ be the set of all finite simple graphs. Let graph $G\in \mathcal{G}$ and $C_G=\left <C_1,...,C_m \right >$ be a sequence of cycles of $G$ for some $m$. For every edge $e$ of $G$...
- 13.8k
35
votes
4
answers
2k
views
Why is "topological sorting" topological?
Why is "topological sorting" called "topological"? Is it just because it determines an order without altering any vertices or edges -- like a doughnut and coffee cup are topologically equivalent? Why ...
- 119
2
votes
1
answer
65
views
Is every 4-colourful Eulerian Orientation of a planar 4-regular graph good?
Let $G$ be a simple undirected plane 4-regular graph. Basic definitions are given at the bottom of this question.
An Eulerian orientation of $G$ is good if for each vertex $v$ of $G$, the edges around ...
- 1,633
1
vote
0
answers
34
views
Cycle decompositions of locally linear 4-regular graphs
(Preface)
We consider only finite, simple, undirected graphs here. An orientation of a graph $G$ is obtained by assigning some direction to each edge of $G$.
(Question starts)
A graph is locally ...
- 1,633
1
vote
0
answers
47
views
Properties of half-way locally bijective homomorphisms between Eulerian orientations
Short Version
Let $G$ and $H$ be two Eulerian graphs and let $\overrightarrow{G}$ and $\overrightarrow{H}$ be Eulerian orientations of those graphs. Let $f$ be a homomorphism from $G$ to $H$.
(...
- 1,633
0
votes
1
answer
85
views
Is a grid graph a vertex-minor of a complete graph? [closed]
Consider a graph $G$. A graph $H$ is the vertex-minor of the graph $G$ if $H$ can be obtained from $G$ using vertex deletions and local complementations. For more information, look at Definition 2.1 ...
- 1,537
8
votes
0
answers
114
views
improved analysis of spectral gap of zigzag product?
I am reading the paper introducing zigzag products of expander graphs (https://arxiv.org/abs/math/0406038). The paper mentions the following observation in the introduction:
Moreover, the variational ...
- 18.8k
1
vote
0
answers
38
views
Is arrangement-type graph on cyclic $k$-permutations of $n$ already studied?
The arrangement graph $A_{n,k}$ is the graph whose vertices are $k$-permutations of an $n$-vertex set $X$ (say, $X=\mathbb{Z}_n$) and two $k$-permutations are adjacent if they differ in exactly one ...
- 1,633
0
votes
0
answers
110
views
optimization on graph edges selection
I have the below problem. I wonder if there exists a similar known class of problems (e.g., in optimization, graph theory) which I can relate my problem to, and find a similar solution there.
I am ...
- 1
-1
votes
1
answer
112
views
Algorithm for finding traffic equilibrium
I watched a youtube video about a certain interesting property of springs and road networks. It made me think: if we represent a network of roads as a graph where edges are roads described by a ...
- 10.1k
-1
votes
1
answer
251
views
Does such a graph exist? [closed]
[EDITED FOR CLARITY]
Does there exist an edge-colored graph $G$ with the following properties?
$G$ has a vertex $r$ with exactly three, distinctly colored, incident edges: $(r, u)$, $(r, v)$, $(r, w)$...
- 9,380
2
votes
1
answer
206
views
Does abundance of max cliques make it easy to solve COLORABILITY?
Let $q\geq 3$. We know that $q$-COLORABILITY is an NP-complete problem.
Suppose that $G$ is a graph such that each vertex of $G$ is part of a $q$-clique (i.e. $K_q$). Since we may assume that $G$ does ...
- 2,560
3
votes
2
answers
239
views
exact path cover for undirected graph
In a Python plotting application,
I have an undirected connected graph, not necessarily simple, that I'd like to cover with paths such that each edge is contained in exactly one path.
The number of ...
- 1,141
2
votes
0
answers
57
views
Complexity of a matrix partition problem in graphs
All graphs in this question are finite, simple, and undirected. Let $H$ be a regular graph on at least five vertices, let $v_1,v_2,\dots,v_n$ be the vertices in $H$, and let $M$ be the adjacency ...
- 1,633
23
votes
0
answers
2k
views
$\Delta = 57, d=2$ Moore Graph
I am looking into the last open question regarding the existence of Moore Graphs of diameter 2. A problem that has been open in combinatorics for more than 55 years.
You may recall that Hoffman and ...
2
votes
1
answer
117
views
Can this special case of Node Weighted Steiner Tree be solved in polynomial time?
Consider the node-weighted steiner problem:
Input: a graph $G=(V,E)$, a set $T\subseteq V$ of terminals, a weight function $w: V\setminus T \to \mathbb{R}_+$.
Output: a minimum weight subset $S \...
CommunityBot
- 1
1
vote
0
answers
51
views
Approximate solution for maximum coverage problem with choice constraint
Suppose a sequence of sets $S_1,S_2,...,S_i$ where each set contains sets of elements. That is, each set $S$ contains many sets $a_1,a_2,...,a_{|S|}$. We are given an integer $k$ and we assume that $\...
CommunityBot
- 1
4
votes
1
answer
177
views
Does a graph resulting from the union of triangles has a particular name?
I have different simple triangle graphs. As an instance, $G_1=(V_1,E_1)=(\{1,2,3\},\{\{1,2\},\{2,3\},\{3,1\}\})$ and $G_2=(V_2,E_2)=(\{1,4,5\},\{\{1,4\},\{4,5\},\{5,1\}\})$.
The union of both graphs ...
- 3,372
0
votes
0
answers
47
views
Is there a primal-dual algorithm for the Tree Augmentation Problem or the Cactus Augmentation Problem?
The TAP problem and the CacAP problem can be seen as covering problems for the minimum cuts of a graph.
It seems like these problems would fall under the framework of network design problems (...
- 597
2
votes
0
answers
76
views
What is the expected treewidth of a large-treewidth graph intersected with Erdos-Renyi graph?
Suppose we have a graph $G$ with treewidth $t$. Let $p \in (0,1)$ be a constant. Then let's independently remove each edge from $G$ with probability $p$. What is the expected treewidth of the ...
- 309
3
votes
1
answer
257
views
Are there an algorithm that find Minimum spanning tree in $O(n^2\log\log^*n)$?
Given completed metric weighted graph $G=(V,E)$ that have $n$ vertices. Are there an algorithm that find MST of $G$ in $O(n^2)$?
I read abstract of this paper that mentioned an algorithm with running ...
- 50.5k
1
vote
1
answer
231
views
State of the art approximation algorithm for $\text{MAXCUT}$ that does better than Goemans and Williamson
I had thought that the Goemans-Williamson approximation algorithm was the best for MAXCUT. To quote from Wikipedia:
The polynomial-time approximation algorithm for Max-Cut with the best
known ...
- 11.4k
5
votes
1
answer
471
views
Pagerank in directed *acyclic* graphs (DAG)
I deal with pagerank computations on large directed acyclic graphs (DAG).
I found no reference to work on this specific case, only some work on pagerank in more specific cases, e.g., PageRank of Scale ...
- 693
5
votes
1
answer
228
views
Computational complexity of Turán-type problems
According to Turán's theorem (with $r=n/2$), any graph $G$ with $n$ vertices and at least $n(n-2)/2$ edges must contain a clique of size $n/2+1$. My question is: how hard is it to find this clique?$^*$...
- 223
2
votes
0
answers
96
views
How typical are odd-H-minor free graphs?
Can anything be said about how typical are odd-H-minor free graphs? (definition of odd-minor-free is in Section 2.2 of notes, page 20 of slides). For instance, for a random graph with $n$ vertices, $...
- 4,651
5
votes
2
answers
278
views
Complexity of "can we get a cycle by stacking directed bipartite graphs?"
Preliminaries
We consider directed bipartite graphs of the form $G = (V,V',E)$, in which the nodes are partitioned into $V = \{1,\ldots,n\}$ and $V'=\{1',\ldots,n'\}$, with $|V|=|V'|=n$, and $E\...
- 617
6
votes
0
answers
279
views
Fastest exact algorithm for MAXCUT
Is the algorithm introduced in the following paper still the fastest exact algorithm for general MAXCUT problems? TIA
Ryan Williams, A new algorithm for optimal $2$-constraint satisfaction and its ...
1
vote
1
answer
128
views
Partition the edges of a bipartite graph into perfect $b$-matchings
Any $r$-regular bipartite graph can be partitioned into $r$ disjoint perfect matchings.
I want to know whether a version of this extends to perfect $b$-matchings.
Suppose we have a bipartite graph $G =...
- 9,380
0
votes
1
answer
159
views
Max-k-cut with negative edge weights
Let $G=(V,E,w)$ be a graph and for edge $e\in E$, there is associated weight $w_e$.
The max-k-cut wants to partition V into k subsets $P_1,\cdots,P_k$ and maximize $\sum_{1\leq r<s\leq k}\sum_{i\in ...
- 3,899
1
vote
1
answer
51
views
Graph classes where giving a q-clique edge cover makes testing for q-colouring easy
A $q$-clique of a graph is a complete subgraph on $q$ vertices.
A $q$-clique edge cover of $G$ is a set of subgraphs of $G$ such that each subgraph is a $q$-clique and each edge of G is contained in ...
- 5,742
1
vote
0
answers
65
views
Prune length distribution of random binary tree
Consider a random binary tree with $N$ leaves. Each node (except the root node) has a degree of exactly three (two children and one parent). No further restriction is placed on the structure of the ...
3
votes
1
answer
106
views
Finding the single-crossing embedding of a single-crossing graph
Is it known how to find a (piecewise) straight-line embedding of a single-crossing graph on the plane with exactly one crossing in polynomial time? We are currently trying to come up with a method for ...
- 617
2
votes
1
answer
166
views
Coloring intersection graph of squares
It is known that the coloring intersection graph of axis-parallel rectangles is NP-Hard.
What about squares and more specific case "unit squares"?
Thanks.
- 3,430
0
votes
1
answer
57
views
Planar 4-regular vertex-transitive graphs as system of circles
It is known that every planar 4-regular 3-connected graph $G$ admits a realization as a system of circles, i.e., it can be drawn on the plane utilizing a set of circles such that the vertices of $G$ ...
- 50.5k
1
vote
0
answers
149
views
How can I find the PhD thesis of A. V. Kostochka?
I've searched for the doctoral thesis of Alexandr V Kostochka in internet but couldn't find it. Can somebody help me?
I have searched in his publications list (which contains only one article ...
- 1,633
1
vote
1
answer
115
views
Is there a regular bipartite graph where the minimum cuts are trivial?
My question is: Given integers $r$ and $k$, is there an $r$-regular bipartite graph $G = L \cup R$ with $|L| = |R| = k$, which is $r$-edge connected, and such that every minimum cut is trivial?
We can ...
- 814
5
votes
0
answers
78
views
Does every graph of clique-width 3 have a large induced subgraph of clique-width 2?
Is there a constant $\alpha>0$ such that every graph $G$ of clique-width $3$ and order $n$ has an induced subgraph of order at least $\alpha n$ and clique-width at most $2$ (in other words, the ...
- 351
2
votes
1
answer
188
views
Is the difference between the acyclic chromatic number and the star chromatic number unbounded?
Is $\chi_s(G)-\chi_a(G)$ unbounded in general graphs?
I thought $\chi_s(G)-\chi_a(G)$, the difference between the star chromatic number and the acyclic chromatic number, is unbounded for general ...
- 15.4k
1
vote
0
answers
106
views
Has this notion of connectivity in edge-colored graphs been studied?
Consider a simple graph $G$ where each edge is either red or blue. I'm interested in the following notion of connectivity:
Two vertices $u$ and $v$ are said to be connected if there is a path ...
- 351
27
votes
3
answers
888
views
The complexity of determining if a fixed graph is a minor of another
The result by Robertson and Seymour demonstrates an $O(n^3)$ algorithm for testing whether a fixed graph $G$ is a minor of $H$. I have two and a half questions on this topic:
1) It appears that there ...
3
votes
1
answer
213
views
Detect if a graph has a $k$ cycle in space complexity $O((\log k)^d)$ for fixed $d \geq1$
For a graph $G$, I want to test if it contains a cycle of length $k$, for some $k$ much smaller than $|G|$. I am interested in particular in an algorithm with low space complexity. The cycle need not ...
- 11.1k
0
votes
1
answer
59
views
Do such instances always admit a 3D matching?
I want to know whether the following kinds of special instances of the 3D Matching problem are ``yes" instances, i.e., admit a 3D matching.
We are given 3 sets $A,B,C$ containing $m$ elements ...
- 25
1
vote
2
answers
169
views
Maximum cliques of the transitive closure of a chordal DAG
Let $G=(V,A)$ be a directed acyclic graph, for which the underlying
undirected graph is chordal (so that every induced cycle in the
underlying undirected graph is a triangle).
It is known that in a ...
- 1,537
3
votes
1
answer
157
views
TSP with "enemy" nodes
I am curious if the following variation of the traveling salesman problem (TSP) (or a vehicle routing problem (VRP) version) occurs in the literature and has a name I could search for.
The story/idea ...
- 211
5
votes
0
answers
176
views
Minimum spanning tree, but with an unusual objective function
This is a problem that came up in my study of rumour networks. I was wondering if anyone had thoughts or references on this problem.
If we have a rooted tree $T = (V,E)$ with root $r$, I first label ...
- 597
8
votes
1
answer
216
views
Finding vertex separator such that the induced subgraph has minimal number of edges
My problem is related to edge and vertex cuts with a little twist.
Given a graph $G$ and two vertexes $u$ and $v$. I want to find a set of vertexes $S \subset V$ that disconnects $u$ and $v$ such that ...
- 50.5k
-1
votes
1
answer
134
views
What are the known classes of undirected graphs such that every graph belonging to that class is guaranteed to have a Hamiltonian Path?
One trivial class of graphs is the class consisting of complete graphs or complete bipartite graphs with equal sized partitions.
I would love to know if more such classes exist.
- 2,333
-2
votes
1
answer
104
views
upper bound on the total number of fixed-length paths in an acyclic graph [closed]
I was wondering if there is an upper bound on the total number of fixed-length paths (path length from 1 to $n-1$ given $n$ nodes) in an acyclic graph (not directed) of $n$ nodes? If so, can you point ...
- 1,526
4
votes
1
answer
192
views
Does such a bipartite graph exist?
In the course of my studies on graphs I sometimes use gadgets. I recently came upon a need for a certain bipartite graph with the following properties, and I am wondering if anyone knows if such a ...
- 9,380