Questions tagged [graph-theory]
Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
1,479
questions
5
votes
0
answers
170
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 ...
- 557
1
vote
1
answer
57
views
Bipartite graph projections, with threshold
Let $G=(\top,\bot,E)$ be a bipartite graph: $E\subseteq \top\times\bot$.
The projections $G_\bot = (\bot,E_\bot)$ and $G_\top = (\top,E_\top)$ of $G$ are defined as follows: two vertices are linked ...
- 683
3
votes
2
answers
109
views
Graph labelling where vertices with a common neighbour get different labels
Is the following notion of graph labeling (let me call it special labeling) ever studied in the literature?
A special labelling of a (simple undirected) graph $G$ is a function $f:V(G)\to\mathbb{N}$ ...
- 1,603
2
votes
1
answer
39
views
Maximum weight matching with classes of edges in a multi-edge bipartite graph
Posted a similar question in mathoverflow, have tried to reduce this to Ford Fulkerson, but been stuck. Thought I'd ask TCS community to see if there are any ideas from individuals, here.
Consider a ...
- 23
6
votes
2
answers
455
views
Is that edge orientation optimization problem NP-hard?
Is the following optimization problem NP-hard?
Problem. For a given undirected graph $G=(V,E)$, find an orientation of the edges that minimizes the objective value $\sum_\limits{u\in V} ~\left( d_{...
- 533
6
votes
1
answer
289
views
Is this edge orientation optimization problem NP-hard?
Is the following optimization problem NP-hard?
Problem. For a given undirected graph $G=(V,E)$, find an orientation of the edges that minimizes the objective value $\sum_\limits{v\in V} ~d_{out}(v)\...
- 533
2
votes
0
answers
208
views
Is this node permutation optimization NP-Hard?
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{succ}_{\pi}(v)$ the set of neighbors of $v$ that occur after $v$ in ...
- 533
7
votes
1
answer
184
views
Random Cerny Conjecture
For simplicity, all DFAs will be using the binary alphabet $\{0,1\}$. Let $M$ be a synchronizable DFA. We let $p(M,n)$ be the probability that a random $x\in \{0,1\}^n$ will synchronize $M$.
We define ...
- 507
1
vote
2
answers
117
views
Name of this graph partitioning problem? (related to coloring)
Given a graph $G=(V,E)$ and an integer $k$, find a partition $P_1, P_2, \dots, P_k$ of $V$ into $k$ parts that minimize the total number of edges between two vertices in the same part, i.e. $\sum_i |(...
- 683
3
votes
1
answer
60
views
Problem conditions to use Laplacian solvers
I am trying to use Laplacian Solvers to solve a linear equation. I am just learning it (form here), so my question is very basic and it might not even make sense.
Suppose that we want to solve Ax=b, ...
- 133
0
votes
2
answers
262
views
Minimum number of triangles required to cover a complete graph?
Let $K_n$ be a complete graph, I am interested in knowing the minimum number of triangles required to get a edge cover of $K_n$. In case there is no closed-form solution to this problem, then I would ...
- 684
3
votes
1
answer
229
views
A stronger Flow Decomposition Theorem?
In the classic Network Flows: Theory, Algorithms, and Applications book (pages 80/81) the flow decomposition theorem is stated as follows:
Every nonnegative arc flow x can be represented as a path ...
- 33
2
votes
1
answer
72
views
random sampling DAGs via nilpotent matrix sampling
The adjacency matrix of an acyclic graph is known to be a nilpotent matrix (all eigenvalues are zero). I am interested in sampling DAG adjacency matrices or equivalently sample random nilpotent ...
- 43
1
vote
1
answer
176
views
Effect of self loops on mixing time?
Consider 2 graphs G1 and G2.
G1: Any non-regular graph.
G2: Same graph but with added self-loops such that degree of each node is the same (either some $\Delta$, or maximum '$n$', where $n$ is the ...
- 33
-1
votes
1
answer
49
views
Multi agent path following with collision avoidance with pre-determined path
I am working on a multi-agent pathfinding algorithm. I am aware of other techniques, but planned on the folowing strategy only.
The problem:
There is 12x12 grid, with a few solid blockades within them....
- 101
3
votes
0
answers
78
views
A class name for series-parallel graphs of same length
I'm currently working on graphs classes where the distance between two specific vertices is the same in every connected spanning subgraphs, and I am looking for a name for this class.
Given a ...
- 31
2
votes
0
answers
54
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 ...
- 1,603
0
votes
1
answer
134
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 ...
- 215
1
vote
0
answers
53
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 ...
- 1,603
3
votes
1
answer
123
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 = \...
- 683
1
vote
0
answers
88
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 ...
- 217
1
vote
0
answers
45
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 ...
- 23
4
votes
1
answer
116
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 ...
- 43
4
votes
2
answers
230
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 ...
- 1,603
2
votes
1
answer
74
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 ...
- 215
2
votes
1
answer
344
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 ...
- 87
3
votes
0
answers
51
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 ...
2
votes
1
answer
129
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 ...
- 1,955
3
votes
0
answers
210
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 ...
0
votes
0
answers
96
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. ...
- 1
0
votes
1
answer
159
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 ...
- 6,615
3
votes
1
answer
75
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?
- 997
2
votes
0
answers
67
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, ...
- 121
1
vote
0
answers
46
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 ...
- 111
0
votes
1
answer
87
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 ...
- 1,603
3
votes
2
answers
153
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 ...
- 1,603
0
votes
0
answers
52
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 ...
- 684
7
votes
1
answer
118
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}$;
...
- 161
2
votes
0
answers
127
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 ...
- 87
2
votes
1
answer
155
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.
- 557
10
votes
1
answer
298
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
1
answer
74
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$....
- 87
1
vote
0
answers
37
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 ...
- 217
2
votes
0
answers
17
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 ...
- 101
2
votes
1
answer
109
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 ...
- 1,603
3
votes
1
answer
226
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 ...
- 183
9
votes
0
answers
86
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 ...
- 1,670
3
votes
1
answer
130
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 ...
- 93
5
votes
1
answer
103
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$ ...
- 1,603
3
votes
0
answers
113
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 $\...
- 131