Questions tagged [graph-theory]

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

Filter by
Sorted by
Tagged with
6
votes
1answer
90 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 ...
1
vote
2answers
65 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 |(...
-2
votes
1answer
30 views

Can there be a graph where IDDFS vists fewer nodes than BFS [closed]

IDDFS: Iterative Deepening Depth First Search BFS: Best First Search Can there be a graph where iterative deepening depth first search visits fewer nodes than BFS, give an example or explain why it is ...
3
votes
1answer
48 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, ...
0
votes
2answers
115 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 ...
3
votes
1answer
105 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 ...
2
votes
1answer
54 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 ...
1
vote
1answer
123 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 ...
0
votes
0answers
22 views

Optimum first stage solution of two stage stochastic shortest path induces tree

I struggle with the proof of Lemma 1 in the Paper "Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization Problems" by Ravi and Sinha and hope this is the right community ...
2
votes
0answers
76 views

The many strengths of PageRank

PageRank is used and studied in incredibly many contexts. It is taught in many courses worldwide, with several books and thousands of papers devoted to it. To this regard, PageRank plays a quite ...
-1
votes
1answer
35 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....
3
votes
0answers
70 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 ...
0
votes
0answers
29 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 ...
2
votes
0answers
39 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 ...
0
votes
1answer
103 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 ...
1
vote
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 ...
3
votes
1answer
106 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 = \...
1
vote
0answers
86 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 ...
1
vote
0answers
37 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 ...
4
votes
1answer
113 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
28 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
117 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
70 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 ...
2
votes
1answer
139 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 ...
0
votes
0answers
36 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 ...
3
votes
0answers
44 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
1answer
110 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
139 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
0answers
85 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
108 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
71 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
40 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
77 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
138 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
109 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
122 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
215 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 ...
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
71 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
216 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 ...
9
votes
0answers
73 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 ...
3
votes
1answer
118 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 ...
5
votes
1answer
68 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
75 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 $\...

1
2 3 4 5
28