1. All Categories
2. Theoretical Computer Science

# Theoretical Computer Science : Recent Questions and Answers

## 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...

## Find min-weight simple path assuming no negative simple cycles

A simple path is a path that doesn't revisit a node. A simple cycle is a cycle that doesn't revisit an edge. You are given an undirected graph G which...

Asked on 12/19/2021 by Craig Gidney

## Complexity of Model Enumeration in function free, equality free, First Order Logic with only Unary Predicates?

This question has inspired the following two questions.Given a first order logic language, with only unary predicates, finite number of variables, $forall$ and $exists$ i.e no...

## Reducing the Height of Context-Free Grammars

Let $G$ be a context free grammar in Chomsky normal form (CNF) with language $L(G)subseteq Sigma^n$. In other words, all strings generate by $G$ have size $n$. Say that...

Asked on 11/26/2021 by Mateus de Oliveira Oliveira

## Dynamic matrix-matrix multiplication

Suppose A and B are initial Boolean matrices. Let C = A*B. Suppose one can perform the sequence of the next operations: "set A[i,j] = 1", "set B[i,j] = 1"....

## 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...

## Proving membership in W-hierarchy when problem is not parameterized by its solution size

I'm curious about the following general problem: Suppose that we have a parameterized problem whose input is $x$ and parameter is $k$ (which is NOT the size of...

## Find a boundary from set of 3d line segments

I have a set of n 3d line segments [(p1_start,p1_end), (p2_start,p2_end),....(pn_start,pn_end)].(I believe that they shod be nin-intersecting...)These segments represent a (closed) boundary. I am looking for...

## approximate maximum clique given vertex cover

I have a non optimal vertex cover of size k of a graph G, and I want to get a (1+epsilon)-approximation kernel of size linear in k for maximum clique...

## Any fundamental papers in TCS which were found to be incorrect/wrong later?

I am asking this question out of curiosity. I recently encountered this well-known paper on (published in 2009):the hardness_of_Euclidean_kmeans The paper showed that the previous NP-hardness result...