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
0
votes
0answers
4 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$....
0
votes
0answers
26 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
32 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
60 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
204 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 ...
8
votes
0answers
61 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
108 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
60 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
57 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 $\...
5
votes
1answer
67 views

Series-parallel DAG characterization

According to this Wikipage series-parallel graphs are characterized like this: 2-connected series-parallel graphs are characterized by having no subgraph homeomorphic to $K_4$. I couldn't find a ...
3
votes
1answer
86 views

Decomposing Single Crossing Minor Free graphs

We know that for a single-crossing graph H of size h, there exists a constant ch whose value depends only on h, such that every four-connected component of an H-minor-free graph is either a planar ...
4
votes
0answers
76 views

Complexity of Encoding a Matroid Flow Problem in a Matrix

Context: Take a directed graph $G$ with a specified subset of source vertices $S$ and target vertices $T$. We say a subset $I\subseteq T$ of size $r$ is independent if there exist $r$ distinct ...
1
vote
0answers
43 views

Complement of Multi-colored Clique with an extra condition

In the problem Multi-colored clique, we ask for a $k$-clique of the input graph $G$ where $G$ is guaranteed to be $k$-colorable. In the complement problem Independent Set given Clique Partition, we ...
5
votes
1answer
77 views

Generate cut $(A,B)$ in edge-colored graph $(V,E_1 \cup E_2)$ such that there are more red than white crossings, i.e $|E_1(A,B)| > |E_2(A,B)|$

Let $G=(V,E)$ be graph. Recall that a cut of $G$ is (or can uniquely be identified with) a pair $(A,B)$ of nonempty subsets of $V$ which partition it. Given a cut $(A,B)$, let $E(A,B) := \{(a,b) \in ...
2
votes
1answer
81 views

Complexity of Multi-colored Clique when every color pair induce biclique+isolated vertices

I am interested in the MulitColoredClique problem with an additional restriction. (Def.: A $k$-coloring $V_1,V_2,\dots,V_k$ of a graph $G$ is a partition of the vertex set of $G$ into $k$ independent ...
5
votes
0answers
102 views

Computational complexity of finding paths with specified product in a (group-labeled) directed graph

This question came up in the analysis of the puzzle game Swish. One way of representing the solvability problem is this: given a directed graph $G$ where each edge of the graph is labeled with an ...
0
votes
0answers
41 views

Isomorphism preserving transformation to graph of logarithmic boolean-width

In short we found isomorphism preserving graph to graph of logarithmic boolean-width. The paper On graph classes with logarithmic boolean-width claims that some graph problems are fixed parameter ...
0
votes
1answer
110 views

Graphs-like data structure with weighted vertices

I am searching for literature related to a graph-like data structure where vertices are weighted instead of edges. Formally, we can define a weighted-(edge)-graph $G=(V,E, w(\cdot))$ as a tuple of ...
5
votes
1answer
358 views

Isomorphic graph embeddings in the Euclidean Space

Given an undirected and unweighted graph $G = (V, E)$, is it possible to find a mapping $f: V \rightarrow \mathbb{R}^k$ for some $k$ such that for every $i, j \in V$, $\|f(i) - f(j)\|_2^2 = \Delta(i, ...
-1
votes
1answer
78 views

Al-Mubaid's Similarity Measure for Ontological Concepts

Al-Mubaid et al. proposed a semantic similarity measure in their research paper [1]. They see ontologies as connected graphs but refer to clusters within ontology graphs without ever defining what ...
2
votes
1answer
94 views

Complexity of acyclicity of a “nondeterministic” graph

By "nondeterministic" I mean the graph is a collection of sets of "candidate" edges sharing a single destination: $E \subseteq 2^V \times V$. The problem is whether it is possible ...
2
votes
1answer
129 views

MaxCut instance with smallest max cut

Let us look at all 4-regular undirected graphs with $n$ nodes and edge weight equals to 1 for all edges. Out of these graphs, I would like to find the MaxCut instance with least number of edges in its ...
1
vote
0answers
178 views

Disproving $\oplus$ETH by reducing $\oplus k$-SAT with $n$ variables and $m$ clauses to planar graph with $o(m^2)$ vertices?

In this question and its answer, they discuss about reducing CNF-SAT with $n$ variables and $m$ clauses to a (problem on) planar graph $G=(V,E)$ with $|V|$ as small as possible. It is said that the ...
5
votes
1answer
169 views

Complexity of finding the most likely edge

Consider a connected, unweighted, undirected graph $G$. Let $m$ be the number of edges and $n$ be the number of nodes. Now consider the following random process. First sample a uniformly random ...
0
votes
1answer
75 views

Sample graph dataset for testing algorithms

I hope I'm addressing the right community. For a project for my students, I need to find some weighted graphs (oriented or not) to benchmark their algorithms (shortest paths, flows...). There are a ...
1
vote
0answers
29 views

Minimum graph cycle basis respect to non-empty pairwise intersection of cycles

I'm trying to understand the following problem if anyone can help I'll be very grateful Instance: undirected, unweighted, connected graph graph $G=(V,E)$. Question: find a minimum cycle basis $B = \{...
2
votes
0answers
50 views

The Edge Cover Equilibrium Problem

Let the Edge Cover Equilibrium Problem be the following: INPUT: a simple undirected graph $G$. OUTPUT: YES, if the number of edge covers of $G$ having odd cardinality is equal to the number of edge ...
1
vote
0answers
76 views

Is the edge cover polytope integral on graphs with self-loops?

It is well known that the edge cover polytope is integral on simple graphs. I am wondering whether this also holds for graphs with self-loops. Here is a Linear Relaxation of the edge cover polytope, ...
0
votes
0answers
54 views

Comparing two graphs when starting from a single edge

Let's assume that we are given two graphs $G_1$ and $G_2$ defined by the two following nicely drawn pictures. Black numbers label the nodes, red numbers show the edge weight between the nodes. $G_1$ ...
3
votes
1answer
115 views

Isomorphism preserving transformation CNF to Graph?

In short we are interested in isomorphism preserving transformation CNF to Graph. Let $\phi_1,\phi_2$ be CNF formulas. Define $\phi_1$ and $\phi_2$ to be isomorphic $\phi_1 \cong \phi_2$ if there ...
0
votes
0answers
106 views

Is the matching polytope integral?

In this document https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture9.pdf they prove the integrality of the matching polytope using the integrality of the perfect matching polytope. The ...
4
votes
1answer
129 views

Neighborly properties in a bipartite graph

Input: Let $G$ be a connected, bipartite graph with parts $A$ and $B$, each of size $n$. For a set of vertices $S$, let $N(S)$ be its set of neighbors. Question: Decide whether there exists a subset $...
2
votes
0answers
114 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
42 views

Non-rigid isomorphic structures

In many of the problems trying to solve hidden shift over some objects like graphs mainly the rigid classes are considered. For eg. in this and this isomorphism problem restricted over rigid graphs is ...
1
vote
1answer
97 views

On the paper “Quantum Computing Hamiltonian cycles”

The paper Quantum Computing Hamiltonian cycles claims: An algorithm for quantum computing Hamiltonian cycles of simple, cubic, bipartite graphs is discussed. It is shown that it is possible to evolve ...
4
votes
2answers
121 views

3-colourability of Eulerian maximal planar graph

The following paragraph is from this answer by David Eppstein (emphasis mine). A maximal planar graph is 3-colorable iff it is Eulerian (if it is not Eulerian, then the odd wheel surrounding a single ...
2
votes
1answer
107 views

Who proved that a triangulation is 3-colourable implies its dual is bipartite

Let $G$ be a maximal planar graph (also called a triangulation); i.e, $G$ is a planar graph every face of which is a triangle. It is well known that the following three statements are equivalent: (i) $...
1
vote
0answers
106 views

Quantum error correction and graph codes

I was reading combinatorial approach towards quantum correction. A lot of work in this is on finding diagonal distance of a graph. Let me add definition of diagonal distance so that this remains self-...
9
votes
3answers
652 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 ...
9
votes
1answer
335 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 ...
10
votes
1answer
140 views

Is there a planar 4-regular graph that is 3-acyclic colourable?

A colouring is said to be an acyclic colouring if there is no bicoloured cycle (i.e each cycle gets at least 3 colours). Burstein proved that 4-regular graphs are 5-acyclic colourable. It seems to me ...
3
votes
0answers
107 views

Graph problems in P with unknown lower bounds

I am looking for references to interesting graph problems, which are known to be in P, but their precise big-O lower bounds are elusive. I would split this into 2 classes: problems, where we know of ...
-2
votes
2answers
151 views

Proof that optimal solutions of LP Relaxation of independent set are half-integral

I saw somewhere that optimal solutions of LP Relaxation of independent set are half-integral, by what I mean the possible values of a solution are ${ \{0,0.5,1 \} }$. I'm looking for proof of that. ...
0
votes
0answers
33 views

Different version of approximation complexity and algorithm for densest-k-subgraph problem

In the densest-k-subgraph problem, we are given a graph $G =(V,E)$ and $k$, and we are asked to find a set $S \in V$ of vertices to maximize the number of edges in the induced graph of $S$, i.e. $|Ind[...
1
vote
1answer
97 views

Intuition behind the Charikar's LP formulation for densest subgraph problem

I understand why the LP gives the optimal solution for the densest subgraph problem. But don't understand the intuition behind the LP in this paper. Just mentioning the LP for maximum density of a ...
9
votes
1answer
151 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 ...
7
votes
1answer
708 views

Algorithm for finding a 3-cycle cover

Given: An undirected, unweighted graph Looking for: A disjoint vertex cycle cover where every cycle has at least 3 edges Is there any algorithm that solves this problem, possibly with some ...
4
votes
0answers
105 views

Network design with reachability pattern

We are given two sets of terminals $A$ and $B$. For each $a\in A$, we are also given $R_a\subseteq B$. Let $|A|+|B|=n$. We want to find a directed acyclic graph $G$ where $A$ and $B$ are subsets of ...
2
votes
2answers
236 views

Is the maximum independent set in cubic planar graphs NP-complete?

In their famous book, Garey and Johnson, write a comment that the maximum independent set problem, in cubic planar graphs is NP-complete(page 194 of the book). They say this is by a transformation ...

1
2 3 4 5
27