1. All Categories
  2. Theoretical Computer Science

Theoretical Computer Science : Recent Questions and Answers

Find answers to your questions about Theoretical Computer Science or help others by answering their Theoretical Computer Science questions.

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

Asked on 12/24/2021

0 answer

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

0 answer

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

Asked on 11/28/2021

2 answer

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

2 answer

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

Asked on 11/26/2021 by gsv

0 answer

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

Asked on 11/23/2021 by Freiburger0

0 answer

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

Asked on 11/19/2021 by Haden Hooyeon Lee

1 answer

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

Asked on 11/14/2021

1 answer

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

Asked on 11/06/2021 by markHall

1 answer

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

Asked on 10/30/2021

9 answer

Ask a Question

Get help from others!

© 2022 All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP