All Questions
71 questions
1
vote
1
answer
119
views
Problem NP-completeness on a specific graph class
Consider the class of simple connected n/2-regular graphs, n even. Are the maximum clique problem and/or maximum independent set problem NP-complete on such graphs? Is there any known result which ...
- 105
2
votes
0
answers
91
views
Blind construction of planar graph with additive spanning tree count
Suppose we have two planar graphs $G_1$ and $G_2$ with number of spanning tree count $P_1$ and $P_2$ respectively then there is an easy construction which gives a planar graph with spanning tree count ...
- 13.9k
7
votes
0
answers
203
views
Upper bound on the number of perfect matchings in $K_{3,3}$-free graphs
Let $G=(V,E)$ be a graph with an even number of vertices $|V|=2n$. Assume that $G$ is $K_{3,3}$-free i.e. it does not contain a graph isomorphic to biclique $K_{3,3}$. A perfect matching of $G$ is a ...
- 965
1
vote
0
answers
185
views
Maximum independent set in dense graphs
Let $0 < A < 1$ and $G$ be connected d-regular graph
with degree $d=[A n]$. The density of $G$ is about $A$.
Q1 Are there constraints on $A$ such that finding maximum
independent set of $G$ is ...
- 25.4k
1
vote
1
answer
218
views
What is this invariant graph?
Let $G$ be a simple graph (finite or infinite), $[n]\mathrel{:=}\{1,...,n\}$. Define the function:
$$\varepsilon_n(G)\mathrel{:=}\min_\phi{\lvert{\operatorname{dom} (\phi)}\rvert},$$
where $\phi$ is ...
- 107
1
vote
0
answers
75
views
Subgraph isomorphism problem with linear map
I am working on proving the NP-hardness of a problem by reducing it from the subgraph isomorphism problem. Currently, I can reduce it from the following problem:
Problem 1: Given two graphs $G=(V, E)$ ...
- 101
1
vote
0
answers
176
views
Reduction graph isomorphism to maximum independent set in very dense graph
We got a reduction graph isomorphism to MIS in a very dense graph,
or alternatively negative monotone 2-CNF to MAX-ONEs with a formula
with many clauses.
Let $G,H$ be graphs of order $n$ and adjacency ...
- 25.4k
2
votes
0
answers
70
views
Isomorphism preserving transformation graph to graph of logarithmic boolean width and bounded degeneracy
The paper On graph classes with logarithmic boolean-width
claims that some graph problems are fixed parameter tractable with parameter
the boolean width.
In particular, boolean-width of the complement ...
- 25.4k
1
vote
0
answers
147
views
The chromatic polynomial of a line graph
Is there a way to obtain the chromatic polynomial of the line graph of a regular simple graph, having known the chromatic polynomial of the graph?
There already exist characterizations of line graph ...
- 2,089
0
votes
1
answer
147
views
Complexity of edge coloring of class 1 graphs
We know that the decision problem of classifying the graphs as class $1$ or class $2$ (with respect to edge coloring) is NP-complete. But, suppose we have to prove a graph to be in class $1$. Does it ...
- 2,089
1
vote
1
answer
157
views
Is the graph minicut with the node cardinality constraint NP-hard?
I wonder whether the following problem is a well-studied NP-hard problem?
Get a graph $G$ and a number $k$, we partition the graph $G$ into two components where each component should have at most $k$ ...
- 111
1
vote
1
answer
137
views
Complexity of edge coloring graphs with $\Delta(G) \ge n/3$ assuming the overfull conjecture
Closely related to this on cstheory.
Let $G$ be graph of order $n$ with $\Delta(G) \ge n/3$.
Assume the overfull conjecture.
Can we edge color $G$ with minimal number of colors in polynomial time?
...
- 25.4k
1
vote
0
answers
45
views
Coloration of an interval graph with constraints [closed]
Given an interval graph that represents a set of tasks, in a given period of time, to be assigned to a set of employees, the objective is to find a minimum coloring of this graph such that the total ...
- 11
3
votes
1
answer
182
views
Edge coloring graphs is in P?
It is known that there exist polynomial time algorithm to approximate the Lovasz number or the supremum of Shannon capacity of graphs.
By Vizing's theorem, the graph $G$ has only two chromatic ...
- 2,089
0
votes
0
answers
82
views
Proving Vizing's and Brooks' theorem using the polynomial approach
It is known that the graph polynomial defined by $\prod_{i<j}(x_i-x_j)$ where the vertices $x_k\ \ , \ \ k=\{1,2\ldots,n\}$ are ordered with respect to some order; can be used to verify the proper ...
- 2,089
5
votes
1
answer
214
views
Graphs with Hermitian Unitary Edge Weights
Very recently, Hao Huang proved the Sensitivity Conjecture, which had been open for 30 years or so. Huang's proof is surprisingly short and easy. Here is Huang's preprint, a discussion on Scott ...
3
votes
2
answers
235
views
Strong chromatic index of some cubic graphs
Edit 2019 June 26 New computer evidence forces us to revise our guesses relating strong chromatic index and girth
Edit 2019 June 25 Some mistakes have been corrected. Question 2 has changed.
...
- 1,018
-4
votes
1
answer
220
views
What is the computationally simplest way to universally index the set of simple graphs?
If given a simple, integer-labeled, but not necessarily connected, graph $G := (V,E)$ consisting of at least one vertex, i.e. $\lvert \rvert V \lvert \rvert \geq 1$, then is there a function to ...
- 387
1
vote
1
answer
82
views
The complexity on calculation of the Graev metric on the free Boolean group of a metric space
For a set $X$ by $B(X)$ we denote the family of all finite subsets of $X$ endowed with the operation $\oplus$ of symmetric difference. This operation turns $B(X)$ into a Boolean group, which can be ...
- 41.8k
7
votes
0
answers
93
views
Combinatorial region-halfplane incidence structures
I've seen a bunch of similar MO questions, yet hopefully this is not a complete duplicate.
Consider $n$ halfplanes in $\mathbb{R}^2$ with their borders in general position, that is, no point of $\...
- 5,590
1
vote
0
answers
78
views
Bipartite clustering is NP-hard?
Let $G = (A\cup B, E)$ be a bipartite graph with edge weights $w: E\to \mathbb{R}$. Find a partition $B_1, B_2$ of $B$ and a nonempty disjoint subsets $A_1, A_2$ of $A$ such that $w(A_1,B_1) + w(A_2, ...
- 221
21
votes
0
answers
441
views
Straight-line drawing of regular polyhedra
Find the minimum number of straight lines needed to cover a crossing-free straight-line drawing of the icosahedron $(13\dots 15)$ and of the dodecahedron $(9\dots 10)$ (in the plane).
For example, ...
- 4,535
0
votes
1
answer
140
views
Maximum partition of bipartite graph
Let $G = (U, V, E)$ be a bipartite graph. Let $w: E \to \mathbb{R}$ be a weight function on the edge set $E$. Given subsets $U_1,\ldots, U_k \subset U, U_i\cap U_j = \emptyset$ and a partition $V_1,\...
- 221
0
votes
0
answers
149
views
Is 3-coloring bounded degree graphs subexponential: $O(\exp{(\sqrt{n}\log^2{n})})$?
We got an argument that 3-coloring bounded degree graphs is subexponential
with complexity $O(\exp{(\sqrt{n}\log^2{n})})$.
The treewidth of a planar graphs on $n$ vertices is $O(\sqrt{n})$
and 3-...
- 25.4k
2
votes
0
answers
254
views
maximum independent set in d-regular graphs
Does anyone know whether the maximum independent set problem is NP-hard in triangle free d-regular graphs and if it's NP-hard for all d larger than some threshold t? Can anyone provide a reference ...
- 213
7
votes
2
answers
324
views
Graph isomorphism problem for minimally strongly connected digraphs
A minimally strongly connected digraph (MSC) is strongly connected (SC), while removal of any arc destroys this. That is, between any two vertices a, b there exists a directed path from a to b, while ...
4
votes
0
answers
84
views
Complexity of counting colorings of co-bipartite graphs?
A graph is co-bipartite if it is the complement of bipartite graph.
What is the complexity of counting colorings of co-bipartite graphs?
Unlike split graphs, the chromatic polynomial isn't of ...
- 25.4k
5
votes
2
answers
412
views
An interesting variant on the maximum independent set problem.
Suppose i have a graph $G=(V,E)$ with $|V|=n$. Furthermore suppose i give you a maximum independent set $\mathcal{I}$ in $G$. Now suppose i obtain a new graph $G'$ from $G$ by removing a single vertex ...
- 213
3
votes
0
answers
98
views
Is the Graph Isomorphism problem in βP class?
βP is the limited nondeterminism NP, cf. https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#betap
Last year Laslo Babai proved that the GI problem can be solved in (deterministic) time
$\exp(\log^c(...
- 193
3
votes
2
answers
362
views
Sparse graphs that are hard to color
I am interested in knowing if there are any types of graphs that are very sparse, perhaps consisting of just connections between paths and cycles, and for which $k$-coloring is $\mathsf{NP}$-hard for ...
- 213
11
votes
3
answers
3k
views
Do you know a faster algorithm to color planar graphs?
while studying the four color theorem, I implemented an algorithm (in Python and Sage) that can color planar graphs much faster than the implementations I found around on internet.
The program can be ...
- 351
3
votes
1
answer
497
views
Which is the most time efficient algorithm for having a Tait Coloring (edge-3-coloring) of planar cubic graphs?
Crossposted from: https://math.stackexchange.com/questions/1964486/which-is-the-most-time-efficient-algorithm-for-having-a-tait-coloring-edge
I wasn't able to find an efficient algorithm nor an ...
- 351
1
vote
0
answers
139
views
bounded degree graph colouring.
I was wondering if anyone could provide references on the following:
Is determining the chromatic number of a bounded degree graph APX-complete?
2.I've seen the result that states it is NP-hard to ...
- 903
3
votes
0
answers
181
views
Hypergraph edge colouring
I'm interested in knowing if finding the edge-chromatic number of a $k$-uniform $k$-partite hypergraph is NP-hard for $k\geq 3$ Could anyone provide a reference for the result? By edge-chromatic ...
- 903
1
vote
1
answer
332
views
Graph colouring for bounded degree graphs
I'm fairly new to colourings on bounded degree graphs i'm interested in the following questions,
For planar graphs with bounded degree $4$ is finding the colouring number $NP$-hard? So is ...
- 903
2
votes
1
answer
93
views
Directed edge-colouring
I'm interested to know whether the following problem is NP-complete or if there is an algorithm to solve it.
Suppose we are given a directed graph $G=(V,E^{\rightarrow})$ and we want to colour the ...
- 903
1
vote
0
answers
34
views
Some confusion regarding the definition of NPO reduction
I've seen the following definition in a paper on approximation preserving reductions.
Definition:Let $\pi_{1}$ and $\pi_{2}$ be two NPO maximization problems. Then we say that $\pi_{1} \leq_{R} \pi_{...
- 213
6
votes
2
answers
2k
views
How can I prove that these two graph coloring problems are polynomial time equivalent?
Given a graph $G(V,E)$. The standard $k$-coloring problem consists in finding a feasible coloring (no two adjacent nodes share the same color) of the nodes with $k$ colors. Let this problem be $P_1$.
...
- 225
3
votes
1
answer
215
views
Construction of planar embedding
I'm reading the following paper on universality considerations in VLSI circuits
http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf
In Theorem 2 On the second page it states there exists ...
- 903
4
votes
0
answers
175
views
What is known about the complexity of this covering problem?
Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called critical if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex ...
- 2,966
5
votes
1
answer
291
views
Minimum number of edges to remove to have low degree
I have the following problem, where $k$ is a fixed integer.
Input: Graph $G$.
Output: Minimum number of edges to remove from $G$ to obtain a graph such that every node has degree at most $k$.
Do ...
- 613
2
votes
0
answers
350
views
NP hard problems on geometric graphs
I have posted this question before but i don't feel i expressed my confusion clearly enough. So i would like to try and explain again. This is a proof of the minimum vertex cover for unit disk graphs ...
- 903
2
votes
1
answer
320
views
NP hard problems on UD graphs
I'm reading up on NP hard problems in Unit Disk graphs. I'd like to point out i'm fairly new to this NP hard stuff so i'm trying to get around how to prove something is NP hard.
http://ac.els-cdn....
- 903
1
vote
1
answer
100
views
Is it known whether Minimum Cost Multicut is APX-hard?
My questions is concerned with the following problem: Given an undirected graph $G = (V, E)$ and (edge costs) $c \in \mathbb{Z}^E$,
$$\min \left\{ \sum_{e \in E} c_e x_e\ \middle|\ x \in \{0,1\}^E \ \...
- 119
1
vote
0
answers
68
views
Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs
Let $C$ be a graph class defined by a finite
number of forbidden induced subgraphs, all
of which are cyclic (contain at least one cycle).
Are there graph problems that can be solved in
polynomial ...
- 25.4k
47
votes
7
answers
5k
views
Is it easy to produce hard-to-color graphs?
This question arises from my recent visit to my daughter's second-grade class, where I led some discussion and activities on graph coloring (see Math for seven-year-olds). In one such activity, each ...
- 236k
25
votes
2
answers
2k
views
Who first dubbed them "expander graphs"?
Expander graphs
("sparse graphs that have strong connectivity properties")
burst onto the mathematical scene around the millennium, but I have not
been successful in tracing the origin of
(a) the ...
- 151k
2
votes
1
answer
183
views
Is the domination number NP for non-bipartite graphs?
Calculating the domination number is an NP-Hard problem. Does it remain NP-Hard if we restrict it to non-bipartite graphs?
- 6,962
7
votes
1
answer
484
views
Seeming contradiction about P vs NP between graphclasses.org and at least two papers about clique in even-hole-free graphs
I believe correctness about clique in even-hole-free graphs
of graphclasses.org
and the paper Vertex elimination orderings for hereditary graph classes, Pierre Aboulker, Pierre Charbit, Nicolas ...
- 25.4k
8
votes
1
answer
418
views
A combinatorial problem concerned with logic circuits
Consider a logic circuit with two-bit gates only. The length of each gate is the number of bit lines that the gate crosses. How hard is to compute the maximum length for a given circuit? Notice that ...
user3409