Questions tagged [graph-theory]
Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
1,374
questions
-1
votes
0answers
12 views
Are there works on flows in networks with a dynamic structure?
I have a network that is initialized in some form, I am looking for a method to find feasible flows in it, the only problem is that, say I find an augmenting path, it could end up not just modifying ...
0
votes
0answers
24 views
Optimum partitioning of vertices into mutually disjoint subsets in a weighted graph
tl;dr I'm trying to partition my students into groups with respect to their preferences, i.e. they can declare if they want to be with someone in a group or if they do not want to be with someone in a ...
-1
votes
0answers
104 views
Are maximum independent set and minimum clique cover also cover-packing problems? [closed]
Maximum independent set and minimum edge cover are a pair of related problems and are cover-packing problems. (Also see p114 of West's Introduction to Graph Theory)
Are maximum independent set and ...
0
votes
0answers
32 views
Internal as well as external partition of (regular) graphs
Let $G$ be a simple finite undirected graph. Let $\{V_1,V_2\}$ be a partition of its vertex set; that is, $V_1\cup V_2=V(G)$ and $V_1\cap V_2=\emptyset$. The partition $\{V_1,V_2\}$ is said to be an ...
2
votes
1answer
133 views
Obtaining Sets of Ancestors Quickly in a Directed Acyclic Graphs
Suppose I have a DAG, $G = (V, E)$ and we know that all nodes in the DAG have at most $A$ ancestors. Let $V' \subseteq V$ be a subset of vertices of $V$. Is there a way to obtain the set of all ...
13
votes
3answers
2k views
What are graph grammars?
I have found information on graph grammars and graph rewriting, but the papers that I find on it are a bit thick. Can someone give a quick overview of what graph grammars are, as well as an overview ...
6
votes
3answers
281 views
Check if graph stays connected after edge swap
Checking whether a (simple, undirected) graph is connected can be done in linear time in the number of edges. What I am looking for is a more efficient way of checking whether it stays connected after ...
0
votes
0answers
34 views
Finding the cardinality of classes that divide all possible directed graphs into those that share k-subgraph cardinalities?
Let us have a set of nodes $V$, such that $|V|=N$. Let $G= (V,E)$ be an arbitrary directed graph on $V$. Let $U$ be the set of all possible directed graphs on $V$.Hence, $|U| = 2^{|V|^2}$. Now, for ...
0
votes
1answer
101 views
When does a bipartite graph have bounded treewidth?
As the title says, I want to know when the treewidth of a bipartite graph is bounded by a constant. What families of graphs are both bipartite and bounded treewidth?
More generally, I would like to ...
10
votes
2answers
265 views
Something-Treewidth Property
Let $s$ be a graph parameter (ex. diameter, domination number, etc)
A family $\mathcal{F}$ of graphs has the $s$-treewidth property if there is a function $f$ such that for any graph
$G\in \mathcal{...
-3
votes
0answers
52 views
Under what name is that NP-Complete commonly known? [duplicate]
When I was a student, I was explained a problem that fascinated me, and at this time, I was told it's an NP-complete problem - which I ended up reducing to a combinatory problem according to notes I ...
39
votes
10answers
12k views
Data for testing graph algorithms
I am looking for a source of huge data sets to test some graph algorithm implemention. Please also provide some information about the type/distribution (e.g. directed/undirected, simple/not simple, ...
24
votes
3answers
1k views
NP complete graph problems about structural properties
(This question is a bit of a "survey".)
I'm currently working on a problem where I'm trying to partition the edges of a tournament into two sets, both of which are required to fulfill some ...
4
votes
1answer
98 views
Minimal clique edge cover vs minimalist (assignment-minimum) ones
Given a graph $G=(V,E)$, a clique edge cover is a collection $C$ of subsets of $V$ such that each element $c$ of $C$ is a clique ($c \times c \subseteq E$) and $G$ is the union of these cliques ($E = \...
2
votes
0answers
31 views
Are there classes where all Eulerian orientations can be listed in polynomial time?
Is there is a subclass of regular graphs (say 4-regular graphs) for which there is a polynomial time algorithm to list all Eulerian orienations?
An Eulerian orientaiton of an (undirected simple) graph ...
2
votes
0answers
84 views
Can someone recommend a reference on graph minors structure theorem and sublinear treewidth?
Can someone recommend a reference on graph minors structure theorem and sublinear treewidth? Doesn't have to be the newest/strongest results as long as it's easier than tracking down all the papers ...
2
votes
0answers
36 views
Directed tree decompositions on subtrees of DAGs
Given a DAG, is the arboreal decomposition of the DAG with the guarantee that given a node $x$, $v$ such that $x$ is reachable from $v$ are in the subtree of $x$? If not, is there a similar ...
-6
votes
0answers
25 views
Your task is to calculate the number of simple paths of length at least 2 in the given graph
how I can calculate this: Your task is to calculate the number of simple paths of length at least 2 in the given graph. Note that paths that differ only by their direction are considered the same (i. ...
-5
votes
0answers
31 views
calculate the number of simple paths of length at least 2 in the given graph [closed]
how I can calculate this:
Your task is to calculate the number of simple paths of length at least 2 in the given graph. Note that paths that differ only by their direction are considered the same (i. ...
4
votes
1answer
112 views
Standard Name for a vertex removal like operation
I have an operation that looks a lot like vertex removal, and I'm wondering if there's a standard name for it. Given a graph $G$ we remove a vertex $v$, but instead of removing the edges that were ...
0
votes
0answers
27 views
Are generalized map involutions captured by GNN?
In coming across a post related to this question's topic, posting in Theoretical Computer Science might be the right place. In combinatorial maps (1,2,3), are generalized map involutions captured by ...
4
votes
1answer
116 views
Does replacing each vertex of $G$ by $H$ increase treewidth of $G$ by at most $\Delta(G)$?
I am asking this question from the context of parameter preserving reductions which has implications for kernelization (See Theorem 18 of [1] for an example). For simplicity, here I am assuming that ...
2
votes
1answer
68 views
Has this bipartite graph problem been studied?
I have a directed bipartite graph with vertex sets $U$ and $V$, directed edge sets $E(U,V)$ and $E(V,U)$, and a demand function $d \colon U \rightarrow \mathbb{Z}$. I want to find a function $f \colon ...
4
votes
0answers
128 views
Power law for degree distribution of random KNN graphs?
Setup Sample random points from say standard Gaussian (or uniform) distribution in $R^{d}$ for some "d"
and consider a KNN (K-nearest neigbour) graph for some K.
Look at the degree ...
10
votes
3answers
764 views
Number of connected components of a random nearest neighbor graph?
Let us sample some big number N points randomly uniformly on $[0,1]^d$.
Consider 1-nearest neighbor graph based on such data cloud. (Let us look on it as UNdirected graph).
Question What would the ...
2
votes
1answer
109 views
Complexity of MAX-ONEs Monotone 2-SAT with $n^{3/2}$ or $C n^2$ clauses?
Let $\phi$ be negative monotone 2-CNF on $n$ variables and $n^{3/2}$
clauses.
What is the complexity of finding satisfying assignment with maximum
number of ones $k$?
Alternatively let $G$ be a graph ...
3
votes
0answers
43 views
Counting subsets of bipartite graph part which admit an induced perfect matching
Given a bipartite graph $G=(U \sqcup V, E)$, count $U^\prime \subseteq U$ for which $\exists V^\prime \subseteq V$ such that the induced subgraph $G[U^\prime \sqcup V^\prime]$ contains a perfect ...
0
votes
0answers
84 views
How many maximal planar graphs are there?
We denote by a triangulation a (simple) maximal planar graph. How many triangulations on $n$ vertices are there? How many triangulations are there if we cannot distinguish the vertices, i.e. ...
0
votes
1answer
101 views
Upper bound on Independence Number of Random Regular Graph with degree $\Theta(\sqrt{|V|} \log^2 |V|)$
Let $G=(V,E)$ be a random $\Delta$-regular graph with $\Delta \in \Theta(\sqrt{|V|} \log^2 |V|)$. I'm analysing an algorithm having asymptotic running time crucially depending on the Independence ...
3
votes
1answer
68 views
Generating hard satisfiability problems with given constraint graph
Is there a systematic way to tune the hardness of a set of satisfiability problems (say 3-SAT or MAX2SAT) where the constraint graphs are always embeddable into a fixed given graph?
2
votes
0answers
57 views
Can we always find a graph with a given algebraic connectivity?
This is crossposted from math stackexchange. This is my first time posting here, so let me know if I'm doing something wrong.
I would like to experiment with various spectral properties of graphs, ...
1
vote
0answers
38 views
Dynamic permutation cycle data
Let $\pi \in S_n$ be a permutation of $\{1, \ldots, n\}$. Does there exist a simple data structure that admits the following operations in polylogarithmic time?
sameCycle($\pi,x,y$): determines ...
0
votes
1answer
76 views
How many more colours do you need if you add to $G$ a maximum matching from $G^c$?
The title says it all. Let $G$ be a (simple undirected finite) graph, and let $G^c$ be the complement of $G$ (i.e. contains edges not in $G$ and no more). Let $M$ be a perfect matching in $G^c$.
How ...
3
votes
2answers
137 views
Coloring where all colors are present in closed neighborhood of every vertex
I am interested in (proper) vertex colorings of graphs with the following condition:
for every vertex $v$ in the graph, all colors should be present in the closed neighborhood of $v$.
Is this studied ...
0
votes
0answers
48 views
How and How fast can we infer a logical formula that expresses a given graph in C$^2$( logic with 2 vars and counting quantifiers)?
In the following paper the author's claim that almost all graphs can be expressed in first order logic with counting quantifiers and two variables.
I would like to know, is there any algorithm that ...
7
votes
1answer
108 views
Extending cographs with product operation
Let $\mathcal{C}$ be the class of undirected graphs defined inductively as follows:
A single vertex is in $\mathcal{C}$;
If $G\in\mathcal{C}$ then its complement $\overline{G}$ is in $\mathcal{C}$;
...
2
votes
0answers
117 views
Finding nodes with enough unique ancestors
Given a DAG $G = (V, E)$, let $T \subseteq V$ be a set of nodes of $V$ that is computed via the following process. Assuming the nodes of $G$ are sorted in topological order, $v_1, \dots, v_n$. We ...
2
votes
1answer
119 views
Is this homework problem on T-joins wrong? [closed]
In Question 9.3a, it states that if $T=V$, then the minimum cost perfect matching is the minimum cost T-join. Is this actually true? I think I have a counterexample which I have drawn below.
10
votes
1answer
210 views
The number of clauses in an unsatisfiable CNF
I am interested in generalisations of the following observation:
An unsatisfiable $k$-CNF has at least $2^k$ clauses.
A special case of the observation is when $k=n$, where $n$ is the number of ...
1
vote
1answer
60 views
Separating DAGs using separators consisting of lists of nodes and all ancestors
Suppose we are given a DAG, $G = (V, E)$ where $n = |V|$. We consider the sets $J_1, J_2, \dots, J_n$ to be lists of vertices where list $J_i$ consists of vertex $v_i \in V$ and all ancestors of $v_i$....
1
vote
0answers
36 views
Remove cycles from a stochastic comparison matrix, while doing the least amount of editing
Let $\mathcal P_n$ be the collection of all matrices $M \in [0, 1]^{n \times n}$ such that $M_{ij} + M_{ji} = 1$ for all $i, j \in [n]$. Such matrices are called comparison matrices. A comparison ...
3
votes
0answers
136 views
Uniquely 4-colorable Planar Graph Conjecture?
My question is on Uniquely 4-colorable Planar Graph Conjecture mentioned in
On purely tree-colorable planar graphs (and other papers of same(?) team such as "Theory on Structure and Coloring of ...
1
vote
0answers
41 views
Three Clique Sums of Bounded Treewidth and Bounded Genus graphs
This question asks about the forbidden minors of the class of graphs that can be formed by taking three clique sums of planar graphs and bounded treewidth graphs(The class is defined for some constant ...
2
votes
0answers
15 views
Power of Hyperedge Replacement Grammars (HRGs)
Can HRGs generate languages which equal or include the following graph languages:
All (bipartite) graphs of bounded degree
All (bipartite) planar graphs of bounded degree
All (bipartite) planar ...
2
votes
1answer
70 views
A conjecture on 4-coloring maximal planar graphs
The question/task is to prove/disprove the conjecture below.
Let $G$ be a maximal planar graph with a 4-coloring $f$. Let $(a,b,c,d)$ be a cycle in $G$. Let $S$ be the collection of all $a,c$-paths in ...
3
votes
1answer
214 views
Two different graph densities: $|E|/|V|$ and $|E|/(|V|-1)$
Let $G=(V,E)$ be a graph.
Let $m(G)=|E|$ and $n(G)=|V|$.
There are two different density definitions for $G$:
$$d_1(G)=\frac{m(G)}{n(G)}$$
and
$$d_2(G)=\frac{m(G)}{n(G)-1}.$$
Let $H^* \subseteq G$ be ...
3
votes
1answer
117 views
Number of maximal cliques in a ($2C_4$, $C_5$, $P_5$)-free graph
So far, I have found out that chordal graphs have linear number of maximal cliques with respect to the number of vertices.
In general case, it is exponential.
I am trying to determine whether the ...
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 ...
5
votes
1answer
67 views
Upperbound for max degree of k-tree completion
Definitions: For a graph $G$, a $k$-tree completion of $G$ is a $k$-tree obtained by adding edges to $G$ (if $G$ has a $k$-tree completion, $G$ is said to be a partial $k$-tree). The least integer $k$ ...
3
votes
0answers
64 views
Minimum feedback arc set for dense directed graph
This is really a matrix problem, but the theory I believe lies in graphs. Consider some matrix $A$ and permutation matrix $P$, where we define $\tilde{A}:= PAP^T$. I want to pick $P$ such that if $\...
